Instance-Dependent Fixed-Budget Pure Exploration in Reinforcement Learning
Authors: Yeongjong Kim
Yeoneung Kim
Kwang-Sung Jun
Venue: ICLR 2026 Poster (2026)
Keywords: Reinforcement Learning
MDP
pure exploration
fixed budget
Primary area: learning theory
TL;DR: We propose algorithms for fixed-budget pure exploration in reinforcement learning and provide a theoretical analysis of its performance.

Abstract: We study the problem of fixed budget pure exploration in reinforcement learning.
The goal is to identify a near-optimal policy, given a fixed budget on the number of interactions with the environment.
Unlike the standard PAC setting, we do not require the target error level $\epsilon$ and failure rate $\delta$ as input.
We propose novel algorithms and provide, to the best of our knowledge, the first instance-dependent $\epsilon$-uniform guarantee, meaning that the probability that $\epsilon$-correctness is ensured can be obtained simultaneously for all $\epsilon$ above a budget-dependent threshold. It characterizes the budget requirements in terms of the problem-specific hardness of exploration.
As a core component of our analysis, we derive a $\epsilon$-uniform guarantee for the multiple bandit problem—solving multiple multi-armed bandit instances simultaneously—which may be of independent interest. 
To enable our analysis, we also develop tools for reward-free exploration under the fixed-budget setting, which we believe will be useful for future work.

Published as a conference paper at ICLR 2026
INSTANCE-DEPENDENT FIXED-BUDGES PURE EXPLO- RATION IN REINFORCEMENT LEARNING
Yeongjong Kim
Yeoneung Kim
Department of Mathematics
Department of Applied Artificial Intelligence Seoultech k kimyeoneung@@mal com
POSTECH k kim. kim.yjjmossstee wiw.yjjpostech......
Swang-Sung Jun
Department of Computer Science Engineering
POSTECH wwangsungjin@posteccc. ac..ecchhc..............
ABSTRACT
We study the problem of fixed budget pure exploration in reinforcement learning. The goal is identify near-optimal policy, given fixed budget the number of interactions with the environment. Unlike the standard PAC setting, we do not require the target error level and failure rate 5 as input. We propose novel algorithms and provide, to the best of our knowledge, the first instance-dependent s-uniform guarantee, meaning that the probability that e-correctness ensured can be obtained simultaneously for all above budget-dependent threshold. It characterizes the budget requirements in terms of the groblem-specinee hardness of exploration. As a core component of our analysis, we derive e-uniform guarantee for the multiple bandit problem-solving multiple multi-armed bandit instances simultaneoully- -wich may be of independent interest. To enable our analysis, we also develop tools for reward-free exploration under the fixed- buddettdeett setting, which we believe will be useful for future work.
INTRODUCTION
Reinforcement Learning (RL) theory Agarwal et al. (2019) has been studied under two main objec- tives: regret minimization and policy identification, also known as pure exploration. While the former focuses maximizing cumulative reward during learning, the latter aims to identify near-optimal policy without concern for rewards gained during learning. substantial body of work on policy identification has focused on the fixed-confidence setting Kearns and Singh (202)). This line of research, often referred to as Probably Approximately Correct (PAC) RL, requires the algorithm to spend as many samples as possible until it find 8-optimal policy with probability least 1 8. Specifically, the algorithm is required to verify itself that the returned arm is indeed e-optimal policy otherwise, it is not fixed confidence algorithm. Due the verification requirement, both and 0 input to the algorithm. Thus, the analysis must be done for the correctness of the verification (i.c., proving that the returned arm indeed an s-optimal policy) well the sample complexity (i.e.. proving how many samples are taken before stopping).
However, the sred-coofiidecee setting is not the only way to perform policy identification. The fixed-budget setting has been popular in multi-armed bandits (Even-Dar et al. 2006 Bubeck et al. 2009). In this setting, the learner is given fixed number of interactions with environment as budget and is required to output a good policy after exhausting the budget. This setting has numerous merits. First, this setting is arguably more practical because the user of the algorithm can control the budget explicitly. In contrast, the fixed confidence setting assumes that the algorithm many samples as possible (though less is preferred). When stopped forcefully to satisfy practical constraints, it is hard to guarantee the quality of the returned policy. Second, the fixed budget setting has potential to guarantee better sample complexity because there is no verification requirement (i.e., the algorithm itself certifies that the returned policy is e-optimll). This true for multi-armed
use as

---

Published as a conference paper at ICLR 2026
bandits where instant-dependen accelerated rates can be obtained as a function of how many good arms there are, and also a data-poor poor regime guarantee can be obtained, meaning that where a nontrivial performance guarantee is obtained even if the sampling budget is smaller than the number of arms, depending on the problem instance Zhao et al. (203)). These bounds are not likely to be obtained in the fixed confidence setting due the verification requirement unless extra knowledge about the best arm is known such as Chaudhuri and Kalyanakrishnan (2077). While the e-correctness verification from the fixed-confidence setting can be necessary in mission-critical applications, there many applications that do not require such guarantee, in which case the parameters E and á becomes a cumbersome hyperparameter.
Despite the desirable properties of the fixed-budger setting in bandit problems, its counterpart in MDPs remains largely unexplored to our knowledge. In this paper, we take the first step studying fixed-budget policy identification in MDPs, providing new theoretical insights and algorithms that bridge this gap. Specifically. a fixed budget algorithm required take in episode budget B and return policy स at the end of B-th episode. Our central interest is to upper bound the probability that the algorithm fails to return an E-optimal policy as an exponentially decaying function of the budget B and restance-depender quantities, simultaneously for all E 2 e' for some budget dependent threshold e'. We refer to this type of theoretical guarantee as an E- e-umiform guarantee. In other words, the degree of suboptimality of the learned policy is random variable, and are characterizing its distribution, in particular its tail behavior.
Contributions. Our main contributions
follows:
We propose novel algorithm, BREA (Backward Reachability Estimation and Action elimination), which is, to the best of our knowledge, the first fixed-budget pure exploration algorithm for episodic MDPs with ristacc-deepenee only requires the episode budget B as an input, and does not assume the uniqueness of the optimal action.
e-uniform guarantees. The algorithm
For the first time, we establish an e-uniform guarantee for the SAR algorithm (ubbeck et al. 2013) for the muliple bandit problem. This may be of independent interest.
We develop algorithmic and analytical tools for fixed- budget reward- frrard-freeeee exploration by carefully adapting fixed-confidence reward-free exploration algorithm, L2E (Wagenmaker
et al. 2022), to the fixed-budget setting. We prove an e-uniform guarantee for our fixed- budget reward-free algorithms.
PRELIMINARIES
Finite-horizon MDP. We consider finite-horizon non-stationary Markov Decision Process (MDP) defined by the tuple M = (S, A, H, (Pr H-1 | {R, ] Ji where S is a finite set of states of size S. A is finite set of actions of size A, E N is the horizon, Po E (SS) is the initial distribution, Pa. : S x A- + A(S) is the transition kernel, and RA, S x A - A ([0,, 1]) is the random rewards with E[RR, a]] (s) (H and {Ra ) are unknown to the learner.
The initial state 81 is drawn from the initial distribution Po- each step h, taking action an in state 8n results in a next state 84+1 sampled from the transition kernel P. 8h, ax). ). A trajectory {(sh an, R2 (S), an HE is called an episode, and when the learner reaches the end of the episode, new episode begins.
policy π = ( πh) ) is a sequence decision rules Ta :S - A(A) for each step E [H]. The Q-value function of a policy at step h E [H] is defined as
Q% a) == E, Σ Rs
(ss) (a(ss,aa)))s h'=h
8, an = a]
and it represents the expected reward obtained by choosing action a in state at step h and choosing the subsequent actions according to the policy æ. The value function of æ at step h is defined as
V (s)
Fr [ (8, (s))))
2

---

Published as a conference paper at ICLR 2026
and it represents the expected reward obtained by choosing actions according to the policy æ starting in state at step h. We also define V/O := (V'" The optimal Q-value function, optimal
value function defined as
(%(s, a) sup (s), (i((s sup VT
Vo = sup Vo
Throughout the paper, we do not assume that the optimal action or policy is unique.
Pure exploration under the fixed budget setting, In pure exploration under the fixed budget setting, the goal is to identify an optimal policy π (or near-optimal) based on a limited interaction budget. Specifically, the learner is allowed to execute total of B episodes and must return a single policy से at the end. The performance measured by the simple regret, which is defined as
V0
policy í is called E-good if Vi- VØ E. E. In this paper, we propose an algorithm and prove their performance guarantee by showing some instance- destance-eependet upper bounds of the failure probability
P(Vo Vo E).
Instance-dependee quantities. need the notion of suboptimality gaps defined as
To capture the instance-dependdet complexity of the problem, we
(s) (s) (s) (i( max (s, (s,
For our analysis, also denote
an)s,),,
(s, < (s)
an(s,a)
an)),a)).
if a) Vř and a' is the second best action,
(s)
if (s, < max. (7 (s, a')
(s)sa)
(s,
if QT, = max. Q7, a') and is the second best action with respect to
Thus, if the optimal action in E S step is unique, Án (8, a) > 0 for all A. In contrast, if there are multiple optimal actions in E S at step h, (n a) = 0 for all optimal actions a. Similar results hold for (s, a) as well.
In MDP, the probability of reaching each state or action is important. Let π be policy, E SS,a E h [ Z C 8 A, use the following notations:
(s) Pa (Sh s],
W (s, a) Px [sh s,an a).
w P. an) E 2).
(s) = sup F (s) sup W. (s,a), a),
(2) = sup w (2).
We refer to w.. (-) as the occupancy measure and Wx(+) as the reachability. Using these notions, we define the controllability of MDP at step h as
No (8)
C = sup
(s(s)*
(=)
Then, we have
(x((s)
Σ sup wx((s)
1 = sup
w5((s) < C₁ sup Σ
S.
Wh(()
(.Wa & Wx(s)
(.W.()))
(
We can see that C₁ if (s) 0 or 1 for any state i.e. the learner can reach 8/ with probability by some policy for any reachable state s. On the other hand, C₁ = S if (s) = (s) > 0 for any state by varying policy and all states are reachable. Therefore, intuitively, a larger C indicates that the MDP is more difficult to control at step h.
S, any policy i.e. the learner cannot control the occupancy measure
3

---

Published as a conference paper at ICLR 2026
3 THE BREA ALGORITHM
There are inherent difficulties in achieving instance-dependent e-uniform guarantee for fixed budget setting. First, while it is relatively straightforward to analyze algorithms in the fixed confidence setting using concentration bounds such as Hoeffding or Bernstein bound with a prespecified confidence level is much more challenging in the fixed budget setting, where neither the confidence level nor the accuracy level e is known in advance. Second, whereas the fixed-confidence setting typically allows for potentially excessive number of samples before termination (depending on the confidence level), the fixed-budget setting strictly limits the algorithm to a finite number of samples. Third, it is hard simply convert the fxxedcoofidennc algorithms since it requires the knowledge of nontrivial pistance-dependee terms. Even if it is possible, the conversion of fixed-confidence algorithm would require not only the budget but also one of the confidence 8 and the accuracy &. Also, theoretical guarantee of this conversion would only applies to prespecified e (or 8), which is much weaker than e-uniform guarantee. In this section, we present how we design and analyze our algorithm to overcome the aforemmeniooee difficulties.
At step each state can be treated as bandit problem, where the expected reward of each action a is given by Q% (s, a). If we aim to learn the exact optimal policy maximizing Q7, (s, a), we need to sample trajectories 1/+11 uh+ HH d generated under the optimal policy [" 1- which unknown. Fortunately, since our goal is to learn an approximately optimal policy, the following proposition shows that it suffices to use suitably accurate policy {ft } =h-=++1 for sampling in order to learn f...
Proposition 1. Waggemaker et al. 2022 Lemma B.1) Assume that some deterministic policy î satisfies A (s, (s)) S for any h' S h S H and any s S. Then, for any policy x',
Σ E (s) (V)(s) - v)())
Σ sup Σ (s))ss(()). A=M
Note that (s, a) depends only the future policies (*x ) = implying that must determine them before learning (s). By this observation, our learning proceeds backward from H to 1.
we assume that the hypothesis of the previous proposition holds with = and e (s) ==
C, W. then the proposition says
H
VO
V
S
sup
Wh (s))n(s)
hml
11
sup
(s)
(s
h=1
H
Σ
(definition of C₁))
h=1
=
Therefore, we design our algorithm to identify a ((,,HWW,))) )-good action for each relevant state s. The precise definition of "relevant state" will be given in the analysis. We again emphasize that is not input algorithm and can be chosen arbitrarily for the purpose of analysis. Our algorithm consists of two key components: estimating the reachability (s)() and eliminating actions. We introduce the following notation, which will be used in the statements of upcoming results.
1og(2) > -0.6321
EB == (1+
c(B)
denotes an error threshold that depends on the budget B. The factor
CL2E ((poly(S,
is formally defined in Appendix equation
We denote CLAE (B) =SH²c(B).
4

---

Published as a conference paper at ICLR 2026
Algorithm Fixed Budget Learn to Explore (FB-L2E)
1: function FB-L2E(A' C 8 x A, step h, budget B3)
2: if [ = 0 then
3: return {(0, 0)0
4: end
5: J <- [0.6321 logg + cB)
los(2) )1 (c(B) is defined in Appendix
6:
for
j to do Lj t 2'-3, 5 8, 4 8SAH
7:
0.6321 by log 1og(88
8:
K₃ + SAHH,,AHH, (Kg defined in Appendix
9:
N2 < K//(4|X1 2
10:
(K 11;) + FINDEXPLORABLLSETSQ: K,,
X' X' \23
12: end for
13: return {(X, NJ))
14: end function
15:
16: function FINDEXPLORABLESETSS/ S S x A, step h, confidence 6, epochs K, samples N)
17:
(8, < (s.a) E X, else 0)
18:
a(s, 0, 0. 0.
19:
for = ===10 K do
20:
StrongEuler defined in Simchowitz and Jamieson (2019
Run STRONGEULER(0) on reward ry, to get trajectory {(s) a h)} and policy T (s ah) Ns a + 11 IU {
23:
if (6 a 2 N. (sh a E X and (o a then
+ U
25:
(s, + lf (s, E V. else j 2 x
26:
27:
Restart STRONGEULER())
28:
end if end for
29:
return y1 11
31:
end function
3.1 REACHABILITY ESTIMATION
The first part of our algorithm is greatly influenced by Wagenmaker et al. (2022) Through the first part, we estimate the reachability (s) each state at step h. To this end, we execute fixed-budget reward-free exploration. One notable benefit of reward-free exploration is that it only needs to be run once, after which the collected data can be applied to a variety downstream reward
11, if (8', R/) (s, 1,)),
functions. More specifically, we reset the reward as (s a') = 0, otherwise.
where we arbitrarily fix an action and denote it by 1. With this reset reward, optimal policy maximizes the visitation probability of (s, 1) at step Therefore, V (s, (s). To approximate such optimal policy, we employ STRONGEULERR (Simchowitz and Jamieson, 2019).
More generally, the reachability (X') of any subset X' C A can be estimated the same manner. We formalize this in Algorithm [ which we refer to as FB-L2E, short for Fixed- -uddee Learn2Explore. is a careful adaptation Learn2Explore algorithm introduced in Wagenmakerr al. 2022), which itself is inspired by Zhang et al. (202T): Braiman and Tennenholtz (2003).
Algorithm satisfies the following guarantee:
Theorem 3.1. Consider running Algorithm 7 with B 2 cBB). Then, the following statements hold.
1. The total budget used at most B.
2. For any e 2 - with probability at least 1 exp (-ô)
eB
Crant
5

---

Published as a conference paper at ICLR 2026
(1) The reachability of each set X, satisfies
A 2-1 S (x( 22 for all i S ig = log2
2SH²
(2) The remaining elements, 8= X' 1 satisfy
Σ (s) 2SH²
sup
(s,a)EX
(3) Moreover, for any der if each policy in II, is executed A times, then every state- action pair (s, a) E X, is visited at least AN, times.
Here, the probability accounts for both the randomness in execution and resampling.
The proof of Theorem 3.1 is deferred to Appendix C
Remark 2. Theorem crucially relies the fact that STRONGEULER (Simchowitz and Jamieson 2019/ achieves a high probability regret bound with log dependence. However, when the target is X { similar results can be obtained by applying a boosting technique even if use other algorithms with worse dependence. Although we only present Algorithm 7 in the main text for the simplicity, the algorithm with boosting technique is described Appendix Algorithm 0
3.2 ACTION ELIMINATION
In the second part of our algorithm, we iteratively sample trajectories, compute empirical Q-function of state-action pairs, and eliminate suboptimal actions. For the purpose of efficient elimination, we employ multiple bandit algorithm, Successive Accepts and Rejects (SAR), proposed by Bubeck et al. (2013), and, for the first time, provide an e-correctness guarantee for this algorithm. By employing this algorithm to our main algorithm, we are able reduce the dependency on S compared applying its multi-armed bandit counterpart. For a more detailed explanation, see Appendix D Remark 27
Multiple bandit problem. Consider M instances of multi-armed bandit problems, each with K arms. Each arm i in instance yields stochastic rewards supported on [0, o). with mean (mm..
ordered such that Pm.1 2 ... 2 J...K. We denote each bandit-arm pair by (m, i). where m E [M] and E [K]. The objective is to identify good arm in each instance [M] under total budget of pulls.
We now define some notations. Let (n) denote the empirical mean reward of arm i in instance m after n pulls. Define the suboptimality gap as
Am,i
Pm,1
Mm,2.
if 1,
Um,1 Pm.á:
if E {2..... K).
We enumerate all gaps A over all (m, E [M] x [K] in increasing order as
( W ( I ... S {(MK)-
Let
g(E) == ((m, i) [M] [K] pm.1 um,i SE}
for any = > 0, and define the harmonic log term
MK Σ
log (MK) =
+
i
For each E [MK- 1), define
B- MK
mi BB M,K)
log(MK) MK + +1
The SAR algorithm (Bubeck al. 2013) is summarized in Algorithm 2 By leveraging the ranking of empirical gaps, SAR adaptively distributes the budget across bandit instances, solving the multiple bandit problem efficiently. We present theoretical guarantee for its ability to identify 8-good arms.

---

Published as a conference paper at ICLR 2026
Algorithm 2 Successive Accept and Reject (SAR) for the multiple bandit
1: input: Budget B
2: A < {(1, 1), .., (M, no <-
3: for k = 1 M K do
4:
7g f- n2. [, .M, K) (as defined in equation
5:
((m, Ag. pull (m,i) for n& Rk-1 times
6:
Vm, 1m arg (m.)em /
(Break ties arbitrarily)
7:
if 3m such that Im is the last active arm in m then
8:
Jm = Im (Accept)
9:
As+1 Ax {(m, 1m)] (Deactivate)
10:
else
(mis in) + arg max (E.. (Pmm.,,, (T2*) - (m.s(tss)) (Break ties arbitrarily)
11:
12:
AR+1 t Ax \ {(mx, is)) (Reject and deactivate)
13:
end if
14:
end for
Jm i for AMK {(m,i)
16:
return {mm, Jm) }m=1 Im=1
Theorem 3.2. If we run Algorithm with M,, then the total number of budget used is most
B and
P(3m E [M] Mm,1 J(m) > 2) R2 exp (- (-1236 (112802 log(M Σieln VE)-2) )
B MK
for any 2
The proof of Theorem 3.2 is deferred to Appendix D
3.3 OVERVIEW OF THE BREA ALGORITHM
We combine the two mechanisms described above to construct our main algorithm. The algorithm proceeds in backward manner steps h H, H 1,..., 1. the budget is devoted to estimating the reachability (s) for each state s, while the second half applies the SAR mechanism eliminate suboptimal actions. Although the logic by which our algorithm eliminates actions is entirely different, the structure of eliminating actions after reward-free exploration was also used the fxee--oofiidecc algorithm, MOCA (Wagenmaker et al. 2022).
At each step h, the first half of
In general MDPs, the stochasticity of the transition kernel prevents us from freely collecting arbitrary state-action samples. However, Theorem ensures that, with high probability, the policies stored during the reachability estimation phase yield sufficient samples for each relevant mate-action pair. Under this event, the SAR mechanism is expected to perform reliably. We now present our main theorem and its corollary; their proofs are provided in Appendix B
Theorem 3.3. If we run Algorithm with
B 2SH
1
B max
B ), 2SA= loga
}
then the total number of budget used is at most B. Moreover, for any 2 2SH2
P V/- VØ=
exp (-6)
eB
CT.E( 28H
+ exp (-ò
B E
H max C E.
W
Corollary addition the hypothesis Tf Theorem assume further that 2SH B min(ming, Ws(s), 2H min+ aak C.Wa(s) a}} and the optimal action in each state each
7

---

Published as a conference paper at ICLR 2026
Algorithm 3 Backward Reachability Estimation and Action elimination (BREA)
1: input: Budget B
2: B' <- 125H), <- [0.6321 l0 +
1og(2) o(13'
)
3: B"
B
4: for 240
H. 1 1 do
5: Zn +
6:
for s E S do {(2g 11 )} + 1)),, B*) (1 is an arbitrary action)
7:
if x ((s,1) for some j E then
8:
(s(() + 2 g-111 2n t 2,, U {s}
9:
end if
10:
end for
11:
for
i
1 to do
12:
Zno t {s Zn (s) = 2- A + Ime x A.
V(s A1. N(s, + T(s.a) 0. ao =, Q(s, a) +
14:
for k = to 2
do
n4 f- n4 ( |,ill A) (as defined in equation
16:
for (s E A₂ do
Tx(s,0) + |
Rerun each policy 11 for (3 a) - times for each time t = + to (s, do if (s, a) is visited at step then Take action and extend trajectory using (#N ( =h+1 N N(s, a) ((s +1
19:
20:
21:
22:
Q(s,a) + Q(s, a) Eneh (s
24:
end if end for
26:
(s, + ((. ((s(s) (s, (f > else 0 T( + T(8,a) + (a( end for
27:
28:
29:
if 3 state s with unique surviving pair (s, a) in Ag then *n(s) t a, Act1 e As (s)
30:
31:
else
32:
V(s,a) E Ak. (s, (a) (s,aa) (s) (s',a)) + arg (ag (s, (Break ties arbitrarily)
33:
34:
Ast1 < A& ((s',d'))
end if
36:
end for
37:
a(x) < for AI = ((s,
38:
end for
39: For each E S Zn, set (s) as any action
40:
end for
41:
return
step is unique. Then, we obtain a guarantee of the best policy identification, given by
(Vo - Vo > >)) S exp (-6
e*B
CLEE B
2SH
+ exp (-ô
H3 maxxe]H] E.es (n(s) EE)
LaeA an(5,a)-2)
3.3 we can derive the sample complexity required by BREA to identify an E-correct policy with probability at least 1 5, given by
Remark 4. From Theorem
Te. = θ (pol((S,A,H)
Σ H max CP hE(H]
Σ
1
log 8
Wh(s)
#ES
aEd
(s
Wx(3]
8

---

Published as a conference paper at ICLR 2026
The first term inside θ is lower-order term. The second term inside θ becomes EaEA (A(a)vs)z for multi-armed bandits (S H 1). This consistent with known results the bandit literature ((Even-Dar Dar et al.) 2006 Audibert et al. 2010; Karnin et al. (013)). It is also noteworthy that our sample complexity is deterministic while the sample complexity of PAC RL algorithm typically is guaranteed with probability least 1 8.
Remark 5. Our sample complexity involves H maxa, term, in contrast to the Ha Ex dependence that appear in PAC RL literature (Wagenmaker et al. 2022 Wagenmaker and Jamieson 2022 Tirinzoni et al. 2023)). This difference stems from the inherent difficulty of the fixed budget setting, where the algorithm does not know in advance how to distribute the budget across different h. similar issue regarding the dependency on S could be resolved by employing multiple bandit algorithm instead of a multi-armed bandit algorithm.
3.4 INCORPORATING TARGET ACCURACY
If an accuracy level is provided as input, modify Algorithm include third part and obtain a different form of probabilistic guarantee. While Algorithm alllccatss T parts, the modified algorithm assigns B to the first and the second part and assgins B to the last part.
1 budget to each of its two
In the third part, for each multiple-bandit instance Zno let (e) denote the number of pairs (s, a) E 2he such that (s, a) S (o) After the second part, we gather the last 9h (E) surviving pairs and perform additional refinement step.
Theoretical guarantees for this variant are presented in the next theorem. The full algorithm (Algo- rithm 5 and its analysis are provided in Appendix F
Theorem 3.4. (Informal) There exists a variant of Algoritim 3 that, when given sufficiently large budget B and an accuracy level 2 2SS2 as input. it uses at most budget B and satisfies the following:
=B poly A, H, log B)
P V/
VØ=
>
exp
-
+ exp
H3 maxxe[H] Exes Wh(s) - "EEesAn(ss wxlor) -22
e²B
+ exp
-
H max [OPT, (3:)
where OPT a)) E A: (s) E]..
derive the sample complexity required by the modified algorithu to identify an E-correct policy with probability at least 6, given by
Remark 6. From Theorem 3.4
H max hE(H]
OPTT,(30)
Te.5 Ō
(
poly(S, A.H.
H I18X
Σ Ws(s))
Σ aEA
+
log g
8
hE[H]
(An(s, v W.is)
E²
SES
It is interesting that even though the logic of action elimination is very different, this expression is closely aligned with the sample complexity
Ha Σ (PPT(()) NE
Te.8 CLOT(S)
+ H²
ΣΣ Wh(s)
Σ
log
KE[H]
aEd
An(s,a) V Wa(a)
of MOCA algorithm Wagenmaker et al.
2022 where CLOT poly(S, A, H, log 1,log] 1)-

---

Published as a conference paper at ICLR 2026
4 CONCLUSION
In this paper, we have explored the fixed-budget setting of the pure exploration MDP, which is surprisingly underexplored in RL theory. While our results establish the first fully instance-dependent guarantee in the fixed budget setting, these are just beginning. First, it would be great to see what kind of dependent acceleration can be proven MDP, which should be possible given that accelerated rates were possible in bandits as function of the number of good arms Katz- Samuels and Jamieson (2020); Zhao et al. (2023). Second, similarly, would interesting to explore what kind of data-poor regime guarantees are attainable again, such bounds are available in the bandit setting Katz-Samuels and Jamieson (2020); Zhao et al. (2023). Third, we believe the factor H in the sample complexity may be improved by leveraging puriance-dependee concentration bounds. Finally, it would be interesting to extend our setting to the function approximation setting.
REPRODUCIBILITY STATEMENT
We have carefully specified details of the algorithms presented this paper. Moreover, we clearly state all assumptions required for the theoretical guarantees of our methods. We believe that this level of detail ensures the reproducibility of our results.
ACKNOWLEDGEMENTS
This work was supported by the National Research Foundation Korea (NRF) grant funded by the Korea govermment (MSIT) NKS-2023-00219980,
10

---

Published as a conference paper at ICLR 2026
REFERENCES
Agarwal, A., Jiang, N., Kakade, S. M., and Sun, W. Reinforcement learning: Theory and algorithms. CS Dept., UW Seattle, Seattle, WA, USA, Tech. Rep, 2019.
Audibert, J.-Y., Bubeck, S., and Munos, R. Best Arm Identification in Multi-Armed Bandits. In Proceedings of the Conference on Learning Theory (COLT), 2010.
Brafman, R. I. and Tennenholtz, M. R-max general polynomial time algorithm for near- optimal reinforcement learning. J. Mach. Learn. Res., 3(null):213-231, Mar. 2003. ISSN 1532-4435. doi: 10.116//152243377652022
URL https::/doi.ooo
1162/
Bubeck, S., Munos, R., and Stoltz, G. Pure Exploration in Multi-armed Bandits Problems. In Proceedings of the International Conference on Algorithmic Learning Theory (ALT), pages 23-37, 2009.
Bubeck, S., Wang. T., and Viswanathan, N. Multiple Identifications Multi-Armed Bandits. In Proceedings of the International Conference Machine Learning (ICML), pages 258 258-265, 2013.
Chaudhuri, R. and Kalyanakrishnan, PAC identification of bandit arm relative to a reward quantile. In Proceedings of the AAAI Conference Artificial Intelligence (AAAI), pages 1777- 1783, 2017.
Dann, C., Marinov, T. V., Mohri, M., and Zimmert, J. Beyond value-function gaps: improved instance-dependen regret bounds for episodic reinforcement learning. In Proceedings of the 35th International Conference on Neural Information Processing Systems, NIPS '21, Red Hook, NY, USA, 2021. Curran Associates Inc. ISBN 9781713845393.
Even-dar, E., Mannor, S., and Mansour, Y. PAC bounds for multi-armed bandit and Markov decision processes. In Proceedings of the Conference on Learning Theory (COLT), pages 255-270, 2002.
Even-Dar, E., Mannor, S., and Mansour, Y. Action Elimination and Stopping Conditions for the Multi- Armed Bandit and Reinforcement Learning Problems. Journal of Machine Learning Research, 7: 1079-1105, 2006.
Garivier, A. and Kaufmann, E. Optimal best arm identification with fixed confidence. In Proceedings of the Conference on Learning Theory (COLT), pages 998-1027, 2016.
Jin, C., Allen-Zhu, Z., Bubeck, S., and Jordan, M. I. Is q-learning provably efficient? In Bengio, S., Wallach, H., Larochelle, H., Grauman, K.. Cesa-Bianchi, N., and Garnett, R., editors, Advances in Neural Information Processing Systems, volume 31. Curran Asso- ciates, Inc., 2018. URL htttts://ppoceeeeee
neuri wtt.pps.cppppppeee cc/paper files/paper)
2018 8/ 1ellee/.0 d3b1
Jin, C., Krishnamurthy, A., Simchowitz, M., and Yu, Reward-free exploration for reinforcement learning. In III, H. D. and Singh, A., editors, Proceedings of the 37th International Confer- ence on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pages 4870-4879. PMLR, 13-18 Jul 2020. URL lttpp::/ppocedding www..mmlr..err press///ss/ Din20d. html]
Kalyanakrishnan, S., Tewari, A., Auer, P., and Stone, P. PAC Subset Selection in Stochastic Multi- armed Bandits. Proceedings of the International Conference on Machine Learning (ICML), pages 655 025-662,77 2012.
Karnin, Z., Koren, T., and Somekh, O. Almost Optimal Exploration in Multi-Armed Bandits. In Proceedings of the International Conference on Machine Learning (ICML), pages 1238-1246. 2013.
Satz--amuels, J. and Jamieson, K. The True Sample Complexity of Identifying Good Arms. In Proceedings of the International Conference on Artificial Intelligence and Statistics (AISTATS), pages 1781-1791, 2020.
11

---

Published as a conference paper at ICLR 2026
Kearns, M. and Singh, S. Near-optimal reinforcement learning in polynomial time. Machine learning. 49:209-233 232, 2002.
Mannor, S. and Tsitsiklis, J. N. The sample complexity of exploration in the multi-armed bandit problem. J. Mach. Learn. Res., 5:623-648, Dec. 2004. ISSN 1532-4435.
Orabona, and Pal, D. Coin Betting and Parameter-Fres Online Learning. Advances Neural Information Processing Systems (NeurIPS), pages 577-585, 2016.
Simehowitz, M. and Jamieson, K. G. Non-asymptotic gap-dependent regret bounds for tabular mdps. Wallach, H., Larochelle, H., Beygelzimer, A., d'Alché-Bue, F., Fox, E., and Gar- nett, R., editors, Advances in Neural Information Processing Systems, volume 32. Curran Asso- ciates, Inc., 2019. URL httpstt:::/// http::///oooeeeeeeeeeccoe n cc/papr files/paper/ 201 0taia//eeeaaaaa22233aaeaedddddd htt.://ewe...caccccccccee-e.....
Tirinzoni, A., Al-Marjani, A., and Kaufmann, Near instance-optimal pac reinforcement learning for deterministic mdps. In Proceedings of the 36th International Conference on Neural Informa- tion Processing Systems, NIPS '22, Red Hook, NY, USA, 2022. Curran Associates Inc. ISBN 9781713871088
Tirinzoni, A., Al-Marjani, A., and Kaufmann, E. Optimistic pac reinforcement learning: the instance- dependent view. In Agrawal, S. and Orabona, F., editors, Proceedings of The 34th International Conference on Algorithmic Learning Theory, volume 201 of Proceedings of Machine Learning Research, pages 1460-14880 PMLR, 20 Feb-23 Feb 2023. URL httpt:t//ppcccee..nggs
m.r.press/v211.
12a. htm_
Wagenmaker, and Jamieson, K. Instance-dependent near-optimal policy identification in linear mdps via online experiment design. In Proceedings of the 36th International Conference on Neural Information Processing Systems, NIPS '22, Red Hook, NY, USA, 2022. Curran Associates Inc. ISBN 978197711777 1713871188.
Wagenmaker, A. J., Simchowitz, M., and Jamieson, K. Beyond regret: Instance-dependent pac reinforcement learning. In Loh, P.-L. and Raginsky, M., editors, Proceedings of Thirty Fifth Confer- ence Learning Theory, volume 178 of Proceedings of Machine Learning Research, pages 358-418. PMLR, 02-05 Jul 2022. URL /tEpp:://rroceednng wtw.ssss......p........m wagenmaker22a.1 html]
Zanette, A. and Brunskill, E. Tighter problem- pooblem-dependent regret bounds in reinforcement learning without domain knowledge using value function bounds. In Chaudhuri, K. and Salakhutdinov, R., editors, Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Reseurch, pages 7304-7312. PMLR, 09-15 Jun 2019. URL ptrr.eeeenggg...rrrrrss///////aa
html]
Zhang, Z., Du, S., and Ji, X. Near optimal reward- free reinforcement learning. In Meila, M. and Zhang. T., editors, Proceedings of the 38th International Conference Machine Learning, volume 139 of Proceedings of Machine Learning Research, pages 12402-12412, PMLR, 18-24 Jul 2021. URL htttps::/proceeeiingg ings. ml wtt..p.eess/111///eeeaaaa. ottppp//eeeccaaiaaaaaaaaaaaaaaaa
html
Zhao, Y., Stephens, C., Szepesvári, C., and Jun, K.-S. Revisiting simple regret: Fast rates for returning good arm. Proceedings of the International Conference on Machine Learning (ICML), 2023.
12


Reviews:
[{"review_id": "sps2364S3c", "reviewer": "Reviewer_HDZ3", "summary": "The paper studies fixed-budget pure exploration in reinforcement learning, where the goal is to identify a near-optimal policy using a limited number of environment interactions. The authors propose a new algorithm that achieves ε-uniform guarantee given budget B (clearly ε=ε(B)).  They also analyze the SAR algorithm in multi-bandit problems.", "questions": "Definition of W_h(s) in line 139: there is dangling a. I assume it is meant \\pi(s) instead of a. \nWhat is S in 148? Has it been defined earlier? I wasn't able to find it. \nIn line 186, why does epsilon_h(s) satisfy the conditions in Proposition 1?\nIn Theorem 3.1, who to interpret B>=c(B)? Does it mean: there exists \\hat{B} such that for every B>=\\hat{B}, ...", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "From practical perspective, budget is more meaningful and easier to set than epsilon. As a result, the authors study 'the right problem.' \nThe assumptions made are reasonable and aligned with similar works. \n\nI did not check the proofs, but the statements are clear and show 'what is promised.'", "weaknesses": "Some notation is weak, i.e., has loose ends. \n\nThe usual weakness for such a paper is the cliche: there are no experiments. I don't take this against the authors. I think no experiments is fine. \n\nThe MAB part comes across as an unnecessary material.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "bEoth1I0ip", "reviewer": "Reviewer_Fd9H", "summary": "This paper studies the problem of fixed-budget pure exploration in finite-horizon episodic Markov Decision Processes (MDPs). The objective is to identify a near-optimal policy given a predetermined, fixed budget of interactions, which contrasts with the more common fixed-confidence (PAC) setting where the error level $\\epsilon$ and failure rate $\\delta$ are provided as inputs.\n\nThe authors propose a new algorithm, BREA, which operates by working backward from the final step $H$. The algorithm integrates two main components: A fixed-budget reward-free exploration mechanism and an action elimination phase. The authors establish an instance-dependent, $\\epsilon$-uniform guarantee for this fixed-budget setting in MDPs. This guarantee upper bounds the probability of returning a $>\\epsilon$ suboptimal policy for all $\\epsilon$ above a budget-dependent threshold. As byproducts, the paper also provides $\\epsilon$-uniform guarantees for fixed-budget reward-free exploration and for the SAR multiple-bandit algorithm.", "questions": "1.  Could the authors elaborate on the $H^5$ dependence in Theorem 3.3? The paper attributes this to the algorithm's lack of foresight in distributing the budget across steps $h$. Is this $H^5$ term an artifact of the BREA algorithm's two-phase design, or do you believe it is a fundamental lower bound for any fixed-budget algorithm in this setting?\n2.  The variant algorithm in Section 3.4 seems to be the one that yields a sample complexity in Remark 6 most comparable to the MOCA algorithm. Why is this presented as a \"variant\" rather than the main result? If a user does have a target accuracy $\\epsilon$ in mind, should they use this variant over Algorithm 3?\n3.  The $\\epsilon$-uniform guarantee for the SAR algorithm (Theorem 3.2) is presented as a contribution of independent interest. How does the resulting bound compare to existing non-$\\epsilon$-uniform fixed-budget guarantees for the multiple-bandit problem?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The paper addresses the fixed-budget pure exploration problem in MDPs, a practical setting that has received little attention in RL theory.\n2. The introduction provides a clear argument for the merits of the fixed-budget setting over the standard fixed-confidence setting.\n3. The paper introduces the $\\epsilon$-uniform guarantee, a new analytical approach for this problem. The new analysis for the SAR algorithm and the fixed-budget reward-free exploration mechanism are also solid contributions.\n4. The BREA algorithm's design, which separates reachability estimation from action elimination, is logical and well-explained.", "weaknesses": "1. The most significant weakness is the $H^5$ factor in the sample complexity of the main result in Theorem 3.3. This is substantially worse than the $H^4$ dependence often seen in related PAC RL literature. The authors acknowledge this, but it remains a major limitation of the paper's primary result.\n2. The paper introduces a variant algorithm in Section 3.4 that achieves a more comparable sample complexity to prior work (like MOCA). However, this theorem is stated informally, and the algorithm details are deferred to the appendix. This makes the paper's strongest result less clear and accessible.\n3. The paper is highly technical, which makes it challenging to parse. Key components and definitions being in the appendix add to this difficulty.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "aNBlQ5peBw", "reviewer": "Reviewer_Hors", "summary": "The paper proposes a novel algorithm called BREA for reward-free exploration of Markov decision processes in the fixed-budget setting. Concretely, the authors show that the probability of the proposed algorithm of failing to achieve epsilon-accuracy is inversely proportional to the suboptimality gaps and epsilon.", "questions": "In the expression for \\epsilon_B on page 4, what is c(B)?\n\nThe idea of rewarding specific state-action pairs is similar to active coverage (Al Majrani et al., COLT 2023), did you explore this connection?\n\nIn Remark 4 the sample complexity \\tau depends on C_L2E(B/(2SH)), which in turn depends on B. Should not \\tau be independent of B?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "To the best of my knowledge, the fixed-budget analysis of the proposed exploration algorithm is novel and correct, though I did not carefully check the proofs.", "weaknesses": "My main concern about the paper is conceptual. Fixed-budget algorithms usually prove a result on the accuracy or regret at the end of learning, and the authors also do this. However, the authors also prove results on sample complexity, which seems backwards when the budget is fixed beforehand. To compute a budget based on the sample complexity, one would need prior knowledge of several problem-specific parameters, which goes against the contribution of needing only B as input. Several theorems state as a *result* that the total budget is at most B, which seems like a tautology.\n\nSeveral theoretical results are difficult to interpret since they include parameters hidden inside functions. It would be useful to include a qualitative comparison with the sample complexity of algorithms in the fixed-confidence setting.\n\nThough a minor point, I do not agree with some of the claimed benefits of the fixed-budget setting. Concretely, the fixed-confidence setting has a clearly defined stopping rule and the aim is to guarantee PAC-compliance of the returned policy, while analyzing the precise sample complexity. Hence the algorithm cannot use as many samples as possible (the number of samples is bounded by the sample complexity), and the quality of the returned policy is guaranteed by the PAC-condition.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "H96W1LgvyF", "reviewer": "Reviewer_81u1", "summary": "The paper introduces the fixed-budget pure-exploration setting for episodic MDPs, where the learner must identify a near-optimal policy using a pre-specified interaction budget without knowing $\\delta$ or $\\epsilon$ in advance. It proposes BREA (Backward Reachability Estimation and Action-elimination), the first algorithm with fully instance-dependent guarantees in this setting. The authors prove that BREA returns an -optimal policy with probability that decays exponentially in the budget and provides tight, instance-dependent sample-complexity bounds, subsuming multi-armed bandit results.", "questions": "1. While gap dependent bounds are characterization of the hardness of an MDP, there are many MDPs (such as mountain car/cartpole/atari) where the gaps are quite small but we can still get fast rates since we can also characterize the hardness of an MDP by looking at the optimal value function like in [1,2]. Could you also comment on whether we could get bounds that depend on the optimal value function?\n\n2. What are the difficulties in extending these results to setting with function approximation such as linear MDPs [3] or linear mixture MDPs [4].\n\n\n[1] Zanette, Andrea, and Emma Brunskill. \"Tighter problem-dependent regret bounds in reinforcement learning without domain knowledge using value function bounds.\" International Conference on Machine Learning. PMLR, 2019.\n\n[2] Ayoub, Alex, et al. \"Switching the loss reduces the cost in batch reinforcement learning.\" Forty-first International Conference on Machine Learning. 2024.\n\n[3] Jin, Chi, et al. \"Provably efficient reinforcement learning with linear function approximation.\" Mathematics of Operations Research 48.3 (2023): 1496-1521.\n\n[4] Ayoub, Alex, et al. \"Model-based reinforcement learning with value-targeted regression.\" International Conference on Machine Learning. PMLR, 2020.", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The problem the paper studies is important and the authors present the first algorithm to enjoy instance dependent bounds for such a setting. Being able to design algorithms that do not require knowledge of the confidence parameter $\\delta$ or the optimality parameter $\\epsilon$  to run the algorithms are more akin to how these algorithms would be used in practice. Furthermore, the author present novel analysis that extends the analysis for the popular SAR algorithm which may be of independent interest to communities who rely on such algorithms to solve problems of interest.", "weaknesses": "The main weakness of this papers lies in the fact that the paper considers RL without function approximation and it the computationally feasibility of the proposed algorithm. Specifically whether such ideas would scale to more complicated function approximation schemes or only hold when using the simpler tabular models considered in this work.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)