Pure Exploration for a Good Policy in Reinforcement Learning with Bandit Feedback
LI ZITIAN, Cheung Wang Chi · 2026
Read Pure Exploration for a Good Policy in Reinforcement Learning with Bandit Feedback by LI ZITIAN, Cheung Wang Chi (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-23182.txt.
Introduction
Li and Cheung study Good Policy Identification in serial reward learning with bandit feedback. For a reward threshold, GPI needs finding a policy with mean reward in an episode at least the threshold if such a policy exists, or saying None otherwise. They define GPI under the fixed-trust setting, needing the output to be correct with chance at least 1 minus delta, and cutting the mean number of runs tried. They propose method BEE-GPI, giving upper bounds on its sample cost for good and bad cases.
Catalog record
| CREATOR | LI ZITIAN, Cheung Wang Chi |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 174990 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2605.23182
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Pure Exploration for a Good Policy in Reinforcement Learning with Bandit Feedback LI ZITIAN, Cheung Wang Chi Abstract Pure exploration in episodic Reinforcement Learning has primarily focused on Best Policy Identification (BPI), which seeks to identify a (near)-optimal policy with high confidence. Motivated by practical settings where a “good enough” policy suffices, we study an alternate objective of Good Policy Identification (GPI). For a given reward threshold μ 0 \mu_{0} , GPI only requires identifying a policy with expected reward in an episode at least μ 0 \mu_{0} if such a policy exists (positive instance), or declaring None if no such policy exists (negative instance). We formalize GPI under the fixed-confidence setting. We require the output to be correct with probability ≥ 1 − δ \geq 1-\delta , and seek to minimize the expected sample complexity, which is the expected number of episodes explored for the output. We propose a novel algorithm BEE-GPI, and derive theoretically-grounded upper bounds on its sample complexity for positive and negative instances. Notably, for positive instances, the coefficient of log 1 / δ \log 1/\delta in our upper bound is O ( H 2 / ( V ∗ − μ 0 ) 2 ) O(H^{2}/(V^{*}-\mu_{0})^{2}) , where H H is the episode length and V ∗ V^{*} is the optimal expected reward in an episode. The coefficient does not depend on the action and state space sizes otherwise, in sharp contrast to the sample complexity in BPI. We further establish lower bound results to show the near-optimality of BEE-GPI and the necessity of the 1 / ( V ∗ − μ ) 2 1/(V^{*}-\mu)^{2} term. Numerical experiments further validate the efficiency of our approach. 1 Introduction Pure exploration is a fundamental objective in Reinforcement Learning (RL), where a learning agent seeks to identify a policy that satisfies specific performance criteria. Unlike the regret minimization framework, pure exploration prioritizes the probability of correct identification and sample efficiency over total episodes. To date, most research in this field has concentrated on Best Policy Identification (BPI) or \epsilon -Best Policy Identification ( \epsilon -PI), leaving the problem of Good Policy Identification (GPI) largely unexplored. In an episodic Markov Decision Process (MDP) with unknown transition dynamics, GPI requires the agent to identify a policy whose value function exceeds a pre-specified threshold \mu_{0} , if such a policy exists, or to return None otherwise. Many real-world applications necessitate finding a “good enough” policy rather than a nearly optimal one, particularly when precise pairwise comparisons are computationally or practically difficult. For instance, in medical informatics, a new treatment protocol is typically evaluated against a known Standard of Care (with known utility \mu_{0} ). The objective is to identify a treatment sequence that ensures a patient recovery rate or “Years of Life Gained” whose utility is \geq\mu_{0} . In such cases, identifying the absolute best treatment with a high confidence 1-\delta is often unnecessary, especially when the performance differences among top-tier policies are marginal. Similarly, in cloud computing, service providers use RL for traffic routing and resource allocation. Rather than seeking an absolutely optimal routing rule, providers often aim to ensure reliability and efficiency levels that exceed a specified Service Level Agreement. Furthermore, institutional investors frequently evaluate whether a new trading strategy meets a minimum Sharpe ratio or Return-on-Investment (ROI) benchmark before deployment. This benchmark \mu_{0} is often derived from established indices with extensive historical data. In these scenarios, the primary concern is determining whether a new alternative is competitive relative to the benchmark, rather than finding the best strategy among all possibile ones. Main Contributions. We provide three primary contributions. First, we formalize the Good Policy Identification (GPI) problem in the fixed-confidence setting. Given a failure probability tolerance parameter \delta\in(0,1) , the learning agent must identify a policy with expected reward at least threshold \mu_{0} (or correctly identify its non-existence) with probability \geq 1-\delta . Second, we develop BEE-GPI, a novel \delta -PAC algorithm that utilizes a early-stopping BPI sub-routine as an oracle to achieve efficient sample complexity. We provide a rigorous upper bound on its expected sample complexity, demonstrating that for positive instances, the coefficient of \log(1/\delta) shrinks with the gap (V^{*}-\mu_{0}) , but is independent of the state and action space sizes. Third, we establish lower bounds for the GPI problem. The resulting gap between our upper and lower bounds is limited to a polynomial factor of S,A , and H , indicating that BEE-GPI is nearly optimal. Notation. Denote \mathbb{N},\mathbb{R} as the sets of positive integers and real numbers respectively. For n\in\mathbb{N} , denote [n]=\{1,\ldots,n\} . We abbreviate a random variable R following the probability distribution p as R\sim p . Problem Formulation. An instance of the Good Policy Identification (GPI) problem is specified by the tuple \nu=(\mathcal{S},\mathcal{A},\mu_{0},\delta,H,R,P,\mathsf{p}) . The sets \mathcal{S} and \mathcal{A} denote the finite state and action spaces, respectively. We denote S,A as the respective cardinalities of \mathcal{S},\mathcal{A} . The scalar \mu_{0}\in\mathbb{R} is the reward threshold, which is the expected total reward in an episode that the learning agent aims to accrue. The error parameter \delta\in(0,1) is the tolerance level on the probability of an incorrect output. The integer H represents the episode horizon. The transition kernels and reward function are respectively denoted by P=\{p_{h}(\cdot|s,a)\}_{h\in[H],s\in\mathcal{S},a\in\mathcal{A}} and R=\{r_{h}(s,a)\}_{h\in[H],s\in\mathcal{S},a\in\mathcal{A}} , respectively. At round h\in[H] when the agent is at state s\in\mathcal{S} and takes action a\in\mathcal{A} , the agent earns a deterministic reward r_{h}(s,a)\in[0,1] , and transits to states s^{\prime} with probability p_{h}(s^{\prime}|s,a) . The initial state S_{1} is distributed according to the initial distribution p . We assume \mathcal{S},\mathcal{A},\mu_{0},\delta,H,R are known to the agent, while P,\mathsf{p} are not known. To facilitate our discussion on P,\mathsf{p} , we prepend each episode with a fictitious time round 0 . Round 0 is associated with one fictitious s_{0} and the single fictitious action a_{0} , which carry zero reward and yield state transition p_{0}(\cdot|s_{0},a_{0})=\textsf{p}(\cdot) . A policy \pi is expressed as (\pi_{h})^{H}_{h=1}\in\Pi^{H} , where \Pi=\{f~|~f:\mathcal{S}\rightarrow\mathcal{A}\} consists of mapping from the current state to an action. Thus, \Pi^{H} is the space of all deterministic policies, and \pi_{h} determines the action in round h\in[H] . The value function of \pi from round h to the end of the episode is \displaystyle V_{h}^{\pi}(s_{h}):=\mathbb{E}^{\pi}\left[\sum_{\ell=h}^{H}r_{\ell}(s_{\ell},\pi_{\ell}(s_{\ell}))\mid s_{h}\right], where s_{\ell+1}\sim p_{\ell}(\cdot|s_{\ell},\pi_{\ell}(s_{\ell})) . Let \pi^{*}\in\Pi^{H} denote an optimal policy. By Bellman optimality, we have V_{h}^{\pi^{*}}(s)\geq V_{h}^{\pi}(s) for any policy \pi and s\in\mathcal{S},h\in[H] . We abbreviate V^{*}_{0}(s_{0})=V^{\pi^{*}}_{0}(s_{0}) as the optimal total expected reward in an episode, and occasionally append the instance \nu to denote V^{*}_{0}(s_{0}~|~\nu) to emphasize the dependence on \nu . Dynamics. The agent’s algorithm is characterized by a sampling rule \{\pi^{t}\}_{t=1}^{\infty} , a stopping time \tau , and a recommendation rule \hat{\pi} . When episode t\in\mathbb{N} begins, the algorithm selects a policy \pi^{t}=(\pi_{h}^{t})_{h=1}^{H}\in\Pi^{H} based on the collected data \mathcal{D}_{t-1} in episodes 1,\ldots,t-1 . Executing \pi^{t} on the instance generates the trajectory z_{t}=(s_{0},a_{0},S_{t,1},A_{t,1},r_{1}(S_{t,1},A_{t,1}),\dots,S_{t,H},A_{t,H},r_{H}(S_{t,H},A_{t,H})) , where S_{t,h}\sim p_{h-1}(\cdot|S_{t,h-1},\pi^{t}_{h-1}(S_{t,h-1})) . This trajectory is added to the history, i.e. \mathcal{D}_{t}=\mathcal{D}_{t-1}\cup\{z_{t}\} , where we initialize \mathcal{D}_{0}=\emptyset . At the end of an episode, the agent may choose to terminate the algorithm. We define the stopping time \tau as the index of the terminating episode. Upon termination, the agent outputs an answer \hat{\pi}\in\Pi^{H}\cup\{\textsf{None}\} based on \mathcal{D}_{\tau} . The agent aims to