Technical Summary: Pure Exploration for a Good Policy in Reinforcement Learning with Bandit Feedback

1. Problem Formulation

This paper addresses the Good Policy Identification (GPI) problem within the framework of Pure Exploration in Reinforcement Learning (RL). Unlike the traditional Best Policy Identification (BPI) objective, which seeks to identify a (near)-optimal policy with high confidence, GPI focuses on finding a policy that satisfies a specific performance threshold.

Formally, given an episodic Markov Decision Process (MDP) with unknown transition dynamics $P$ and initial distribution $p$, a finite state space $S$, action space $A$, and horizon $H$, the agent is provided with a reward threshold $\mu_0$. The goal is to design a $\delta$-Probably Approximately Correct ($\delta$-PAC) algorithm that:

• Positive Instance: If there exists a policy $\pi$ such that its expected total reward $V^\pi_0(s_0) \ge \mu_0$, the algorithm must output such a policy with probability at least $1-\delta$.
• Negative Instance: If the optimal policy's value $V^*_0(s_0) < \mu_0$, the algorithm must output "None" with probability at least $1-\delta$.

The performance metric is the expected sample complexity (the expected number of episodes explored, denoted as $\tau$) required to reach a correct decision. The paper explicitly excludes the case where $V^*_0(s_0) = \mu_0$, as previous work (Degenne and Koolen [2019]) established that any $\delta$-PAC algorithm would require infinite samples in this boundary case.

2. Methodology: BEE-GPI

The authors propose a novel algorithm named BEE-GPI (Balanced Exploration-Exploitation for Good Policy Identification). The algorithm operates in phases $k=1, 2, \dots$, where each phase consists of an adaptive exploration stage followed by a decision branching mechanism.

Key Components:

1. Exploration Stage (ES-BPI-UCRL):

   • This stage utilizes an Early-Stopping BPI-UCRL oracle. It employs an optimistic sampling strategy (similar to BPI-UCRL) to estimate the transition kernels and value functions.
   • Crucially, it introduces a novel early-stopping mechanism. The oracle checks two conditions at each step:
     • Condition (3): A lower confidence bound on the value of the current optimistic policy exceeds $\mu_0$ (adjusted by a factor $C$). If met, a candidate policy is identified.
     • Condition (4): An upper confidence bound on the optimal value function is below $\mu_0$. If met, the instance is declared negative.
   • If neither condition is met and the exploration budget $T^{ee}_k$ is not exceeded, the algorithm continues sampling.

2. Decision Branching:

   • If the oracle returns "Not Completed," the algorithm proceeds to the next phase with a tighter error tolerance $\delta_k$ and increased budget.
   • If the oracle returns "None" but the confidence is insufficient ($\delta_k \ge \delta/10$), the algorithm continues to the next phase to ensure the $\delta$-PAC guarantee.
   • If the oracle returns a candidate policy $\hat{\pi}_k$, the algorithm enters the Exploitation Stage.

3. Exploitation and Verification:

   • In this stage, the candidate policy $\hat{\pi}_k$ is executed repeatedly to estimate its true value.
   • The algorithm constructs a confidence interval for the empirical mean reward. If the lower confidence bound exceeds $\mu_0$ within a specific sample budget, the policy is output as the solution.
   • If the budget is exhausted without verification, the algorithm returns to the exploration phase of the next iteration.

3. Key Contributions

The paper makes three primary theoretical contributions:

1. Formalization of GPI: The authors formally define the Good Policy Identification problem in the fixed-confidence setting, distinguishing it from $\epsilon$-BPI. They highlight that standard $\epsilon$-BPI reductions are suboptimal for GPI because the gap $V^*_0(s_0) - \mu_0$ is unknown a priori, making the choice of $\epsilon$ difficult.
2. Algorithm Design and Upper Bounds: They propose BEE-GPI and derive theoretically grounded upper bounds on its sample complexity for both positive and negative instances.
   • Positive Instances: The sample complexity is bounded by $O\left(\frac{H^2 \log(1/\delta)}{(V^*_0(s_0) - \mu_0)^2}\right) + O\left(\frac{\text{poly}(S, A, H)}{(V^*_0(s_0) - \mu_0)^2}\right)$.
   • Negative Instances: The bound involves terms coupled with state and action space sizes, specifically $O\left(\frac{(H+1)^4 SA \log(1/\delta)}{(V^*_0(s_0) - \mu_0)^2}\right)$.
3. Lower Bounds and Near-Optimality: The authors establish lower bounds for the GPI problem using constructed "Uniform Instances" (for positive cases) and "Tree Instances" (for negative cases).
   • They prove that for positive instances, any $\delta$-PAC algorithm must incur a sample complexity of $\Omega\left(\frac{H \log(1/\delta)}{(V^*_0 - \mu_0)^2} + \frac{H^2 SA}{(V^*_0 - \mu_0)^2}\right)$.
   • For negative instances, the lower bound is $\Omega\left(\frac{HSA \log(1/\delta)}{(\mu_0 - V^*_0)^2}\right)$.
   • These results demonstrate that BEE-GPI is near-optimal, with the gap between upper and lower bounds limited to polynomial factors of $S, A, H$.

4. Results and Analysis

Theoretical Insights

• Decoupling of Logarithmic Terms: A significant finding is that for positive instances, the coefficient of the $\log(1/\delta)$ term in the sample complexity is $O(H^2)$ and is independent of the state space size $S$ and action space size $A$. This contrasts sharply with standard BPI reductions, where the coefficient typically scales polynomially with $S$ and $A$.
• Asymmetry: There is an inherent asymmetry between positive and negative instances. While positive instances allow for efficient identification of a good policy without exploring the entire state-action space, negative instances require global exploration to certify that no policy meets the threshold, hence the dependence on $S$ and $A$ in the $\log(1/\delta)$ term.

Numerical Experiments

The authors validate their approach using two classic environments: Single Chain and Double Chain MDPs.

• Setup: They compare BEE-GPI against the state-of-the-art BPI-UCRL algorithm (Kaufmann et al. [2021]). To ensure a fair comparison, BPI-UCRL is provided with the oracle parameter $\epsilon = V^*_0 - \mu_0$, giving it significant prior knowledge.
• Findings: Across various thresholds $\mu_0$, BEE-GPI consistently requires significantly fewer episodes to identify a qualified policy compared to BPI-UCRL. The empirical results confirm the theoretical advantage of decoupling the $\log(1/\delta)$ term from the state and action space sizes.

5. Significance and Claims

The paper claims that BEE-GPI offers a more efficient solution for practical RL scenarios where finding the absolute optimal policy is unnecessary or computationally prohibitive, but finding a "good enough" policy (exceeding a benchmark) is critical.

• Practical Relevance: The authors cite applications in medical informatics (identifying treatments exceeding a standard of care), cloud computing (meeting Service Level Agreements), and finance (meeting ROI benchmarks) where the goal is threshold satisfaction rather than optimality.
• Theoretical Advancement: By formalizing GPI and providing near-optimal bounds, the work bridges the gap between theoretical pure exploration and practical threshold-based requirements. It demonstrates that the sample complexity can be significantly reduced when the objective is relaxed from optimality to threshold satisfaction, particularly in the positive instance case.
• Future Directions: The authors modestly suggest that future work could involve deriving tighter instance-dependent bounds and extending this framework to large-scale MDPs using function approximation.

In summary, the paper establishes that identifying a policy meeting a reward threshold is fundamentally different from identifying the best policy, and proposes an algorithm that leverages this distinction to achieve superior sample efficiency, particularly when the gap between the optimal value and the threshold is the primary driver of difficulty.