Minimax Optimal Reinforcement Learning with Quasi-Optimism
Authors: Harin Lee
Min-hwan Oh
Venue: ICLR 2025 Poster (2025)
Keywords: Reinforcement Learning
Tabular Reinforcement Learning
Regret Analysis
Primary area: reinforcement learning
TL;DR: We propose a simple and practical algorithm with the tightest minimax regret bound for tabular reinforcement learning.

Abstract: In our quest for a reinforcement learning (RL) algorithm that is both practical and provably optimal, we introduce EQO (Exploration via Quasi-Optimism). Unlike existing minimax optimal approaches, EQO avoids reliance on empirical variances and employs a simple bonus term proportional to the inverse of the state-action visit count. Central to EQO is the concept of *quasi-optimism*, where estimated values need not be fully optimistic, allowing for a simpler yet effective exploration strategy. The algorithm achieves the sharpest known regret bound for tabular RL under the mildest assumptions, proving that fast convergence can be attained with a practical and computationally efficient approach. Empirical evaluations demonstrate that EQO consistently outperforms existing algorithms in both regret performance and computational efficiency, providing the best of both theoretical soundness and practical effectiveness.

Published as a conference paper at ICLR 2025
MINIMAX OPTIMAL REINFORCEMENT LEARNING WITH QUASI-OPTIMISM
Harin Lee
Min-hwan Oh
Scoul National University harinboy@snu.c ac. ac.kr
Scoul National University minoh&smu.co ac.kr
ABSTRACT
In our quest for reinforcement learning (RL) algorithm that is both practical and provably optimal, we introduce EQO (Exploration via Quasi-Optimism) Unlike existing minimax optimal approaches, EQO avoids reliance on empirical variances and employs simple bonus term proportional to the inverse of the state-action visit count. Central to EQO is the concept of quasi-optiminne where estimated val- ues need not be fully optimistic, allowing for a simpler yet effective exploration strategy. The algorithm achieves the sharpest known regret bound for tabular RI. under the mildest assumptions, proving that fast convergence can be attained with a practical and computationally efficient approach. Empirical evaluations demon- strate that EQO consistently outperforms existing algorithms in both regret perfor- mance and computational efficiency, providing the best of both theoretical sound- ness and practical effectiveness.
INTRODUCTION
Reinforcement learning (RL) has seen substantial progress in its theoretical foundations, with nu-
merous algorithms achieving minimax optimality (Azar al.] 2017 Zanette & Brunskill] 2019 Dann et al., 2019 Zhang et al. 2020 Li et al. Zhang et al. 202 la 2024). These algorithms are often lauded for providing strong regret bounds, theoretically ensuring their provable optimality in worst-case scenarios. However, despite these guarantees, an important question remains: Can we truly claim that we can solve tabular reinforcement learning problems practically well? By "solving reinforcement learning practically well," we expect these theoretically sound and optimal algorithms to deliver both favorable theoretical and empirical performance
Although provably efficient RL algorithms offer regret bounds that nearly optimal (up to log- arithmic or constant factors), they are often designed to handle worst-case scenarios. This focus on worst-case outcomes leads to overly conservative behavior, these algorithms must construct bonus terms to guarantee optimism under uncertainty. Consequently, they may suffer from practical inefficiencies in more typical scenarios where worst-case conditions may rarely arise.
Empirical evaluations of these minimax optimal algorithms frequently reveal their shortcomings in practice (see Section 5). In fact, many minimax optimal algorithms often underperform compared to algorithms with sub-optimal theoretical guarantees, such as UCRL2 (Jaksch et al.) 2010). This suggests that the pursuit of provable optimality may come at the expense of practical performance. This prompts the question: Is this seeming tradeoff between provable optimality and practicality in- herent? Or, can we design an algorithm that ottains both provable optimality and superior practical performance simultaneously?
To address this, we argue that fundamental shift is needed in the design of provable RL algorithms. The prevailing reliance on empirical variances to construct worst-case confidence bounds- tech-
'If one questions the practical relevance of tabular RL methods given the advancements in function approx- imation (Jin et al. 2020 He et al. 2023 |023 Agarwal et al. (2023), is important to recognize that many real-world environments remain inherently tabular, lacking feature representations for generalization. In such cases, effi- cient and practical tabular RL algorithms are not only relevant but essential. Furthermore, even when function approximation is feasible, tabular methods can still play a crucial role. For instance, state-space dependence
may persist even under linear function approximation (T.ce & Oh 2024 (wang & Ohl 2023)

---

Published as a conference paper at ICLR 2025
nique employed by all minimax optimal algorithms (Azar et al. 2017 Zanette & Brunskill] 2019 Dann et al. 2019; Zhang et al.) 2021a) (see Table I
may no longer be the only viable or practical approach. Instead, we propose new methodologies that, while practical, can still be proven efficient to overcome this significant limitation.
In this work, introduce tabular reinforcement learning algorithm, EQO, which stands for Ex- Unlike existing minimax-optima. algorithms, EQO does not rely on empirical variances. While it employs bonus term for exploration, EQO stands out for its simplic- ity and practicality. The bonus term is proportional to the inverse of the state-action visit count, avoiding the dependence on empirical variances that previous approaches rely on.
ploration via
On the theoretical side, we demonstrate that our proposed algorithm EQO, despite its algorithmic simplicity, achieves the sharpest known regret bound for tabular reinforcement learning. More im- portantly, this crucial milestone is attained under the mildest assumptions (see Section 4.1) Thus, our results establish that the fastest convergence to optimality (the sharpest regret) can be achieved by simple and practical algorithm in the broadest (the weakest assumptions) problem settings.
To complement-not as tradeoff-the theoretical merit, we show that EQO empirically outperforms existing provably efficient algorithms, including previous minimax optimal algorithms. The prac- tical superiority is demonstrated both in terms of regret performance in numerical experiments and computational efficiency. Overall, EQO achieves both minimax optimal regret bounds and superior empirical performance, offering a promising new approach that balances theoretical soundness with practical efficiency.
Our main contributions are summarized as follows:
We propose reinforcement learning algorithm, EQO (Algorithm which introduces a dis- tinct exploration strategy. While previous minimax optimal algorithms rely on empirical- variance- based bonus terms, EQO employs simpler bonus term of the form c/N(s, (s,a), where с is constant and (sss, a) is the visit count of the state-action pair (s. a). This straightforward yet effective approach reduces computational complexity while maintain- ing robust exploration, making EQO both practical and theoretically sound. Additionally, this simplicity allows for convenient control of the algorithm through single parameter, making it particularly advantageous in practice where parameter tuning is essential.
Our algorithm achieves the tightest regret bound in the literature for tabular reinforcement learning. Even compared to the state-of-the-art bounds by Zhang et al. (2021a), EQO pro- vides sharper logarithmic factors, establishing it as the algorithm with the most efficient regret bound to date. Our novel analysis introduces the concept of quasi-optimism (see Section 4.4.2p, where estimated values need not be fully optimistic This relaxation simpli- fies the bonus term and simultaneously controls the amount of underestimation, ultimately leading sharper regret bound.
A key strength of our approach is that it operates under weaker assumptions than the pre- vious assumptions in the existing literature, making it applicable to broader range of problems (see Section 4.1 While prior work assumes bounded returns for every episode, we relax this condition require only the value function (i.c.. the expected return) to be bounded. This relaxation broadens the applicability of our algorithm.
We show that EQO enjoys tight sample complexity bounds in terms of mistake-style PAC guarantees and best-policy identification tasks (see Section 2.1 for detailed definitions). This further highlights our proposed algorithm's robust performance.
We perform numerical experiments that demonstrate that EQO empirically outperforms ex- isting provably efficient algorithms, including prior minimax -ptimmal approaches. The su- periority of EQO evident both in its regret performance and computational efficiency, showcasing its ability to attain theoretical guarantees with practical performance.
By fully optimistic, we refer to the conventional UCB-type estimates that lie above the optimal value with high probability. See the distinction with new quasi-optimism in Section 4.4.2
2

---

Published as a conference paper at ICLR 2025
Table 1: Comparison of minimax optimal algorithms for tabular reinforcement learning under the hime-homogeneou setting. Constant and logarithmic factors are omitted. The Empirical Variance column indicates whether the algorithm requires empirical variance. The Boundedness column shows the quantity on which the boundedness assumptions are imposed, where bound on "Reward" and bounds on "Return" and "Value" are H.
Empirical Variance
Paper
Regret Bound
Boundedness
Azar et al. 2017)
HVSAK 11 VISK
Required
Reward
Zanette & Brunskill
2019
HVSAK H25S)AA(HH+VS)
Required
Return
Dann al. 2019
II 112
Required
Reward
Zhang et al. (201aa)
HVSAK HSA
Required
Return
This work
IVSAK AISAA
Not required
Value
* Our regret bound is the sharpest with more improved logarithmic factors than that of Zhang et al. (22
Bounded reward is the strongest assumption; bounded return is weaker than bounded reward: our bounded value assumption is the weakest among the three conditions (see the discussion Section 4.1
1.1 RELATED WORK
There has been substantial progress in RL theory over the past decade, with numerous algorithms advancing our understanding of regret minimization and sample complexity (Jaksch et al.) 2010
Osband & Roy 2014 Azar al., 2017 Dann al. 2017, Agrawal & Jia 2017|[0uaa
et al.
Jin et al. 2018 Osband et al. 2019, Russo 2019; Zhang et al. [020 (022 and some recent
lines of work focusing on gap-dependent bounds (Simchowitz & Jamieson 2019 Dann al. 2021
Wagenmaker et al., 2022, Tirinzoni et al.) 2022 Wagenmaker & Jamieson, 2022). In the remainder
of this section, we focus on comparisons with more closely related methods and techniques.
Regret-Minimizing Algorithms for Tabular RL. In episodic finite-horizon reinforcement learn- ing, the known regret lower bound is Q(H VSAK) (Jaksch et al. [0100] Domingues et al. 2021 The first result to achieve a matching upper bound is by Azar et al. (017). Their algorithm, UCEVI-BF, adopts the optimism in face of uncertainty (OFU) principle by adding an optimistic bonus during the estimation. For the sharper regret bound, they use Bernstein-Freedman type concentration inequality and design bonus term that utilizes the empirical variance of the esti- mated values at the next time step. Zanntte & Brunskill] (2019) show that by estimating both upper and lower bounds of the value function, their algorithm automatically adapts to the hardness of the problem without requiring prior knowledge. ZZhang et al. (2021a) improve the previous analysis and reduce the non-leading term to O(H5² A), achieving the regret bound that is independent of the lengths of the episodes when the maximum return per episode is rescaled to 1.
Time-Inhomen hoane--nhomogeeeuuss Setting. There has also been increasing number of works that focus on time-inhomosee mmme--nnoooggccouss MDPs, which have different transition probabilities and rewards at each time efficient model-free algorithm, which has space complexity of of S2 A) (Strehl et al., 2006). Jiin et al. (2018) propose a variant of Q-learning with a bonus similar to UCBVI DOVI-BE BF and show that this model-free algorithm achieves O(vK) regret. How- ever, their regret bound is worse than the lower bound by a factor of VH. This additional factor is removed by Zhang et al. (2020), achieving the minimax regret bound for the time-inhenn ineeeiinoooooouuss setting with a model-free a algorithm for the first time. [i et al. (2021) further improve the non-leading term and achieve regret bound of 3/H / SAKK
step One active area of study is to design
6 SA). Foddlll-bassed algorithms, the non- leading terms are further optimized. Menard et al. (2211b) combine the Q-learning approach with momentum, achieving non-leading term of O(H*SA) Recent work by Zhang et al. (2024) further reduce it to i SA), resulting in the bound of 2 HK}) on the whole range
'The regret lower bound for the time-inhomogencous case is S2H3/22/SA (Domingues al. 2021), heing worse than the hime-homogencous case by factor of VH. Due to this sub-optimality, the time- inhomogeneous setting is often viewed a special case of the homogennggns setting with HS states.
3

---

Published as a conference paper at ICLR 2025
of K. Deviating from the algorithmic framework shared by these works, Tiapkin al. (2022) pro- pose a posterior-sampling algorithm and achieve the minimax bound without computing empirical
variances.
PAC Bounds. Dann & Brunskill (2015) present a PAC upper bound of Ö (2
and a lower bound of Q H² (A))) where their focus is on what later named as the mistake-style PAC bound. Dann et al. 2017 generalize the concept to uniform-PAC. which also implies a high-probability cumulative regret bound well. Dann et al. (2019) propose further generalized framework named Mistake- /POC, which encompasses uniform-PACe best-policy identification, and an anytime cumu- lative regret bound. Notably, their algorithm achieves the minimax PAC bounds for the first time. Other PAC tasks include best-policy identification (BPI) (Fiechter) 1994, Domingues et al. [021] Kaufmann et al. 202T), where the goal to return a policy whose sub-optimality small with high probability, and reward- fare-frree&a exploration (Kaufmann et al. [02 Ménard et al. (021a)). where the goal is similar to BPI, but the agent does not receive reward feedback while exploring.
6²
((L/N)-bomts Exploration. To the best of our knowledge, our algorithm is the first to use an exploration bonus of the form e/N for the reinforcement learning setting and attain regret guaran- tees. In the multi-armed bandit setting, (Simchi-Levi et al. (2023) 2024) utilize a similar bonus term, but the underlying motivations and derivations differ significantly. Their focus on controlling the tail probability of regret-that that is, minimizing the probability of observing large regret. Their bonus term arises from Hoeffding's inequality with a specific failure probability. In contrast, our work is aimed at developing a practical algorithm for tabular reinforcement learning. Our bonus term stems from a distinct context-decouplingg the variance factors and visit counts that naturally arise in re- inforcement learning settings when applying Freedman's 's inequality (see Section 4.4). Importantly, Livc et al. (2023) 2024) do not appear to leverage Freedman's 's inequality, either directly or indirectly, their derivations. The distinction becomes evident when comparing the failure proba- bilities of the inequalities.
2 PRELIMINARIES
2.1 PROBLEM SETTING
We consider finite-horizon time-homogeneous Markov decision process (MDP) M (S, A, P.r, H), where S is the state space, A is the action space. P : S x A + AS is the state transition distribution, : A + R is the reward function, and H E N is the time horizon of an episode. We focus on tabular MDPs, where the cardinalities of the state and action spaces are finite and denoted by S = |8| and A == [A]. The agent and the environment interact for sequence of episodes. The interaction of the k-th episode begins with the enviromment providing an initial state, of E S. For time steps h- 1, ...., Ht, the agent chooses an action o A, then receives a random reward R2 E IR and the next state s E S from the environment. The mean of the random re- ward is r(st, a and the next state is independently sampled from P(- I af.). These probability distributions are unknown to the agent. The goal of the agent is to maximize the total rewards.
A policy is a sequence of H functions π = { with Tr : S - A for all h. An agent following policy chooses action a (s) at time step h when the current state is 8. We define the value function of policy π time step h as (s) = Ex(- E/=m ((ss),a)]] where (x(--=-==) denotes the expectation over (sy, = 8, uh...... 88,, an,, 88+11 with aj = n ()(3)) and 8j+1 P(-ss,, a,) for j = h...., H. Similarly, we define the action-value function as (s,s, a) Ex(-19)=s.0,== E az)] We set 1 = 0 for all π and 8 E S. x is the optimal policy, which chooses the action that maximizes the expected return at every time step, and it holds that V/T" (+) = sup, (s) for all = I...., H and s E S. We denote V by Vū and call it the optimal value function. The regret of policy π is defined as (s1 (s1). The agent's 's goal to find policies that minimize cumulative regret for given MDP. The cumulative regret over K
episodes is defined as:
K Regret(K) Σ
(VI(()) (ot)).
1=1
4

---

bonuses used in prior al- Published as a conference paper at ICLR 2025
Algorithm 1: EQO (Exploration via Quasi-Optinism)
Input: {c* 1.00
for k = 1,2, K do
foreach (s, 0, E S x
A
do
()) + == k=
1((5) an) = as;
(*, - x²(s.a)
Liml h=1 R2 (1) a/)) = (s,
H
(* + (=,a, 2i=1 h= 1((h)) oi s/+1)
(8) 50;
for h H1, -.,...,,, do
foreach (s.a) E x Aoo
6" (² (s,N*(
min (s, (b, (t, H}
if (s) >
(s) -
10
H
if N =
(s) + a 0 a) for all s S;
11
12
(s) argmax Q (s,a) for all S;
Execute n² and obtain 7 (5) at nb, si a R s s442):
13
In addition to regret, another important measure of performance is the PAC (probably approximately correct) bound (Kakade 2003), also referred to as sample complexity. This measure focuses on obtaining policy (after sufficient exploration) whose regret is no more than with probability at least 1 - 6, for given values of e > 0 and 8 E (0, 1]. A policy ı said to e-optimal if regret satisfies (s1) VTT (s1) S We evaluate two different tasks using PAC bounds: (i) the mistake- style PAC, which aims to minimize the number of episodes in which the agent exccutes a policy that not E-optimal, and (ii) best-policy identification, whose objective is return c-optimal policy within the fewest possible episodes.
2.2 NOTATIONS
(I. is the set of natural numbers. For N N, we define [M] := (.,..,,N, 1 is the indicator function that takes the value 1 when E is true and 0 otherwise. For any function S + and a state-action pair (s, a) E S A, we denote the mean of V under the probability For any other function P S x
distribution P(-|s, a) by aV) = Eves P(s"|s,a)Vis
variance of V under P(-ss, a) by Eves a))) in the same manner. We denote the == P(s'ls, (V PV(s, a)) A tuple (31, 01, Ri, SH aH, RH, 1H+1) generated by single episode of interaction is called trajectory. Let 7 be the trajectory of the k-th episode. For h [H]. we also define the partial trajectory as T == (sf af R ........ (r% be the o-algebra generated by the agent-enviromment interactions up to the action at: taken at the h-th time step of the k-th episode. For convenience, we define Fk as ((r')
A R define (V)
......., s a.) For all E [H] and N, let Ft = ((T')) U
ALGORITHM: EQO
We introduce our algorithm, Exploration via Quasi-Optimist (EQO), which presents a distinct ap- proach to bonus construction compared to prior optimism-based methods. While the framework of our algorithm shares some structural similarities with UCBVI (Azar et al. (017)). which has been widely adopted by several subsequent works (Zanette & Brunskill 2019 Dann et al. 2019 Zhang ct al. aa. EQO diverges significantly in its exploration strategy. The key novelty lies in its bonus term, which does not rely empirical variances, unlike the previous methods. Instead, EQO takes a sequence of real numbers {c as input, and the bonus for a state-action pair (s, a) E S x A in episode & is simply cg/N*(s. a), where N (s, a) is the visit count of (s, a) up to the previous episode. This simplicity stands in contrast to the empirical-variance-boo
5

---

Published as a conference paper at ICLR 2025
gorithms, demonstrating that empirical variance (and UCB approaches based on estimated variance) is not necessary for achieving efficient exploration in our approach.
A notable advantage of our algorithm is its simplicity in practice. While many existing RL algo- rithms often involve multiple parameters with complex dependencies, our approach consolidates these into single parameter, Ck. making tuning much more straightforward
4
THEORETICAL GUARANTEES
4.1 ASSUMPTIONS
Before presenting our theoretical guarantees, we provide the regularity assumptions necessary for the analysis. We emphasize that our assumptions weaker than those in the previous RL literature.
Assumption 1 (Boundedness). 0 S (s) < H holds for all E S and h E [H), and 0 s R s H holds for all h E [H] and & E N.
Assumption (Adaptive random reward). E[R r(sh at) holds for all h [H] and k N.
Assumption I regularizes the scaling of the problem instances. The most widely used regularity assumption is that the random rewards lie within the interval [0, 1] for all time steps (Jaksch al.,
2010 Azar et al. 2017; Dann et al. 2019). A slightly generalized version assumes that the return, defined as the total reward of an episode, is bounded as 0 < > Rs < H, and that each random reward non-negative (Jiang & Agarwal 2018: Zanette Brunskill 2019 Zhang al.) 2021a). Such assumption allows non-uniform reward schemes. For instance, the agent may receive reward of H at exactly one time step and no rewards at the other time steps. We further relax this boundedness assumption by constraining only the optimal values V (s) to be within the interval [0, H), along with the conventional boundedness on the random rewards within [0, H. Since the value function is the expected return, our bounded value condition is weaker than the bounded return assumption (and hence, also weaker than the widely used uniform boundedness of rewards) used in the previous literature.
Assumption 2 allows martingale-style random rewards. Standard MDPs assume a fixed reward distribution for each state-action pair, where rewards are sampled independently of history and the next state. Some recent studies introduce joint probability distribution on the next state and the
reward, defined as p : S x A + ASS x R), so that (s4+1, i.i.d. p(sh, an) (Krishnamurthy et al., 2016, /Sutton 2018 We further weaken this assumption by requiring only that the mean of
the random reward equals r(s, a). allowing specific distributions to adapt to the history. Note that in Assumption 2 s is not part of Ft This fact allows dependence between s and R making our assumption more general.
4.2 REGRET BOUND
We now present the regret upper bounds enjoyed by our algorithm EQO (Algorithm D.
Theorem (Regret bound of EQO). Fix å E (0, 1]. Suppose the number of episodes, denoted by K, is known to the agent. Let max 1.4H /
(AH/KE,/(SAA,,,,, (Kt///(/AAAAA..... K)), where & log 2AHSA and 6
f2,K log(1 + K H/(SA)). If Algorithm is run with Ca = c.for all l E [K], then with probability at least 5, the cumulative regret of K episodes bounded as follows:
Regret(K) I 38H SSAKGl2K 256HS Al + l2,k),
where (_ = log(500ISA(log(eKKn)
When the number of episodes K is specified, Theorem I states that the input of Algorithm I {c k Je can be set as constant independent of k. making the algorithm even simpler. In case where K is unknown, it is possible to attain a regret bound that holds for all K E N by updating C doubling-trick styled fashion. Theorem 2 states the anytime regret bound result enjoyed by Algorithm Note that resetting the algorithm is not necessary, unlike the actual doubling trick.
"The theoretical results in Theorems and justify setting C₁ as k-independent constant, offering both
thcoretical and practical convenience.

---

antee in Zhang et al. a2221a). The second terms of the regret bounds are OH A), which implies that our algorithm matches the lower bound for 2 S A. This bound matches the previously best non-leading term in the momooeooggeeu setting by Zhang al. (2211)) even in the logarithmic factors. Therefore, our regret bounds are the tightest compared to all the previous results in the Published as a conference paper at ICLR 2025
Theorem 2 (Anytime regret bound of EQO). Fix ò (0. For any episode & E N, take Ck
where 222 = 2 22logg f1,x log 24HSA(1+ Dog, and f2 log(1 1 + (s)) If Algorittmm D is run with ck as defined above, then with probability at least - 8, the cumulative regret of K episodes for any K E N is bounded as follows:
max m k. 1.4H / / AS2
Regret( (K) - 75H /SKK,
256HS A + f2,k),
where 1,,x= = log(50HHAA((og(<eHH)))
Discussions Theorems and 2
We discuss the regret bounds of both Theorems | and 2 The first terms of the regret bounds are in O H v SAR), which matches the lower bound up to logarith- mic factors. In fact, the logarithmic factors of Theorems and 2 are O (VVlg HSA log K H
and log A.o K) log ()) respectively, which are even tighter than the state-of-the-art guar- oV
hime-homogeneous setting up constant factors. Furthermore, to the best of our knowledge, our sult is the first to prove that the minimax regret bound is achievable under the weakest boundedness assumption on the value function.
4.3 PAC BOUNDS
We demonstrate that by setting the parameters Cı: appropriately, C PAC bounds.
Theorem (Mistake-style PAC bound). Let s E (0, H] and (0, 1]. Suppose Algorithm is run with cæ 56Hf2 for all k E N, where & log o Then, with probability least 1 8, the number of episodes in which the algorithm executes policies that are not E-optimal is at most Ko.
where Ko ②(( SA + A log 4T)
In Appendix D we present (E, E)Q (Algorithm 2) which runs Algorithm with parameters spec- ified as in Theorem 3 then performs additional procedure to certify e-optimal policies. With this extension, our algorithm is capable of solving the BPI task with the same bound as the mistake- style PAC bounds.
with
Theorem 4 (Best-policy identification). Let e E (0, H] and E (0, 1]. Algorithm Provides an e-optimal policy within Ko episodes, where Kg takes the same value in Theorem
For < H/S, the bound Kg ((H'S )))="), which matches the lower bounds for both tasks (Domingues et al. (02T). For both tasks, our results exhibit the tightest non-leading term compared to the previous results. For detailed discussions and proofs of Theorems and refer to Appendix D
4.4 SKETCH OF REGRET ANALYSIS
In this subsection, we provide a sketch of proofs of Theorem and Theorem 2 For simplicity, we denote all logarithmic factors by É in this subsection. The full statements of the proposition and lemmas with specific logarithmic terms and their detailed proofs are presented in Appendix [C
We propose Proposition 1 that demonstrates the effect of the bonus terms the cumulative regret. In this proposition, we introduce an auxiliary sequence of positive real numbers {Ax 1 and set Ck -H///>x
Proposition 1. Let 1oc he be sequence of non non-increasing positive real numbers with A1 < 1. Suppose Algorithm| is run with e = 7HE/ X for all k: E N. Then, with probability least 5, the cumulative regret of K episodes for any K E N is bounded as follows:
K
K
88 HSA 16 AL
Regret( K) < 4H Σ
d +
AK
Am
7

---

Published as a conference paper at ICLR 2025
Proposition demonstrates that the cntioraatoonepllittatiiii trade-off can be balanced by the param- eter λg. The term Σ A represents the regret incurred due the estimation error, while the term proportional to 1/Ax represents the regret incurred from exploration. For example, if the values of {^&} are large, the algorithm runs with smaller bonuses. This reduces the regret caused by ex- cessive exploration, but the algorithm may exploit sub-optimal policies due to lack of information, contributing to a larger Σk=1 A term. Both Theorem and Theorem follow from Proposition by setting appropriate values for λς- For Theorem we set X2 min 5/ 1 SAE2 KK} for all E [ For l'heorem 2
we set X = min 11, AAAAA//AAAA /k2), where k₂ = 2 2loga kj. The proof of Proposition 1 sketched throughout the following subsections.
4.4.1 HIGH-PROBABILIN EVENT
We denote the high-probability event under which Proposition Tholds by &, E is defined as an inter- section of six high-probability events, including concentration events of transition model estimation and reward model estimation. Refer to Appendix [ for the specific events that constitute & and the proofs that the events happen with high probability.
Although our algorithm does not use empirical variances, all the concentration results in the analy- sis are based on Freedman's is inequality (Freedman) 1975). The following lemma is variant of the inequality that use frequently throughout the analysis. While the current presentation focuses i..d. sequences, it is also applicable to martingales, as shown in Lemma of Appendix F
Lemma 1. Let C > O be constant and {X,]e= be i.i.d. copies of a random variable X with X C. Then, for any x E (0, 1] and E 1,, , the following inequality holds for all N with probability at least 8:
T2
31 4C
C An 1og
1
X
Var(X)+
log
One advantage of this form is that the variance term and the 1/n term are isolated, whereas the previous Bernstein-type bound includes term of the form /Var /n. While the sum of the variances achieves a tight bound within the expectation, the 1/n terms must be summed according to actual visit counts. This discrepancy necessitates the use of multiple concentration inequalities, alternating between the expected and sampled trajectories when bounding the sum of / Var /n terms. However, Lemma D allows us to address the two factors independently. Refer to Appendix F for more details about Freedman's inequality and its derivatives we utilize.
4.4.2 QUASI-OPTIMISM
Optimism-based analysis begins by showing (*(s) > (s) for all 8, h. where the use of empirical variances plays a crucial role (Azar et al. 2017 Din et al. 2018 Zanette & Brunskill] 2019: Dann ct al. 2019; Zhang al. 202 2024). However, variances. In fact, our bonus term does not guarantee optimism or even probabilistic optimism. Instead, it guarantees what we name quasi-optimism, meaning that the estimated values are almost optimistic. Specifically, the estimated values need to be increased by constant amount to ensure they exceed the optimal values. In other words, the estimation may be less than the optimal value, but only by a bounded amount. We formally present our result in Lemma 2
bonus term does not contain any empirical
Lemma 2 (Quasi-optimism). Under E, it holds that for all S, h E [H [H
3 (x) + As H VT(().
We outline the main ideas behind quasi-optimism. Fix h [H] s S, and k N. For ease of presentation, we assume that the reward function is known and that V/ (s) < H. For a" == (s), we have Vi(()) = r(s, a²) )++ + PVA (s,a") by the Bellman equation and (A((s) > 0 r(s, a)) bx, a²) + pk (
(s, a²) by the definitions of V and Q Therefore, we obtain that
(x) - (s) - PVi+1 (8,a") 1$ (s. a²) - p'Vi
=bb"aaa") + (P 1 pt) (s, a*) (pc))**(VV (V V (s, (I)
12
8

---

Published as a conference paper at ICLR 2025
In the previous method of guarantecing full optimism, assumee I2 < 0 using mathematical induction and then faces the challenging task of fully bounding 1 by b"(s, In the proof of Lemma [ set slightly relaxed induction hypothesis. As a result, 12 may be greater than zero, while (s, a²) no longer needs to fully bound /T. The key to quasi-optimism is to allow underesti- mation of T1, while controlling the resulting increase in 12. We explain each concept in detail.
Applying Lemma Ito Vi+ (s') with s' ~ P(-ls, a*), we obtain the following inequality (Lemma
( P----
d Var(Vi+1)ss,d)) + 4H
3HL
as,")s
We set (s, we obtain a recurrence relation of
3HE (s,a") to compensate for the 1/N term, but leave the variance term. Then,
(s) - (i) - A Var(Vi++)(s,a") + PV - Vi+ta)s,a"), 4H
(2)
We use backward induction on h to obtain a closed-form bound for Vi (s) - (s), specifically, (s) - V22 (s) I (s) for some functions (W) To infer what W should look like, we consider the case where the recurrence term is based on P instead of pst If we had V
V (s) S A Var(VV;+) a======-=)))) + P(V V (+,+)(s,aa) where pk in Eq. 2 is replaced with P. by iteratively expanding the V h++ part, we observe that the expected sum of the variance terms along a trajectory serves as an upper bound for (s) (s). (s). that is, (s) S A E. Σj= Var(V az)]. This sum has non-trivial bound of H², and this fact has been frequently exploited to achieve better H -ddependencyy in the regret bound since since/Azar et al. (2017). However, it has not been used for showing optimism, and furthermore, this observation relies on the boundedness of returns (see, for example, Eq. (26) of Azar et al. (2017)) We derive a novel way of bounding the sum of variances without requiring such a condition, which is applicable to showing quasi mansi-optimism. We first present the following difference-tyy -tppe bound for the variance (Lemma 27
Var (ar(VVi)))ss a²) & (Vz)((())) - P(2HV - (Vi+t)")ss, (s,a")
Using this inequality and mathematical induction, one can show that the expected sum of variances bounded by 2 (s) (s), which is at most 1/2. Then, the recurrence relation with P instead of pk implies (s) - (s) < A (2HV (s)
(+))
Now, we deal with the original recurrence relation Eq. ( where technical approach is required to handle the dependence ps. Recall that we aim find functions (W, H that satisfy Vi (s)
VA (s) & (s) under Eq. Assuming induction hypothesis Vi V Vh+1 (s) S Wk w+1(s)
for all s E S, we bound pa (Vi+z - (s41) a" as follows:
p* "x+1)ss,a") S P&Wn+1(s,
(p+ P)Wn++ +
We that (s(ss) must bound not only the of the variance terms but also addi- tional error term (itt P)W a*). The demonstration above suggests setting W
# (c, ())) (s)) for some constants e₁ and c2. Then, since Wk41 is a function of Vi++1 applying Freedman's 's inequality the error term results in a Var(Vit+2)s, at --related term and a 1/N*(s, as) term. The 1/N term compensated by increasing (s, a²) and the variance term is merged into the variance term that is already present in the recurrence relation. Then, only PW d²) remains, and we apply the method of bounding the sum of variances explained car- lier. Through some technical calculations, we show that the induction argument becomes valid with C1 = 2 and C22 = 1/2. Then, we have (s) - V (s) & (s(s) I 2 A for all s, h, leading to Lemma 2 The full demonstration of the induction step is presented in Appendix C.1
3
4.4.3 BOUNDING THE CUMULATIVE REGRET
We bound Vi - VI=" (sf)) the amount of overestimation with respect to the true value function. Similarly to the previous section, we use Freedman's inequality and bound the amount of overesti- mation at single time step by the sum of variance term and a term proportional to 1/ /s, a)) We denote the latter by (s, a) = [* ( 111H + S1H. As in the previous section, the ex-
pected sum of the variance terms is bounded by X H. Therefore, the amount of overestimation is

---

Published as a conference paper at ICLR 2025
bounded by the sum of A H and the expected sum of 8* We define Us)) the sum of 3 along trajectory that follows x/ starting from state at time step h with appropriate clipping. Specifically, let U == for all E S, then define U (s) for H, H L...., itcratively as follows:
U (s) min (s, *s)) PU (s. (s)) H)
The next lemma states that the amount of overestimation is bounded by the sum H and U..
Lemma 3. Under &, V VE (s) S 2 (U) holds for all S, h E [H 11. and
k E.N.
By Em= 1/n log N. the sum 1/N* (s, a) is well-controlled when the sum is taken over the sampled trajectories. Using concentration results between the expected and sampled trajectories. we derive the following bound for the sum of Uf:
Lemma 4. Under E, holds that Σ
Uf S HSAC + AC for all K N.
The detailed proofs of Lemma 3 and Lemma 4 can be found in Appendix C.2 and Appendix respectively, Proposition D is proved by combining Lemmas
to
5
EXPERIMENTS
UCRL2
I
UCBVI-FF
EULER
I
ORLC
I
MVP
I
EQO (Ours)
x10
Riverswim S=30, H=120
X10
Riverswim $=40, H=160
12.0
15.0
Cunulative Regret
10.0
Cumulative aavve Regret
12.5
6.0
4.0
5.0
2.0
2.5
0.0
0.2
0.4
0.6
0.8
1.0
0.0
0.2
0.4
0.6
0.8
1.0
Episodes
1e5
Episodes
1e5
Figure 1: Cumulative regret under RiverSwim MDP with varying S and H.
We perform numerical experiments to compare the empirical performance of algorithms for tabu- lar reinforcement learning. We consider the standard MDP named RiverSwim (Strehl & Littman 2008 Osband al., 2013), which known be a challenging environment that requires strategic exploration. We compare our algorithm EQO with previous algorithms, UCRL2 (Jaksch et al. 2010), UCBVI-BF (Azar al.] 2017), EULER (Zanette Brunskill 2019). ORLC (Dann et al. (019), 99, and MVP (Zhang et al. 2021a) We run the algorithms on the RiverSwim MDP with various configura- tions of S and H. The results for
and = 40 are presented in Figure where we observe the superior performance of EQO. Additionally, Table Appendix G shows that our algorithm also takes less execution time. provide experiment details Appendix
CONCLUSION
Our algorithm EQO simultaneously achieves the minimax regret bound and demonstrates practical applicability. Our work introduces the concept of quasi-optimism, which relaxes the conventional optimism principle and plays a pivotal role in achieving both theoretical advancements and practical improvements. This fresh perspective offers new insights into obtaining minimax regret bounds, and we anticipate that the underlying idea will be transferable to a wide range of problem settings beyond tabular reinforcement learning, such model-free estimation general function approximation.
10

---

Published as a conference paper at ICLR 2025
REPRODUCIBILITY STATEMENT
We provide the complete proofs of the theoretical results presented in Section appendix, and the whole set of employed assumptions is clearly stated in Section 4.1 We also
4 throughout the
guarantee the reproducibility of the numerical experiments in Section ( and Appendices G
and H.2
by providing the source code with specific seeds as supplementary material.
ACKNOWLEDGEMENTS
This work was supported by the National Research Foundation of Korea (NRF) grant funded by the Korea government (MSIT) (No. RS-2022-NR07188 1853 and RS-2023-00222663) and by AI-Bio Research Grant through Seoul National University.
REFERENCES
Alekh Agarwal, Daniel Hsu, Satyen Kale, John Langford, Lihong Li, and Robert Schapire. Taming the monster: A fast and simple algorithm for contextual bandits. In International conference on machine learning, pp. 1638-1646. PMLR, 2014.
Alckh Agarwal, Yujia Jin, and Tong Zhang. Vogl: Towards optimal regret in model-free with nonlinear function approximation. In The Thirty Sixth Annual Conference on Learning Theory, pp. 987-1063. PMLR, 2023.
Shipra Agrawal and Randy Jia. Posterior sampling for reinforcement learning: worst-case regret bounds. In Advances in Neural Information Processing Systems, pp. 1184-1194, 2017.
Mohammad Gheshlaghi Azar, Ian Osband, and Rémi Munos. Minimax regret bounds for reinforce- ment learning. In International Conference on Machine Learning, pp. 263-272. PMLR, 2017.
M. G. Bellemare, Y. Naddaf, J. Veness, and M. Bowling. The arcade learning environment: An evaluation platform for general agents. Journal of Artificial Intelligence Research, 47:253-279, jun 2013.
Alina Beygelzimer, John Langford, Lihong Li, Lev Reyzin, and Robert Schapire. Contextual bandit algorithms with supervised learning guarantees. In Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statisties, pp. 19-26. JMLR Workshop and Conference Proceedings, 2011.
Liyu Chen, Mehdi Jafamia-Jahromi Rahul Jain, and Haipeng Luo. Implicit finite-horizon approx- imation and efficient optimal algorithms for stochastic shortest path. Advances in Neural Infor- mation Processing Systems,
2021.
Maxime Bhevalicr-Boisvert,, Bolun Dai, Mark Towers, Rodrigo de Lazcano, Lucas Willems, Salem Lahlou, Suman Pal, Pablo Samuel Castro, and Jordan Terry. Minigrid & miniworld: Modular & customizable reinforcement learning environments for goal-oriented tasks. CoRR,
abs/2306.138t 13831, 2023.
Christoph Dann and Emma Brunskill. Sample complexity of episodic fixed-horizon reinforcement learning. Advances Neural Information Processing Systems, 28, 2015.
Christoph Dann, Tor Lattimore, and Emma Brunskill. Unifying pac and regret: Uniform pac bounds for episodic reinforcement learning. In Advances in Neural Information Processing Systems, volume 30, pp. 5713-5723, 2017.
Christoph Dann, Lihong Li, Wei Wei, and Emma Brunskill. Policy certificates: Towards account- able reinforcement learning. In International Conference on Machine Learning, pp. 1507-1516. PMLR, 2019.
Christoph Dann, Teodor Vanislavov Marinov, Mehryar Mohri, and Julian Zimmert. Beyond value- function gaps: Improved instance-dependent regret bounds for episodic reinforcement learning. Advances in Neural Information Processing Systems, 34:1-12, 2021.
11

---

Published as a conference paper at ICLR 2025
Omar Darwiche Domingues, Pierre Ménard, Emilie Kaufmann, and Michal Valko. Episodic rein- forcement learning in finite mdps: Minimax lower bounds revisited. Algorithmic Learning Theory, pp. 378-598. PMLR, 2021.
Claude-Nicolas Fiechter. Efficient reinforcement learning. In Proceedings of the seventh anmual conference on Computational learning theory, pp. 88-97, 1994.
Dylan Foster and Alexander Rakhlin. Foundations of reinforcement learning and interactive deci- sion making. arXiv preprint urXiv:2312.16730 2023.
David A Freedman. On tail probabilities for martingales. the Annals of Probabilit,, pp- 100-118, 1975.
Jiafan He, Heyang Zhao, Dongruo Zhou, and Quanquan Gu. Nearly minimax optimal reinforcement learning for linear markov decision processes. In International Conference Machine Learning, pp. 12790-12822. PMLR, 2023.
Tachyun Hwang and Min-hwan Oh. Model-based reinforcement learning with multinomial logistic function approximation. In Proceedings of the AAAI conference artificial intelligence, vol- ume 37, pp. 7971-7979, 2023.
Thomas Jaksch, Ronald Ortner, and Peter Auer. Near-optimal regret bounds for reinforcement learning. Journal of Machine Learning Research, 11(,), 2010.
Nan Jiang and Alekh Agarwal. Open problem: The dependence of sample complexity lower bounds on planning horizon. In Conference On Learning Theory. pp. 3395-3398. PMLR, 2018.
Chi Jin, Zeyuan Allen-Zhu, Sebastien Bubeck, and Michael Jordan. Is q-learning provably ef- ficient? In Advances in Neural Information Processing Systems, volume 31, pp. 4868-4878, 2018.
Chi Jin, Zhuoran Yang, Zhaoran Wang, and Michael Jordan. Provably efficient reinforcement learning with linear function approximation. In Conference Learning Theory, pp. 2137-2143. PMLR, 2020.
Sham Machandranath Kakade. On the sample complexity reinforcement learning. University of London, University College London (United Kingdom), 2003.
Emilie Kaufmmann Pierre Ménard, Omar Darwiche Domingues, Anders Jonsson, Edouard Leurent, and Michal Valko. Adaptive reward-free exploration. In Algorithmic Learning Theory, pp. 865- 891. PMLR, 2021.
Akshay Krishnamurthy, Alekh Agarwal, and John Langford. Pac reinforcement learning with rich observations. Advances in Neural Information Processing Systems, 29:1840-188 18400,18...10 2016.
Cassidy Laidlaw, Stuart Russell, and Anca Dragan. Bridging rl theory and practice with the effective horizon. In NeurIPS, 2023.
Joongkyu Lee and Min-hwan Oh.
Demystifying linear MDPs and novel dynamics aggregation framework. In The Twelfth International Conference on Learning Representations, 2024.
Gen Li, Laixi Shi, Yuxin Chen, Yuantao Gu, and Yuejie Chi. Breaking the sample complexity barrier to regret-optimal model-free reinforcement learning. Advances Neural Information Processing Systems, 34:17762-177766 2021.
Marlos C. Machado, Marc G. Bellemare, Erik Talvitie, Joel Veness, Matthew Hausknecht, and Michael Bowling. Revisiting the arcade learning environment: Evaluation protocols and open problems for general agents. Journal of Artificial Intelligence Research, 61:523-562, 2018.
Pierre Ménard, Omar Darwiche Domingues, Anders Jonsson, Emilie Kaufmann, Edouard Leurent, and Michal Valko. Fast active learning for pure exploration reinforcement learning. In Inter- national Conference Machine Learning, pp. 7699-7608. PMLR, 2021a.
12

---

Published as a conference paper at ICLR 2025
Pierre Ménard, Omar Darwiche Domingues, Xuedong Shang, and Michal Valko. Ucb momen- tum q-learning: Correcting the bias without forgetting. In International Conference on Machine Learning. pp. 7609-7618. PMLR, 2021b.
lan Osband and Benjamin Van Roy. Model-based reinforcement learning and the eluder dimension.
In Advances in Neural Information Processing Systems, pp. 1466-1474, 2014.
Ian Osband, Daniel Russo, and Benjamin Van Roy. (more) efficient reinforcement learning via posterior sampling. Advances in Neural Information Processing Systems, 26, 2013.
Ian Osband, Benjamin Van Roy, and Zheng Wen. Generalization and exploration via randomized value functions. In International Conference on Machine Learning, pp. 2377-2386. PMLR, 2016.
Ian Osband, Benjamin Van Roy, Daniel J Russo, Zheng Wen, et al. Deep exploration via randomized value functions. Journal of Machine Learning Research, 20(124):1 62, 2019.
Yi Ouyang, Mukul Gagrani, Ashutosh Nayyar, and Rahul Jain. Learning unknown markov deci- sion processes: A thompson sampling approach. In Advances in Neural Information Processing Systems, pp. 1333- 1342, 2017.
Daniel Russo. Worst-case regret bounds for exploration via randomized value functions. Advances in Neural Information Processing Systems, 32, 2019.
David Simchi-Levi, Zeyu Zheng, and Feng Zhu. Stochastic multi-armed bandits: optimal trade-off among optimality, consistency, and tail risk. Advances in Neural Information Processing Systems, 19:36619-356339 2023.
David Simchi-Levi, Zeyu Zheng, and Feng Zhu, A simple and optimal policy design with safety against heavy-tailed risk for stochastic bandits. Management Science, 2024.
Max Simchowitz and Kevin G Jamieson. Non-asymptotic gap-dependent regret bounds for tabular mdps. Advances in Neural Information Processing Systems, 32, 2019.
Alexander L Strehl and Michael Littman. An analysis of model-based interval estimation for markov decision processes. Journal of Computer and System Sciences, (448):1309-1333 2008.
Alexander L Strehl, Lihong Li, Eric Wiewiora, John Langford, and Michael L Littman. Pac model- free reinforcement learning. In Proceedings of the 23rd international conference on Machine learning, pp. 881-888, 2006.
Richard S Sutton. Reinforcement learning: An introduction. A Bradford Book, 2018.
Daniil Tiapkin, Denis Belomestny, Eric Moulines, Alexey Naumov, Sergey Samsonov, Yunhao Tang, Michal Valko, and Pierre Ménard. From dirichlet to rubin: Optimistic exploration in without bonuses. In International Conference on Machine Learning, pp. 21380-21433 PMLR, 2022.
Andrea Tirinzoni, Aymen Al Marjani, and Emilie Kaufmann. Near instance-optimal pac reinforce- ment learning for deterministic mdps. Advances in neural information processing systems, 35: 8785-8798, 8798, 2022.
Andrew Wagenmaker and Kevin G Jamieson. Instance-dependent near-optimal policy identification in linear mdps via online experiment design. Advances in Neural Information Processing Systems, 35:5968-599 5981, 2022.
Andrew Wagenmaker, Max Simchowitz, and Kevin Jamieson. Beyond no regret: Instance- dependent pac reinforeement learning. In Conference on Learning Theory, pp. 358 418. PMLR, 2022.
Yunbei Xu and Assaf Zeevi. Upper counterfactual confidence bounds: a new optimism principle for contextual bandits. arXiv preprint 10XY::0077007766 2020.
Andrea Zanette and Emma Brunskill. Tighter learning without domain knowledge using value function bounds. In International Conference on Machine Learning, pp. 7304-7312. PMLR, 2019.
regret bounds in reinforcement
13

---

Published as a conference paper at ICLR 2025
Andrea Zanette, David Brandfonbrener, Emma Brunskill, Matteo Pirotta, and Alessandro Lazaric. Frequentist regret bounds for randomized least-squares value iteration. In International Confer- ence on Artificial Intelligence and Statistics, pp. 1954-1964. PMLR, 2020.
Zihan Zhang, Yuan Zhou, and Xiangyang Ji. Almost optimal model-free reinforcement learningvia reference-advantage decomposition. In Advances in Neural Information Processing Systems, vol- ume 33, pp.
2020.
Zihan Zhang, Xiangyang Ji, and Simon Du. Is reinforcement learning more difficult than bandits? near-optimal algorithm escaping the curse of horizon. In Conference on Learning Theory, pp- 4528 4531. PMLR, 2021a.
Zihan Zhang, Yuan Zhou, and Xiangyang Ji. Model-free reinforcement learning: from clipped pseudo-regret to sample complexity. In International Conference Machine Learning, pp- 12653-12662. PMLR, 2021b.
Zihan Zhang, Yuxin Chen, Jason D Lee, and Simon S Du. Settling the sample complexity of online reinforcement learning. In The Thirty Seventh Annual Conference on Learning Theory, pp. 5213- 5219. PMLR, 2024.
14

---

Published as a conference paper at ICLR 2025
Table 2: Table of notations
Notations for analysis
K
Number of episodes
Trajectory of k-tth episode, (s* añ, R ....... # o R #1
Partial trajectory of k-th episode up to h-th action selection, (sf, aj R ................................ s x/
F
o-algebra a ([r')/_] Ur/)
(s,
Visit count of (s,a) E x A up to k - 1-th episode
n (s,aa
Visit count of (s.a) E A up to h-th time step of k-th episode
min [H] ni (s ax) > (x ot)) H
(v))(
(&)() (V,+1 a)
when { is constant, + [loge k] when { changes at powers two
log 8
24H
log SAASA
log 50
log(1
+
&H
3A
log
12.5. 1 KH)
(s,
log 125.(11Hog NO (e.0))
8h (s,
11H& + 21 21H
N (s.a)
Au
(s,
(s)
min
(s, (9)) + PU (s, n. ()) HJ -
Notations exclusive for analysis of PAC bounds
l,,= ts,e
log(1 270 H ((2(
1 + log log log(()e/s)
(s),a)
8811
--3HSS,,,
(*,0,)
(s,,aa)
S8HF2 1
(*.0.))
(+)
min ( (8, (x)) + p* h+1 (8, n
(f] #11
(s) Tk
min (3th (f)) +
( Hf Of]
Set of k E [K] that satisfies (s+) > 2/8
Tk
Size of fx
TK TR
Set of k E [K] that satisfies (+) > E/ 8/16
Size of Tk
(=
Visit count of (s, a) E x for episodes in T x-1
n (s)
Visit count of (s, a) E for episodes 4. up to h-th time step of k-th episode
min(h [H] n ( af) > 2N (Nf. o H + 13
Appendix
A DEFINITIONS AND NOTATIONS
In this section, define additional concepts and notations for the analysis. We also provide Ta- ble 2 for notations defined in this paper. Conventional notations such as S, A, H. V or N are omitted. Notations that are used exclusively for the analysis of the PAC bounds are introduced in Appendix D.2
For the well-definedness of some statements in the analysis, we define 1/N*(s, a). PM (s'1s. a), and ak a) to be +00 when & a) 0 throughout this paper.
15

---

Published as a conference paper at ICLR 2025
For any sequence of H + functions V } h=1 with V1, S + R. we define An (V
- PV a). is similar to the Bellman error, but lacks the reward term. Therefore, for any policy π,, we have (s, (s)) V (s) - PV, L (s, (s)) r(s, (s)) for all h [H] and S.
We define n (s, a) to be the number of times the state-action pair (s, E S x A is visited up the h-th time step of the k-th episode, inclusively. To handle some exceptional cases more conveniently, define T7 to be the first time step h such that n (5) a > 2 (s af.)) occurs in the k-th episode for k N. In other words, 1/ is the first time step where the number of times state- action pair (s, a) E S x A is visited during the k-th episode exceeds N (8, a). We define 17 to be
H + 1 if there is no such time step. 1f is a stopping time with respect to { Jhm1 that is, we have {n/ = =h} E FK for all h [H + 1].
HH+
The input {= of Algorithm [ depends on sequence of non-increasing positive numbers, (A We mainly consider two cases where d is fixed for all k E N and Å changes only at powers of 2, i.e., A * λς-1 only when & 2m for some positive integer m. We let 4 denote the (maximum possible) number of distinct values in AI...., X2 Specifically, in the first case where A is fixed, we set la == for all E N. In the second case where A rarely changes, we set 4 = 1+ [log2 kj.
we define L = log 24HSAA l2 log(1+ 5 and E3,4 log 12SA(1+logkir kH) We overload the defini- tion of f,, to be function S A with (s,((s,)) == log 12SA(1+log N* Additionally, define f log SOHSA[1+Hg KH)" which serves an upper bound for max(ei, lg
Several different logarithmic terms appear in the analysis. For simplicity,
We rigorously define 3h and U introduced in Section 4.4.3
3 (s. := N*(s,a) ( (U + +21SSe,,(e,a)
Ax
Uk (8) the clipped expectation of the sum of 1eth under *² defined as follows:
U ( =00 0
(s) = min { (s, (+)) + PU (x))), for h E {M].
B HIGH-PROBABILITY EVENTS
In this section, we define the events required for the analysis and show that they hold with high probability. Throughout this section, assume 8 e (0, 1] and set 8' ;= 8/6, and let ) be fixed sequence of positive real numbers with A I 1 for all k.
Lemma 5. With probability at least 8'.
| (p*-P)Vi+H (s, a)) S
A (s,, Nx
3H11
4H
holds for all (s, a) ES he [H], and l e N.
Proof. Fix (s, a) E S x A. h E [fI]. and X E (0, 1]. Suppose {= is sequence of i.i.d. samples drawn from P( s. a). Let X, = Vi+1 (st)
( Then, X,| < H holds almost surely,
E[X,] = 0, and E[X?] = ( a). Applying Lemma 36 on { (x) with À = X X/3, the following inequality holds for all n E N with probability at least 8':
Xn Var(Vit,
3H 1
Σx.
X
log 8
4H
x
Dividing both sides by n yields
3H
Σ x, = (P. -
<
Var(Vitn)
log
4H
Xn
y
16

---

Published as a conference paper at ICLR 2025
where (s := Ei= 1[s, s is the empirical mean of P(s'|s, ss a) based on samples.
Repeating the same process for -X,, then taking the union bound over the two results, as well as over all (s, E S x A and h [H] yields that
[P. - PVVi+t <
X (s,(V) + 4H
3H 2HSA Xn log 8'
holds for all N. (8, E x A, and h E [H] with probability at least 8 Now, let X1 X2= ... be the subsequence of {Ax obtained by removing repetitions. In other words, we have X b for all k E N. We take the union bound over {Xi} by assigning probability 8' 82/(2i²) for X₁. By Ee (2/(2))) S 8', we have that with probability least 1 1-8,
X Var(V +
3H 4HSA2
(Pn - P)Vi+ii &
log
(3)
4H
Xmn
8'
holds for all n E N. ()) S x A. E [H] and E N. For any k E N, by taking n (s, and = ls. inequality (3) implies
|itt - PPVii 1
Var (ar
(x log 4HSA
3H
4H
Replacing 8' with 8/6, the logarithmic term becomes (2 = l, completing the proof.
Lemma 6.
With probability at least -
(P - P--P))V (s, = Var(Vit 6
(*
holds for all (s, a) E S x A. h E [H], and k E.
Proof. Fix (s, S A and h E [H]. Let {st] be a sequence of i.i.d. samples from P(.|s. a) and define X; P(V (s a) (Vi+1) ) (st), similarly the proof of Lemma Then, [2] S 2 holds almost surely, [[X.] = 0, and
E [X* Var((Vi++)))) (s), a) 4H² (sr(V
holds for all E N, where use Lemma 35 for the inequality. Applying Lemma 36 with X 1/6, the following inequality holds for all with probability at least 8':
1 n (ar(Vi++1(saa) 6 log 8'
X1
2
t=1
Plugging in X, 1(V (s, 1 and dividing both sides by n yields
6H log 8
(P ) < Var(Vin a)
(s,
where ( a) = En 1st 8')/n. Taking the union bound over (8,a) a) E A and h [H], obtain that
1
6H HSA log 8'
(P (P- P-).VVi = (sr
n
holds for all n N, (s) E S A, and f E [ft] with probability at least 8'. Replacing 8' with 8/6, the logarithmic term becomes ( which is less than f = S for
any l E N. The proof is completed by taking n N*(s, a) for each k E N.
O
Lemma 7. The following inequality holds with probability at least 1 - 8' for any (s, E S SxA. s' E S, and k E N:
2P(s' 8,
(8,
ph (s' s.a) P(s' P(s'|s,a) 2
(*,
3.4 (s)
17

---

Published as a conference paper at ICLR 2025
Proof. Fix (s, a) E S A and s' E S. We write p == P(s'|s,a) for simplicity. Suppose {st) is a sequence of ii.d. samples drawn from P(. a). Let X; [ = 8 Note that E[X, =
and B[X?]] p(1 - p). Applying Lemma 37 with p(1 p), the following inequality holds for all n E with probability at least 6':
2(1 log )²
2(1 + log
Σ 2 p(1 pp log 1=1
log
8'
3
d'
We apply the same bound on Et=1 -X,, then take the union bound. Further, we bound p(1 -p) S p and obtain that
n X S 2 pn log 4(1 log n)?
4(1 + log n)²
Σ
+ log
(4)
8'
8'
holds for all n e N with probability at least 1 1-d'. Let (s a) = Ei= 1 = =t//n. Dividing both sides of inequality (4) by n, obtain that
P(s' s,a) (s 8, P(s' 88 8, 2
4(1 log n)²
4(1 logn)²
n log
log 8'
8'
By taking the union bound over (s, as)) become log(45² log n))/8"), which is bounded by 2 1ogg(2SA(1 log (88)) Therefore, we obtain that
S x
A x S. the logarithmic terms
1og(452A A2 + log / =
2P(s' s,a)
2SA(1 logn)
2 log 3n
2SA(1 + log n)
Pa |s,a) - P(s') [s,a) s 22
log
n
8'
8'
(5)
holds for all n E N. ss) S A x S with probability at least 1 - 8'. Finally, by taking (*, a) for any lo E N, inequality (5) implies
(* 8, a,a) P(s'1 s,
2P(s' s, log
2SA(1 log N*
28A(1 + log N (s, as)
/²/
log
(x)
8'
3N
2P(s' | (.)))s a)
(8,,
2/
(*
(s,)
where we use that log(25 A(1 + log (s, (") = 1og(125A(1 + log N* (s,)))/8) = (a,4(8,)) a).
0
Lemma 8. With probability least 1 8', the following inequality holds for all (s,a) E S x A and k E
H
|** a) r(s,,)) s Aur(s,a) + (*
Proof. Fix (s, E S x A and X' E (J Let (e be a sequence of rewards obtained by choosing (s, a). Let X, Rs Re-r(s,,) a). By Assumptions [add {x, is martingale difference sequence with [X,] < H almost surely for t. For simplicity, let E, be the conditional expectation conditioned on {X; __ Then, by Lemma 36 with A = X, holds with probability 8' that
X H
Σ
E.
X +
log g'
for all E N, where we bound 3/4 with 1 for simplicity. We proceed by using that for ran- dom variable with < X < H, holds that Var(X) < E[X < HE which implies that [x-[XX]] Var(R,) < HE,-IRR [R Hr(s,a). Therefore, obtain that
H X, Xn + x log
18

---

Published as a conference paper at ICLR 2025
Dividing both sides by n, we derive that with probability least 1 - -
Σ X, = - -((,,a))r(sa)) S a)) + X'n
log 8
holds for all n E N, where in ;= - Re/n is the empirical mean of random rewards. Repeat the process for -X, instead of Xx, then take the union bound over the two events and over all (s S A and ak. as in the final steps of the proof of Lemma 5
Then, obtain that
H
log 4SA
(s, r(s, a)) S a))(s,
(x
holds for all (s, E ES and k E N. The proof completed by upper bounding the logarithmic term log( (4 (8) by f = lo
Lemma 9. Let r/ and (-) be defined as in Appendix following inequality holds for all K E N:
With probability at least 8', the
K
K 1
(PU ahd - 1
Var(Uh- a..) + 3/4 log x
4=1
Proof. Let X 1(h (PUh (sh, ot) U ( (5) }). We have 1(h n/² Fh and i at) - U U E Fh+r and hence X E Fh+1- Furthermore, we have [| = 0 since shi11 ~ P(-s a is independent of Fh. Therefore, {KA]RR is mar- tingale difference sequence with respect to (a We have | I H almost surely and 31( = 1(h < r²*) Var(U (sh ). Using Lemma 36 with À = 1/3,, obtain that
K
H
K
ΣΣ
x
ΣΣ k=1h=1
1 1 (1 < Var(Uk- a + 3H log 8'
4H
holds for all K E N with probability least 1 - 8', which is equivalent to the desired result.
Lemma 10. With probability at least 1 - 8', the following inequality holds for all K E N:
K
K +
(P(U) (1 at: ( s
Var(U
a + GH2 log
Proof. Let X (h < ( a ( For the same reason as in the proof of Lemma 9 { is a martingale difference sequence with respect to {Fk Ja. We have [ < H² almost surely and
B((X)))FA) ( r Var((U)+1))) a 1sh n ]4H² Var(U (sh at)),
where we use Lemma 35 for the inequality. Using Lemma 36 with À = 1/6, we obtain that
ΣΣ
1 & MΣΣN < </) Var(Uk)+) a GH2 log
k=1/=1
holds for all K E N with probability least 8', which equivalent to the desired result.
Now, we define the event E, under which Theorems I and hhold. Lemma 11. Let & be the intersection of the eventy of Lemmas with probability at least 1 - 8.
and 10 Then, & occurs
Proof. By each of the lemmas and the union bound, E happens with probability at least 1 68'
1 - 8.
19

---

Published as a conference paper at ICLR 2025
C PROOFS OF THEOREMS 1 AND 2
In this section, we provide the full proofs of Theorems and We begin by restating Proposition with specific logarithmic terms. The proof the proposition is identical to the one presented in Section 4.4 Lemmas used prove this proposition
also proved in this section.
Proposition 2 (Restatement of Proposition]] D. Ler [A be a sequence of non- too-increassing posi- is run with = 7HH11//x Then, under the event of the cumulative regret of K episodes is bounded as follows for any K N:
tive real numbers with X < L. Suppose Algorithm 7
88H Aσ
Regret K) S 4H Σ A
SAl,,K2, - 168HS Al2 A 6HSAA1,
Proof. The inequality holds by Lemmas
2
3 and
14
where the last lemma is restatement of
Lemma with specific logarithmic factors.
Theorems aad are proved by assigning appropriate values for X in Proposition 2
Proof of Theorem 7
Take X min(1, 5 forall [K]. We apply Proposition
First, we bound the sum of 0 for E [K] as follows:
SAL1E2 K
4H Σ k=1
AR S 4HK 5V
20H v SAKE11,,
We also have that
88HSAR162 88HS ALI l,, max
K SALIE2,
55
K
$ 88HSAR122.
1+
5V
SAL122
68HSAL66, + 18H V SAKe
(6)
By Proposition 2 the cumulative regret of K episodes is bounded as follows:
Regret(K) 38/1 3811 SAKe 168H1 Al2,Ke, S8HSA 6HSAA
We further bound the last three terms into simpler form. Recall that G. log 50 log KM?
and that both & < f,xx and la,K S x hold. Therefore, bound the terms follows:
16 Al2,Kls.K + 88HSAC1 6HSAA < 168HS AC, A 88HSA, 22, + 6HS AC,
< 168HS
88HS (1+(2)
< 2 AC (2,k).))
Proof of Theorem 2
Fix is N momentarily. Let be the greatest integer such that 2 < k. We first show that { is non- -on-irreaaiig. so that Proposition 2 is applicable. We take A
min (1, / AAL/AAA,,00 2 m. Taking C' = log(22HHAA/0 and defining f(m) as in Lemma
33
have ds (f(m) and the conclusion of the lemma implies that (2e) is non-increasing.
20

---

Published as a conference paper at ICLR 2025
We bound the sum of 2ạ for le [K]. Note that f1.2 I 61,ks m2 hence have d I A4 Therefore, we derive that
62 and 2 k/2 hold,
K
K
2SAL1
4H
A
S 4H
k
k=1
$ 20H V AS K2,K
< 40H 2
< 5TH /TH/SSKK,,.. SAKE,
where we use that Ex=1 k-1/2 < 2 K for the penultimate inequality. By the same steps as in inequality (6) of the proof of Theorem we have that
< 88HSAL, + 18H ISH/SSAKG,,K..r
By Proposition 2 the cumulative regret of K episodes is bounded as follows for all K E N: + 6HSAA,K
Regret K) S 75H T5H.SAKKe,Kk. + 168H (2 + 88HSAL,
Using incquality 7 in the proof of Theorem [ the sum of the last three terms is upper bounded by SS Al", I. + f2,x), completing the proof.
C.I
PROOF OF LEMMA
In this subsection, we prove Lemma 2 which states that our algorithm exhibits quasi-optimism.
Proof of Lemma 2 Elementary calculus implies that for x E [0, HJ. the bound 0 S 2x + x² s
2H
H holds. Therefore, sufficient to prove the following stronger inequality, which we prove by backward induction on h:
1 (v))(s)) 2H
(s) - (x) S A (v)
The incquality trivially holds for h = H + 1 as both sides are 0 in this case. We suppose the inequality holds for h + and show that holds for h. Since the right-hand side is greater than equal to O, the inequality trivially holds when Vi H. Suppose (s) < H. Denoting = n (s) and a" = o (s), have that
v (s) = Q (s. 2 = (s, + (
where the first inequality holds by the choice of argmax, or EA O (8, a') of the algorithm, and the last equality holds since (s, a*) I (s) H. We bound V (s) (s) follows:
(s) (z) < (r(s,a") PV PV (i
(8, a²)) (p*(s)") b² (s, + pt
= (b((s + r(s,a")) - pk (*, + PV p (8)
T is bounded by Lemma as follows:
H6L
I S )er(s,a")+
XcN*(s,a")
21

---

Published as a conference paper at ICLR 2025
We bound 1z follows:
2 = (P - P - V (=,,aa))"")
$ (P- SP-PP P Aa 22 /
2H (Vitz)) (s,a")
1
= (P -P- V/+
(8, Ae(PR - -P) ()(((1 (aVitI 1
2H (Viti)2) (0,
+ A 2V/it1
1
(Vitt2)) (s,a")
2H
dk
= - (P - Vitzsss (s,aa) +
2H (P (t
1
P 2V
(V (Viit1) )²
(8,a*),
(10)
2H
where the first equality adds and subtracts js 1 a²), the next inequality is due to the induction
hypothesis, and the following equality adds and subtracts P(2V h+1 W+++1 ) 1 (2H() We bound
the first two terms using the concentration events. Since 0 S A S 1, we have [1 2Ax S 1. Using À Lemma have [(P Vi)Vi+ (s)aa) 4H
Var Var(Vi+1 a²) + 3N/1. (=,a)" By Lemma 6
61 we have (P- pk ( a²) I Var(V (s,, a²) 1/2+ N*(s,a")) Plugging in these bounds into
(3,
inequality 10 we obtain that
A
3H41k
3 de Var(V (*(ssa*)
1 S
+
4H
\sN*(s,a*)
4H
+ A
22
2H (Vitt)) (s,a*)
A
6H61
< Var(Vi+t)(s,aa))
+ A
2 (Viit2)² (8,
2H
\xN*(s,a*)
2H
À
6HH,,
(Var(Vi+1)ss,a))
1(V (s, + 2h PV (8, (s.
= 2H
where the second inequality applies d < 1/Ax from A < 1. By Lemma 27 we have Var(Vi (V, case have An (V*)(s,a)) r(s,a"). Therefore, we obtain that
( I (V) + 2H max max[Ax(VV (v*))) 0),,, where in this
d (s) + Aur(s, + PV,
6H6 N a+)
L < 2H
(11)
Combining inequalities
8 and
together, we complete the induction step as follows:
H4I
(i) - () < ab" + Aur(s,a")+ + (x,*(ss,a*)
d (s) + AuT(s,a") (M,PV) \xN*(s,aa))
6HEI,
2H
-s,aa"" TH6
d
+V
(v)
2H
Ae (2V)(() 2H (V))()))
where the last inequality uses that (8,a0)) = TH41s/(ANN (s,
and
r(s,a") a*) + PV (s).
C.2 PROOF OF LEMMA
To prove this lemma, need the following two technical lemmas.
22

---

Published as a conference paper at ICLR 2025
Lemma 12. For any E S, h [H + 1], and & E N. define (s) == (s) (s). Under the event &, the following inequality holds for all (s, E x A, h E [H] and N:
1ipe PPV a)
A Var(VVi-))s.a)) + 10H
4H
where (s) N=(3,o] (3HL1 21HSL3,
Proof. We add and subtract - -PV= a) and then use the triangle inequality to obtain
lit - PPM-PP s (ist P) (Vitz (i+t)) (pt ())
By Lemma 5 2 is bounded by dE Var(Vi++))s,0) + (3 To bound T, we aH
apply Lemma with = 10 and obtain
21HS83,((5,a)
Var(V + (*(
1077
Putting these bounds together, we conclude that
(p+ - PPVX
d Var(Vi+t))s,aa
1 Var(V (x)
(3Hl1
5
+ (13
4H
10H
Au
d Var(Vit+1
1
Var(V (s,
4H
10H
Lemma 13. Under the event E, the the following inequality holds for all s E S, [H) and k e N:
An(V* V= (o,a)
An de 3V
2H (V1))
(vx
3
2
+ 23 (2,0))23(s,,0))) (s,a), (12)
5H
where a == (s) and (*,ss)) = N((a,a)
(11H6, +1H55(,((8,0)
Proof. We begin as follows:
An(K - v** [8, (V) - (b, - (Vx (s) (v)
I (s) bb + a) (pt -P)V - r(s,a)
= (8) + (f* - r(s,a)) - -(pA (P=-P)V/t+(e
By Lemma 8 we have that (*(,)) - r(s,a) I )er(s,a) + A.N=(M,a)' By Lemma 12 it
HELK
holds that ppk- ()V < TH Var(Vi+t)(s,a)) + 1OH Var(V/t + (s De-
(s, 0}. Combining the bounds and using that 3 (s, = 1yth (*(8,)) a) (s, a) + (L,,t/(A,,V)) N* (s, a)) holds by defiiitoon, we obtain
fine I = max (
h S Aer(s, a) + 4H
Var Var(Vi+z)(s,a)) + 10H (s.
(13)
Applying Lemma 27 to Var Var(V a). we have that Var( - (Ax)()))))s + 2H max{ A, (V*) a), 0}. Since Lemma 28 states that (s,)(s,)) 2 0, we infer that
Var(V ((s, -V. 2H
(14)
23

---

Published as a conference paper at ICLR 2025
By Lemma 2 we have 1/ + H 2 0 for all h [H + 1]. Applying Lemma 27 to
Var(V Var(Vh+1)ss,a) = Var W/+ /+1 + 2x, a), we obtain that
Var v + +22 ( (s,a) -An
3 ( MaH
(s,a)
An (vM+ + 2 2
(s, (9,0).0
+ (2H + 32p H) max
We bound (v k + Hx) () as follows:
Do vh + 222itt (5, = An,
An(V) - As(V")ssa)
S (s,a) r(s,a)
AA(V"))s, - Aa(V=)) (s,a)
- as,
Therefore, by the definition of I,, we obtain that max Dn (V* + )))HH)(s, 0} s 11 and conclude that
where the inequality is due to Lemma 28
Var (/t + 3 - =dall) (s, S -An
((7A
2 (8, a) - +(2H- + 3
2 AuH
2
S S
H
+ (00))5HH1-
(15)
where we use As I 1 for the last inequality. Plugging inequalities 14 and 15 into incquality then applying a(s,a) & (v(V)) (s, a") by Lemma 28 we obtain that
[3
S Dn
An
(
V* v-
4H (v3)))
1
T y
+
))
1))(es) (s, + (s,
(
1
10H1
Solving the inequality with respect to I implies inequality 12
Now, we are ready to prove Lemma 3
Proof of Lemma For notational simplicity, we define the following quantity:
Da(s)= == As (V)
2 (V7)(())
1
((^x.T)
2
3 ())(s) X H ))
5H
For x E [0, H). the bound < 3x x² 22/(2H) S 3 holds. Similarly, for E [0, H] and
y E [-H, H). we have ²² (y + c)2 -y² 2cy and -4H² < y2² 2cy S 0. Therefore, by
setting x = (s),,,, = (s), and c c= 2 H, we obtain that - H - (n((s) S 5 [H] and
2 A for all
To prove the lemma, we prove the following stronger inequality by backward induction on h:
V, Since (s) = 0 for all E S, the inequality trivially holds for h = H + 1 as 0 < O. Suppose that the inequality holds for h + 1. By Lemma 13 which can be rewritten as A (V* Va S Au (D) a) + 28, a). we have that
(s) -, (s(s) + (x)
v)( VØ," (s) An(V= V* (s. P(V (
(n(())s,,a) + + (s, P(V Vnti)ss
(16)
24

---

Published as a conference paper at ICLR 2025
By the induction hypothesis, we have that
P(V
V (s, S P(Dn+1 20
(17)
Combining inequalities 16 and 17 yields
V (s) V (s) Da(s) + (s, PU P (s,
(18)
Finally, by that -4H/5 & (s(s) and (s) Vi (s) - H always hold, the following inequality
always holds:
(6) - V (s) - H E (s) 2H.
(19)
By inequalities 18 and 19
we conclude that
(s) Vi (s) - Dn(s) 2mnn))+m (s, + (5)+2(5, H3
= +.((s)+
completing the induction argument.
C.3 PROOF OF LEMMA 4
We restate Lemma 4 with specific logarithmic factors.
Lemma 14 (Restatement of Lemma[4). Under &, it holds that
K
4AHSAC1, + A Al2 + +3SSA
(t(s)) <
Ax
k=1
for all K- E.
We prove this lemma in two steps: using the concentration results bound Σn Th by En. (sh, a and using the logarithmic bound for the harmonic series, En 1/n S + log N.
Lemma 15. Let n/th be defined as in Appendix A Under the event it holds that
K
K x*
Σ
(+ <
2
(s ab) + +3HSAL1,K
for all K N.
Proof. Decompose U$ (st) as follows:
U+(st) - 8* (st, at) + (U aft)
8t (st, )+ PU att U22 (sh) + (5+)
(3t a + PU at) (h+1(sh+1)) U (5/t
Σ (sh, ot) + PU (5 oft) U H1 11 + +H+13,
where the last inequality uses that U + = 0 and (s)(s) < H for all s E and h E [H]. We take
the sum of U$ (s4) for k 1,2, K. Let 11 = Σ (PU so that
(
k
K ( + H
Σ
U <
1 H
+1+1)+1-
(20)
1=1
1=
k=1
1=1
25

---

Published as a conference paper at ICLR 2025
By Lemma 9
we obtain that
6
1 4H
Var(U at) + 3H log
k= h=1
1
=:
12 + 3H log 8'
(21)
4H
where we define 17 = -E - Var(U ) By Lemma 27
we have that
Vor(Uh++)) o S - -an((U)))) o + 2H max (Ax (s* at), 0}
S { ( 2Hh a%)
=-(U)) + 1( (5% + 2HB (8%, ah)
where the second inequality uses that
(n,U))(s, a) U (s) 1 (s, (8* PU 1 (s. a))
PU P (s. 3 (s.
Therefore, the sum of the variances of U (s at) for the k-th episode is bounded as follows:
(shh S
Σ (()) +
Σ
P(Uh+1)) af)
+ Σ 2 af)
hml
Am
h=1
2H a/) (Ut)) (
h=1
(2
h=1
<
2H 2H (sh al) + 112 # 11 + +
h=1
(P(U 1( (5 a (U%+ 12 (5h+z))),
h=1
where we again use that Uk 1/)) S Hn + H + 13 for the last inequality. Therefore, by taking the sum over k [K]. Ig is bounded as follows:
K 1t + 11 11
1
211 21 (3%
(5%
at) + H
h=1
k=1
K
( (sh att - (s
km
The last double sum is bounded by Lemma 10 as follows:
K n
P(Utti)(ss at) 12
1=1
1=1
K
<
Var(Ukh ab) + 6H2 log z
2 k=1 h=1
- 12 + 6H2 log 6
Therefore, we deduce that
-1
K Σ
1 12 + 611
log 6
1 <
21 (6),
2
# +
2
k=1
26

---

Published as a conference paper at ICLR 2025
Solving the inequality with respect to I2, obtain that
K
K
1
4H3
(8 a +
2H²
Σ
# + 12H2 log
(22)
R=1 h=1
Plugging the bound of inequality
(22) into inequality 21
we obtain that
H
6
I
Σ
6H log
(23)
By combining inequalities
(20 and 23
we conclude that
K
K
3H
2
(s
Σ
#1
6H log
2
R=
Finally, we bound the last two terms using Lemma 30
as follows:
3H
3H
6 8
Σ 10
H 13 6H log
SA log, 2H + 6H log
2
6
3HSA log 2H + 33SAAlo
12H
3HSA log 5
< 3HS
where the first inequality is due Lemma 30 and the second inequality applies log, 2H S 2 log 2H on the first term and A > on the second term. The proof is complete.
Proof of Lemma
14
By Lemma
we have
K
Σ
(+ <
( a + +3HSAA
Let = 11H A +21HS and obtain that
Then, it holds that 3(s, a) S / (s, a). We apply Lemma 31
(s
(sh. an 5
T (=
KH
$ 2/ SA log
1+
SA
22
Alg
Combining the two inequalities completes the proof.
D PAC BOUNDS
In this section, we provide the analysis of PAC bounds. We summarize previous achievements and our results on PAC bounds for episodic finite-horizon MDPs in Table We note that although Jin et (2018) propose conversion that enables regret-mininizing algorithm to solve BPI tasks, the conversion is sub-optimal in terms of 1/8-dependence; it results in 2/82-dependenee when log } is possible. Refer to Appendix E in Ménard et al. 2022aa for detailed discussion.
D.1 ALGORITHM
We introduce (e, 6)OO an algorithm for the PAC tasks, and describe it in Algorithm 2 The interac- tion between the agent and the environment is the same EQO, where the parameters set based on and 8. Then, executes additional procedures to verify whether the policy n is e-optimal, which is necessary for BPI tasks.
27

---

Published as a conference paper at ICLR 2025
Table Comparison of PAC bounds of different algorithms for tabular reinforcement learning. denotes that the bound is not available.
Best-Policy Identifi fication
Paper
Mistake-style PAC
Dann & Brunskill
2015
H² log 1
Dann et al. (2017)
(H' SA + H S' log
Dann et al. (2019)
S1
S
log 8
11 SA + H 1
log
Ménard et al.
(2021a)
$1
log
SA
(S + log x))
Zhang et al.
(2021a)
HH'AA
HS" A
log
12g2
This work
H'SA
HS*
log 8
H¹ + log
Algorithm 2: EE0
Input E (0, H. E (0
Output: IT, Set of e-optimal policies
B(n) 68/2 log 24HSA 30HS 129 log(en)
II 0:
3 for k= 1,2,.... do Compute x² using Algorithm Ü (s) +- 0 for all s E S; for H. H 1,...,, do foreach do
with Cj 56H²
log 24HSA
- (s);
(M B(N
(%(()) - min (s) p40 H}
if (s)
10
if (s,
(s)) then Add nh to IT;
// If current task is BPI, return ,":
13
Execute policy n² and observe trajectory (s at, sh...., sty, a $
D.2 ADDITIONAL DEFINITIONS FOR PAC BOUNDS
this section, we define additional concepts that are required to analyze the PAC bounds.
We define two more logarithmic terms, fa log(1 + 270( H 2 + S(26) )) and fa log (oogoo/ss)).....oo.....///))((() We also define analogous concepts for 3h, U... N n and r/Sh define and B, which are functions that map N to R as follows:
B(n) 18812
B(n) 1
188H
73HSt3,n
E
28

---

Published as a conference paper at ICLR 2025
For k N, 3h and 3 are functions from S x A to R defined using / and B:
(s,aa) = 3 88H + 30H 30HSLt,,(ssa)
a))
(s, (s,
88H
73 731156a,(5.a)
(N)
(s) and b defined in similar manner to U2. but using 3 and 3 instead of 3h respec- tively. Additionally, the definition of Ü uses ps instead of P. They are formally defined by the following iterative relationships:
(s) == ( :=0
(s) min ( (s)) - (s)), H) for h [H] (s) min (3th (s, (s)) PU के. (s)), H} for h e [H].
Algorithm 2 adds n² to II if (s s e/8. We denote the set of episodes that do not meet this condition among the first K by Tk. and its size by Tk. In the analysis. we are also interested in the episodes with (++) > e/16. For K E N, we define Tx == (k [K] (x(+)) > e/16} to be the set of episodes that satisfy U (x e/16 among the first K episodes. Analogously, T I is the
size of T
We define n and (s, a). which are the counterparts of nh and N a), but only count the episodes T K. Specifically, we define them as follows:
as) ΣΣ (s.) sh) j=
(* a) / (s,
H
= Σ Σ
- = (s,
1ET h=1
Finally, we define 17*, which the counterpart of n² defined by using n and N instead. Specif-
ically npt = min(h E [H] ( at) > ( a where 1/t = H + 1 if there is no such h E [
D.3 PIOO-BROBA EVENTS FOR PAC BOUNDS
the events of Lemmas 9 and 10 have be replaced by the following events. To summarize, Uh is replaced with U ./ is replaced with 17* and only the episodes in Tk contribute the sum instead of all & [K]. Recall that 8' 8/6.
To prove Theorems
Lemma 16. Fix E E (0, H). With probability at least 8', the following inequality holds for all K E N:
Var (sh ab) + 3H log 6 g
Σ NET
att - Dh (s S
4H
kET
Proof. Let 1 == (() > e/16, < n and x = (PT h+1 (s (o5/,at) att) - Uk h+ i (st
Since IN Fi. (X/Tan is martingale difference sequence with respect to (F% in the proof of Lemma We have x H almost surely and [{(()))) 7/ Var(U h 1 at)-
29

---

Published as a conference paper at ICLR 2025
Using Lemma 36
with À 1/3, obtain that
K
H
K
H
I Var Var(Uh+11)(f) a + 3H log 8'
4H
A=
holds for all K N with probability least 1 1- 8', which is equivalent to the desired result.
Lemma 17. s E (0, HJ. Then, with probability at least 5, the following inequality holds for all K N:
Σ NET h=1
(P(U)+1) a - ( S Σ
Var(U%+ a + 6H2 log
6
h=1
x+11)) h+1) (s at -0 ( Proof. Let 1/ (s) c/16, < n/*} and X = (P(U
As in the proof of Lemma 16 (x a martingale difference sequence with respect { 1R, We have X I 2² almost surely and
B B(xx = I Var((UU+1)))) a S Var(U a%)
where we use Lemma 35 for the last inequality. Applying Lemma 36
with A 1/6, we obtain that
K
K H
I Var + a + 6H2 log
R=1 A=1
1= A=1
holds for all K N with probability least 1 - 8', which is equivalent to the desired result.
Now, we define the event under which the bound of Theorems 3 and holds.
Lemma 18. Let be the intersection the the events of Lemmay with probability at least 1 5.
16 and
17 Then, & happens
Proof. This lemma is proved by taking the union bound over the listed lemmas.
D.4 PROOFS THEOREMS 3 AND 4
In this section, we prove Theorems and The following proposition presents the theoretical guarantees enjoyed by Algorithm 2 and it directly implies both thcorems.
Proposition Fix & (0, H] and (0, 1}. Let be the output of Algorithm Under E, the following two propositions hold:
1. All policies in II are e-optimal.
2. The number of episodes whose policies not included in II is at most Ko.
where Ko is defined follows:
Kg A
5 A(26, + C4.2
g2
E
Assuming that Proposition is true, Theorems and are proved as follows:
Proof of Theorem Proposition 3 states that under E, all policies of II are e-optimal, hence all the policies that are not e-optimal are not in II. Proposition B also states that the number of episodes whose policies are not included in II is at most Ku, therefore the number of episodes whose policies are not e-ottiall is at most Kg. By Lemma 18. the probability of & is at least 6, completing the proof.
30

---

Published as a conference paper at ICLR 2025
Since the number of episodes whose policies are not included in II is at most Ky under by Proposition 3 there exists at least one episode among the first Kg + whose policy is added to II. As all policies in II are e-optimal, the algorithm may return the first such policy. The probability of this event is guaranteed by Lemma
Proof of Theorem 4
17
Now, we prove Proposition S
The following two lemmas show the relationships between UA, Uk and U
Lemma 19. Under E, it holds that for all E S, h E [M]. and k e N.
( $ 2 (8)-
Lemma 20. Under E, it holds that for all s S, h E [H]. and & E N,
(+) - 20 (z)
The proofs of these lemmas are deferred to Appendices D.5 and D.6 respecciiiv
We first show that under Σ, the policies in II are e-optimal. Note that by setting X 8H Algo- rithm 2 runs Algorithm ] with C = / Aς. Also, the proofs of Lemmas 2 and 3 do not rely on
Lemmas 9 and 10 Therefore, the conclusions of Lemmas and hold with A sH under & This fact leads to the tollowing lemma:
Lemma 21. Suppose that Algorithm 2 is run and the event & holds. If (f S s/8, then policy x is e-optimal. Consequently, all the policies in II are s-optimal.
Proof. By Lemmas 2 and the instantaneous regret in episode k: is at most 4h, + (U = e/2 + (xf). By Lemma 19 this quantity is less than equal to e/2 40/ (sf). Therefore, if (s e/8, then the instantaneous regret in episode i is at most c/2 + e/2 =
Now, we prove the second part of the proposition that states that the number of episodes whose policies are not added
finite. Restating our goal using the notations defined Appendix D.2 we want to show that Tk < Ko for all E N. To so, we show Tx < TT and Tk Ko. To show T < Ko, provide upper and lower bounds of E Uf($), While the lower bound straightforward to obtain, the upper bound more technical. We state the upper-bound result in Lemma 22 and defer its proof Appendix D.7 We note that Lemmal 22 and its proof analogous to those of Lemma 14]
Lemma 22. Under E, it holds that
(1())) 2 + 292HS Al l,,Tx +3HSAC,
Σ RETx
for all KEN.
We require one more technical lemma, which is necessary derive upper bound of Tx from an inequality it satisfies
Lemma 23. One has
5632H
A12 + 48HSA4
< Ko.
2²
The proof of this lemma is deferred to Appendix D.8
Now, we are ready prove Proposition 3
Proof of Proposition By Lemma 21 we have that for all policies in 1l are e-optimal, which proves the first part of the proposition. Now, we prove the second part of the proposition, that there most K, episodes whose policies not included in II. By Lemma 20 (++) > e/8 implies that (st)) e/16. Hence, the
31

---

Published as a conference paper at ICLR 2025
number of episodes where (f(( > e/8 holds during the first K episodes is at most 7x Therefore, it is sufficient to show that TK I Ko holds for all K N. we obtain the following condition on Tx:
Using Lemma 22
ETK K
Σ (+)) кеTк
16
352H2 SA1 2.TK 292HS Al 2l2 3T + +3HSAE,
where the first incquality holds since (s is greater than e/16 when & Tx by definition, and the second inequality is from Lemma 22 Rearranging the terms, deduce that Tk satisfies the
following inequality for any K E N:
5632H S
4672HS AC2 3I + 48HSAC
TKS
E²
This inequality, combined with Lemma 23 shows that one can not have Tx = Ko for any K E N. Since Tx k starts at To = and increases by most as K increases, we conclude that T K < Ko must hold for all K E N.
D.5 PROOF OF LEMMA 19
Proof of Lemma 19 on h:
We prove that the following stronger inequality holds by backward induction
($) S ()) 211 (s)
The inequality is trivial when h = H + Suppose the inequality holds for h + 1. The inequality trivial when (s) H. Assume that (*))) H, that (z) (s, + 1 (s, where a = (s). We have that
(s) S P
(s,a))
P (s, a).
(24)
We bound the second term in inequality
24 by applying Lemma 29 with p 4.
9H N*(ss a)
(P- Pkyuk 1 (s,a))
<
Var(U (s.,
(25)
4H
We bound the last term of inequality
24 using the induction hypothesis as follows:
PhU (8, a) S pk 2 h+1
2H (1 (s.a)
1
- + (P (P- pk -
(U)t)) 2H
((. (26)
211
For (P -P- (U) h+11) 1) (s,
apply Lemma 29 with p 8 and obtain the following bound:
8H2 ( + 17HH"St
(P (USh)))
(*
2 Var(U + 17HA250,,(8..))
<
(27)
(*
where we use Lemma 35 for the last incquality. Plugging inequality 27 into inequality (26 we
obtain that
9H (
p ( s (s, + 4H
Var (s,
(*(
2H
(28)
32

---

Published as a conference paper at ICLR 2025
Plugging inequalities 25 and 28
into inequality 24 obtain that
(s) S (s) 18H5(3,4(3,))
- P(U)) + 2
(s
2H
By Lemma 27 we have that (ar(Uh+))(s,aa- - ( --U))) 2H max (s,))))
S - (s,aa,
where the last inequality uses that An (s,)) a) U (s) PU S (8" + PU 1 a)) PU Ph (8, a) = (s,a)
Therefore, we conclude that
(s) s (8,
18H5L3,4(3.4) (4(s,a) a)
1
(U)) +2P"0
2H
1
= 23 + 2 (s
2H (s)
=00 2H (U*))
where the first equality comes from that 3 (s. a) 3h (s. ().a)+ + 9 (H.))
(2,00) by their definitions and
the second by Ú (5) = (s, + p
D.6 PROOF OF LEMMA 20
Proof of Lemma 20 We prove the following stronger inequality by backward induction on h: (s) s (s) - (0))
The incquality trivially holds when h H + 1 or (s) H. Suppose the inequality holds for h + 1 and (s) H. Using the induction hypothesis, derive that
(+) S (s, + ( (8,
s { + Pb 2 h+1 2H
(hh (hht))) (s,0)
= (s,, + -(pt -P) (2 h+1 2H (U (Uhti)2) (s,a)+1 + (2
_
2H (U (s,a)
-B)(s, + +2(0x - P)U 14 (s, (P (P- (T)a))
2H
+ + 22 f
1
12 (s,a),
(29)
2H
where a (()). Using Lemma 29 with p= 8, we obtain that
8H Var(U), 17H
(p+ - -P)U (s, <
(*
and
(3s - 17H² SLg,
(P (P-P")(Th - 8H² Var((U) (3) a)
(s,
Var(Uk (s, a) 17H2SS3,M(s.a)
2
N*
where we use Lemma 35 for the last inequality. Plugging these bounds into inequality 29 we obtain that
$
S (s,
1
Var(UR (s., 43HS4z,4(s.0) a)
+
P
(U h+1 2H
(U
(Uh+1)2)
(8.a) a)
2H
(*(
1
= as, 2H
(\)s -
+
(
33

---

Published as a conference paper at ICLR 2025
where the last equality comes from that (*, (s, (aHSts,a(s.o) (x,0) by their definitions.
Using Lemma 27 we have
Var 11)((+)))sss)))
P(U (s, - (())) +2H (
S - (sH)),
where the last inequality uses that (s, a) = (s) - PU Pu a) S (s, + PU (s, PU ( = (s,a)) Therefore, we conclude that
1
(+) < 2.3 (8.0) a) + 2PU (+
(s)
2H
= (s) 2H (s),
completing the induction.
D.7 PROOF OF LEMMA 22
Analogously to Lemma 14 Lemma 22 is proved in two steps: first, using the concentration results to bound Σx Uh with Σx, (s ). and second, using that Ex=1 1/n S + log N to bound En. (st,,, at)) However, more meticulous care required for the second step, the bound must depend only on I'x and be independent of K.
Lemma 24. Under ε, it holds that
Σ RETK
3h (sh. o + +3HSAR,,K
RET
for all K E N.
Proof. The proof is identical to the proof of Lemma 14 except that the use of Lemmas 9 and 10 replaced with Lemmas In
Lemma 25. Under E, it holds that
Σ
8
Σ
3h
S 2SA
(88112 + +7HHSE
) 12TT
8
kETx
h=1
for all K E.
Proof. Recall that Nik N* a) represents the number of times the state-action pair (s, a) S x A visited in episodes that satisfy U (sf) e/16 up to the (I: 1)-th episode. Clearly, N* > (*(s,, a). By Lemma 34 with C1 88/2 + 73HS 1oggS1 and C2 73HS. we have that B(n) == (C₁ + C2 log(1 + log n)) /n non-increasing. Therefore, we know that 3 (sssaa) a)
B(N*(s.a) s B(N*(s,a)) (s) Thus, we have that
Σ kET h=1
3 (sh
B(NK (shi dfi)
NET 1=1
Since (s, < TKH, we have (NN a)) I N/ a), where & = 88H + T3HSE By Lemma 31 we conclude that
Σ
B(N a S Σ
7
N4 at)
KETR.
h=1
кеTw 1=1
Txll
< 2..5Al0n Algg
1+ SA
(8811211
73H SL. C2TTT.
-SAA
34

---

Published as a conference paper at ICLR 2025
To be more specific, apply Lemma 31 to the episodes in T K. meaning that 7 in Lemma 31 should be the trajectory of the k-th episode that satisfies (s)) > e/16, and the sum is taken over k episodes.
Proof of Lemma 22
Combine the results of Lemmas 24 and 25
D.8 PROOF OF LEMMA 23
Before proving Lemma
23
technical lemma regarding the logarithmic terms is required.
Lemma 26. The following inequalities are true:
Kg 261, f3 S 281 + ls
(30)
(31)
Proof. We first provide a crude bound for log KoH. Let B == H& H8(26++66,)) By definition,
have Ko I 12000BS AL4.c and l..c log(1 270BH)). First, applying Lemma 32
log(1 + 270BH) with C2 = 270, we obtain that
log(1 270)
4. 5
(270BH) S 6BH
270
Therefore, we have
KoH & 12000BHS S =
(32)
To prove inequality
30 we use inequality 32 and proceed as follows:
KgH
f2 log
1
SA
log (1
72000 H²)
2
(1 v72000
21og(1 + 270BH)
244.5
where the first inequality holds since + x² < (1 + x²²² for all æ 2 0.
To prove inequality (31b, we need to further bound B. Since 24HSA 2 48, applying Lemma 32 with
C 48 yields
log 48
24HSA
2HSA
&
(33)
48
8
8
Applying logæ S x/e, we obtain that Es I 1 that
log H/e)) < + H/(es) < 2H/e. Then, it holds
4HSA
2H
20, + ls,s
8
4HSA
H
HSA
H
+
8
8
8
5H2SA
(34)
where the second inequality uses that H/e 2 and HSA/8 2 Then, we bound B as follows:
126
HS((e, + ls,s)
+
E²
E
4HASA
52
862
de2
52
<
(35)
8e2
35

---

Published as a conference paper at ICLR 2025
where the first inequality applies inequalities (33) and (34 simultaneously. Utilizing these bounds, we derive an upper bound of log KgH as follows:
log KoH < log 72000 H3
5832000//
log
82gt
106817H A
log e H
log
8²
where the first inequality applies inequality 332 and the last inequality uses that 5832000 follows:
the second inequality comes from inequality (35).
106871. The first term be further bounded as
10681711$$44"
26705/1 A
log
S log
82
85
8HSA
S 5 log
7HSA
where the first inequality uses that H 2 1,8 < 1, and A 2 2, the second inequality holds since 26705 < 8 32768, and the last inequality is due to Lemma 32 with C₁ 16 and 5 x 8 x (log 16)/16 < 7. Using these results, we further bound log Ko H as follows:
7HSA
EH
log KoH <
+ 4.log
8
THSA
eH
2HSA
eHl
<
log
log
8
9HSA
eH
log
(36)
8
where the second inequality log(eH/E) 2 and HSA/8 2. We conclude that inequal- ity (1). the bound of Kg is true by the following steps:
2SA log KoH
k, log
18 A log eH
< loog
82
16/1 A²
9
eH
< log
log
log log
82
4HSA
eH
< 2 2og
+ log log
8
< 26, + ls
where the first inequality holds by inequality (36), and the last inequality uses log(9/8) < 1.
Proof of Lemma 23 Note that Ko 2 12000S A, hence f2, 2 holds. Then, we have
48HSAL//
/A < (l. therefore sufficient to prove that
SA k2,Ko 4672H5 Al2, Ko < Ko.
82
36

---

Ko Ko. Published as a conference paper at ICLR 2025
Applying Lemma 26
conclude that
5680HT-5AC 62,Ke
4672H Ko L3
S1
4672HS A(28) + es.5
E²
SAR
4672H A(28) + (s,5)l4. -2
2²
12000fI*SAR, la.5
5000HS A(28; + [s,e)lsss -2
1 SALis la.e
5000H A(26, &s,e)
W
+
g²
where the first inequality applies the results of Lemma 2 simultaneous,,, and the second inequality uses that SASAE f 1.
E TECHNICAL LEMMAS
HH+1 be a sequence of + 1 functions such that Lemma 27. Ler C 2 0 be a constant. Let {Vi
: + 10, for all h E [H 1). For any (s,a) 8 A, the variance of Vi+1 under P(-|s,a) is bounded as follows:
(ar(V a) S - 2C 200mma(44a) (V)ss)a
Equivalently, the following inequality holds:
Var(V=+1)(s,a) P(V)-))) - (VV((s)) + 2C' m (V)ss,)))
Proof. We add and subtract (Vi(s))2 to Var(Vn+1)(s, a) and obtain the following:
Var(Vh+1)(s, a) P(V++1(( (s, (
(s (V)( (V) (PV++1 (S. a))²
12
We have 1= = a) by definition. We bound 12 as follows:
I2 = (s) + IV, a)) (V) - (V)+1(s,a)
S 2C max (V),
where the inequality that 0 I V%((s) PV,+1 a) 2C and the definition of A, (s),,a)
Plugging in these bounds for / and 12 proves the first inequality of the lemma. The second inequality is obtained by subtracting P(V++1) (s, from both sides of the first inequal- ity and using that - - (V (s, a) - P(VN+1)2(s
- -VV))² (s. a) by definition.
Lemma 28. For any (s E A and e [H], holds that (v a) 2 r(s, 2 0.
Proof. This inequality is due to the Bellman optimality equation: An (V*)(s,
(s) PVi+1(s,5 (s,a)
max(r (s,)) - (s,
a'EA
2 (r(s, a) PV a)) (V)+1(s,a)
r(s, a) 0.
Lemma 29, Let C> 0 be a constant. Under the event of Lemma the following inequality holds for all (s,a) E A
N, p > O, and V :S + [-C,
1 (ip - -P)((s, s Var(V) + C(2p + (1)axs)
Cp
(*(
37

---

Published as a conference paper at ICLR 2025
Proof. Without loss of generality, we assume that (V a) 0 and C since the inequality is invariant under constant translations and scalings of V. By Lemma 7 for any (s, s') E AxS, it holds that
2P
8, 5,
( (N,
(s' s, - P(s' s. a) S 1
(s,
Multiplying both sides by [V(')) and using that [V(s') S C CC we obtain that
( (P" P(s' 8s, a) v(S') 22IV("0) 2P(s' s,0){a,((85)) 2lax(s,0) (s,)
(s)
We apply the AM-GM inequality, 2ab S d²/p - pb? for any a, p > 0, on the first term of the right-hand side with a = P(s 88, (+)) and = 22s, (s,
2P(8' (8,)) (8,,(
2
(=(
(s.a
s P(s (v))) 2plx.(3.a) 2ls.x(s,a)
())
(s)
p
p(s (v)))( (2p+ 1)3,))a(();aa)
$ p
(*
which implies that
P(s' s,))(( + (2p + 1)(,,(s,a)
(d)()))),))) P(s'ls, a)) v(() - p
(37)
(=
Taking the sum over s' E S, we obtain that
|(pt - P))
= Σ
(5 |,,a) - P(s' [,,a)) v(s')
s'ES
1 Σ
(pt(s' s,a) -P(s' ((,0)s,))) V(s')
s'ES
! P(s' (v)))((())))+ (2p + (),
S
(a(ssa)
8 ES
= Var(V)(s, a) + (2p + 1)Sts,((s,a)
(s,
where the first inequality is the triangle inequality, the second inequality (37.. and the last equality is by PV(s, a) = O, which implies Var(V)(s,a) (s,)))s,a).
Lemma 30. For any sequence of K trajectories, we have
K Σ
In * H +1 < log, 2H
and
K
Σ 1=
1 + +1 < SA log, 2H.
Proof. We only prove the first inequality, as the proof for the second inequality is identical. We focus on the acteon pair that triggers the stopping of r/:
An + H +1)
Σ
Σ
In h + H + 1, (s drte) (s,
(8.0)ESxA
K
Σ
Σ
11n
+ H + (5 I
= (s, -
A
38

---

Published as a conference paper at ICLR 2025
If 17 * H + then by definition, it implies that n (s gky agee) 2N (s a + 1, which in turn implies that (st ( axpe) 2 2N (s") agd + 1. For any (s E S A and K E N, let Mx(s,a) a) be the number of [K] such that N (s, a) 2 (s, 1. Then, we infer that
Σ + H (6fj))
(s,a)) Mx(s,a).
Now, it is sufficient prove that Mr (s, a) I log, 2H for all (s, S A. Since N (s, a) S
(*, + H, we infer that (s, 2 2N a) + 1 occurs only if (*, < H. On
the other hand, using induction on k, one can prove that N a) 2 2 - holds for all
k E N. Hence, once Ms(s, a) attains the value [log, H ++1 for some k we have N H.
Therefore, MA (8, a) does not increase after it reaches [log, HJ + 1, implying that Mx(5,a) S Dlog, HJ + S log, 2H for all K E N.
Lemma 31. Let {-") be any sequence of trajectories with 7 (s at, ..... ++1) Let Pr be sequence of increasing positive real numbers. Then, holds that for any K E N.
K
N (K abt S 22%5SAlog (1 (1+ (1 SA
KH
Jem
hml
Proof. By the stopping rule of nf', have No at) 2 (s att) when h < s7"h at implies
that when h < r/t, n² (sh; att) 2 2 must hold. Hence, we have that
K 1 k=
K
2n n
N + a.t)
(st a
1=1
h=1
NK+1 (s.a)
27k
Σ (s:a)
n
< 27
Σ
(1 2 23 N
(K,))SSA
S 2%K
Σ
log(1 + (
(8.0)ESAA
Since log(1 + x) is concave, applying Jensen's inequality implies that
E(sa)esx (1 + N (s,
Σ
+ Dg(1+NK+l// a)) S SA
SA
(A,
KH 1+
=SAlog
SA
Lemma 32. For any constant C₁ 2 e, if x 2 C₁ then log x < log
x. Also, for any constant
C₁
C2 > O, we have log(1+z) < C2
(1+ x for 2 C2 and log (1+z)= >
log(1-Ca)
C² x for x < Cz.
Proof. By elementary calculus, one can check that (log x)/x decreases on [e, 00). Then, x 2 C1 2 implies (logx)/z < (log C1)/CI, which proves the first inequality. For the second incquality, note that log(1 + x) is concave, hence g(z) = log(1+C2) C2
log(1 + x) is convex. Note that g(0) = g(C2) = 0, therefore by its convexity, we have that g(ø) 2 0 whenever I 2 C2 and
g(x) when 0 < x S Cz.
Lemma 33. For E NNU. (0} and constant C 2 3, we define the following function:
f(m) = min {1. 25SA(C 2log(1 + m)) log (1
2n H
SA
2m
Then, is non-increasing.
39

---

Published as a conference paper at ICLR 2025
Proof. We directly show f(m) 2 f(m + for any We write := 2 10 /(SA). f(m) min 25 + 2 log + m)) + 22] Let my == max(m E N U [0] 2 2 255A]. We deal with two cases, - mg and m mg. separately.
Case 1 m & mo We show that f(m) 1 for m I mp. which implies f(m) 2 f(m 1).
First, we have that 25(C + log(1 + m)) 2 75 by C 2 and log(1 + m) 0. Thus, must show that (75 log(1 (1 + H2))/2 2 1. Note that H 2 1 and x S 25 when m I mg, therefore is
sufficient prove that 26 log(1 + 2 1 for
25. By Lemma 32 with C2 25, we have that
log(1 + x) lug(1+25)) for S 25, hence we have 75 log(1 2) 2 log 26 1.
Case 2 m > my: We prove that f(m) 2 f(m + 1) by showing that the second argument of the minimum in the definition of f is decreasing when m mnn Specifically, we show that
(C + log(1 + m)) log(1 +
2"H H SA
2log(2 + m)) log(1 +
2
SA
n
2
Rearranging the terms and plugging in 2 = 2n ((SA) one can see that is sufficient to prove
(C 2 log(2 m)) log (1 + 2H2) s 2(C + 2ogg(1 + m)) log (1 + Hz)
(38)
First, we bound C' + 2 log(2 + m) as follows:
C + log m) = + 2(log + m/2) + log 2)
SC + 2 m) 1.5
3
- 0 + 3 m)
2
3
(C + 2 log(1 + +)))
2
where the second inequality uses that C 2 3 and log(1 + m) 2 0. We bound log(1 + 2H²) as follows:
+g(1+2HH) < log 2 + log 2 + H2)
S 1 + log(1 + H²)
4
$ 3 log(1 + Hz),
where the last inequality uses that log(1 + H=) 2 when = 2 25, which holds since m m-.
As we have derived 2 log(2 +m) S (C 2 log(1 + m)) and log(1 + 2H²) log(1 + Hz). by multiplying the two incqualities we conclude that incquality (38) holds.
Lemma 34. Let Ci > C2 > be constants. Let f(x) = 1 (C1 + C2 log(1 + log for x > 0.
Then, is non-increasing on 2
Proof. Taking the derivative of f, we obtain that
C2
C1 O2 log(1
+ log
f(()) 1+log
x²
Note that the numerator is decreasing in æ, and when plugging in = 1, the numerator becomes C2 Ci < 0. Therefore, we have that f'(x: < 0 for all x 2 1.
Lemma 35 (Lemma 30 in Chen et al. (021)). Let C 2 0 be a constant and X be a random variable such that X < almost surely. Then, Var(X?) < 2 Var(X).
F CONCENTRATION INEQUALITIES
All the concentration inequalities used in the analysis are based on the following proposition, which derived by following the proof of Theorem (1.6) in Freedman (1975).
40

---

Published as a conference paper at ICLR 2025
Proposition 4. Let {X1][=1 be martingale difference sequence with respect to filtration (FilE-o- Suppose X₂ S 1 holds almost surely for all t 2 1. Let V2 == =i for t 2 and take À > 0 and ō E (0, arbitrarity. Then, the following inequality holds for all n N with probability at least 6:
d
1
Σ X
V2
log
(39)
X
Proof. Let M, exp( (X, ((e> -1 -)/A)vi)) for all n E N, where Mj 1. Corollary 1.4 (a) in Freedman (9955) states that [==g is supermartingale with respect to {F, ) By Ville's maximal inequality, we infer that P(supn20 Mn 2 1/8) S 8, which implics that P(Vn, Mn & 1/6) 2 d. Taking the logarithm on both sides and rearranging the terms, we check that Mn 1/5 5 is equivalent to inequality (3) completing the proof.
We mainly use the following two corollaries of Proposition 4 The first one has appeared in the literature several times (Beygelzimer et al. 201T Agarwal al. 2014 Xu & Zeevi 2020 Foster &
Rakhlin 2023).
Lemma 36. Let C > O be a constant and {x be a martingale difference sequence with respect to a filtration {Fi] with X, C almost surely for all E N. Then, for any X (0, 1] and d E (0, 1], the following inequality holds for all n E N with probability at least 1 - 6:
n
C
1 log 8
X.S
+
4C
Proof. For E (0, 1]. it holds that e² < x1+ (e 2) hence, = X,/C. Applying Proposition 4 on [X]]0= we obtain that
دداي- S (c (e- 2)). Let
X 1((x)) log
holds for all n E N with probability at least 1 - 8. Bounding e e 2 < 3/4 and multiplying both sides by C' completes the proof since CX₃ X, and CEE((X)) = F1-l/F-
The second corollary is a time-uniform version of Bernstein's 's inequality for martingales that incor- porates log log n factor instead of log n.
Lemma 37. Let {X be martingale difference sequence with respect to a filtration {F,) t-o- Assume that X, S holds almost surely for all t > 1. Let Tn = E' E[x? Fe-1) be the sum of conditional variances. Then, for any e > 0 and ō (0, the following inequality holds for all E N with probability at least 1 5:
max cf log 2(1 + log + (Tn/c))²
2(1 + log (og+(Tn/c)))
Σ Xx S 2//
+ log
8
3
t=1
where log* log( (omxx(1,4) 11,
Proof. Let [ be sequence that satisfies 0 < X < 3 for all j E N. We apply Proposition with X 4- Aj and 6 6/(2)²) for j E N. For tixed j. we have
- -i-
2j²
8
P
3n E N: Σ
log
X
25
Using the Taylor series expansion, verify that the following holds for 0 < X1 < 3:
eAs - - A1
k-1
Aj
k!
2 36-2
2(1 Aj
k=2
41

---

Published as a conference paper at ICLR 2025
Therefore, have that with probability at least 1 - 6/(2)2), the following inequality holds for all
n E N:
Aj
1
2j² 8
X1 S
T
+
log
(40)
2(1
A1 3
We take
log 2j²
Voe 1
V log 2
One can check that >3 < We have
log 2
Vce +
and
+
2
A
2V0
3
log 2f
Plugging in these values to inequality (40), we obtain the following inequality:
E 1=1
Tn 22/CE
+ V=e
log
2j²
+ log
1
2j² 8
(41)
8
3
Taking the union bound over j N and noting that ΣØ=1 27 holds for all j and for all n simultaneously with probability at least 5, which can be written in following equivalent form:
I 6, we obtain that inequality (41
P 3n ::N:::
Σ 1=1
X min
{
Ta 2/ + V
2j² log
log
2j² 8 so.
8 3
Now, we choose In for each E N and provide bound for the minimum. We define Ty max max(Tn, of and take jn 1 + [og((T//c)] Then, we have e imn /ec/Th, implying that
I v VT/e and
S
Tn
+ Vee"2" j-1
2j²
2j²
min JEN
log
+
log
2
I
3
To
2j
2
In-T + Vce"
log
log
cee
5
3
Tn
2j
1
2
+
TV
log
+ 3
log
2
Ty
21
21a
$ / TV log
log
8
3
8
where in the last inequality we apply T, S Ty and +1+1 2. Finally, noting that jn S + log(T", /c) 1 log (Tn/c), we obtain that the following incquality holds for all n N, with probability at least 1-d: d:
X 21 max cJ log 2(1 + log (Tn/c))² loog
2(1 + +lg llgggoon (Tn/c))²
8
8
G EXPERIMENT DETAILS
In this section, provide additional details for the experiments described in Section Specific transitions and reward functions the RiverSwim environment are depicted in Figure All param- eters set according to the algorithms' theoretical values described in their respective papers.
42

---

Published as a conference paper at ICLR 2025
For EQO, the parameters number of episodes. The algorithm UCRL2 modified to adapt to the episodic finite-horizon setting. We report the average cumulative regret and standard deviation over 10 runs of 100,000 episodes in Figure with the average execution time per run summarized Table
described in Theorem 2 where the algorithm is unaware of the
We observe the superior performance of EQO. When and H small, only ORLC shows competi- tive performance against EQO, but our algorithm outperforms ORLC by increasing margins as $ and H. grow. Especially in the case where S 40 and H 160, only our algorithm learns the MDP within the given number of episodes and achieves sub-linear cumulative regret. We also note that our algorithm takes less execution time.
0.4
0.6
0.6
0.6
0.35
Q
0.35
0.35
(1,-= 0.005) -
83
8n
(0.6, r =
0.05
0.05
0.05
0.4
Figure 2: The RiverSwim MDP with n states. The solid arrows and dashed arrows describe the state transitions of the "right" and "left"actions respectively with their probabilities labeled. X shows the reward of the state-action pair, where = 0 if not shown.
Table 4: Average execution time of each algorithm seconds.
S = 10
S S 20
S S 30
S = 40
Algorithm
H = 40
= 80
H = 120
= 160
UCRL2 JJkksch et al. 2010
1899.5
7298.9
17541.9
22594.3
UCBVI-BB BF (Azar et al.] (017))
699.0
2171.4
4439.3
6785.6
EULER (Zanette & Brunskin kill 2019)
991.0
2847.3
5643.7
8353.7
ORLC
(Dann et al.) 2019)
1219.4
3871.1
7408.7
11655.0
MVP
(Zhang et al.) 2021a)
523.4
2155.4
4106.5
6687.3
EQO (Ours)
535.2
1904.0
3847.1
6713.1
We report additional experiment results conducted under a MDP described in Figure of Dann et al. (202T). It is a deterministic MDP where the reward is given only for the last action. If the agent has followed the optimal policy until the penultimate time step, faces a state such that one action has an expected reward of 0.5 and the other has O. If the agent's 's actions deviate from optimal policy, then receives an expected reward of either 0 or & 0.02, depending on the final action. Refer to Appendix C in Dann al. (2021) for more details about the MDP. We report the average cumulative regret and standard deviation over 10 runs 500,000 episodes in Figure 4 UCRL is excluded due to its high computational cost under large state space. We also add a tuned version of EQO, highlighting its strength when the parameter is set appropriately. EQO with theoretical parameters outperforms all other algorithms except ORLC. When appropriately tuned, EQO incurs the smallest regret by significant margins. While it may be unfair to compare the results of the algorithms with and without the tuning of the parameters, the complicated structure of the bonus terms of ORLC. As presented in Algorithm 3 in Dann et al. (2019). the bonus terms of the algorithm utilize at least twenty terms estimate both upper and lower bounds of the optimal values, making it almost intractable to effectively tune the algorithm. For the other algorithms, their bonus terms also consist of multiple terms, being subject to the same problem. Only EQO offers comprehensive control over the algorithm through single parameter. What we highlight here is not only the empirical performance of EQO but also the simplicity of the algorithm that makes it extremely convenient tune.
draw the reader's attention to
'free- We conduct additional experiments in two more complex environments: Atari
way_10_fs300 (Bellemare al. 2013) and Minigrid 'MiniGrid- KeyorridorSRRR (Chevalier- Boisvert et al. 2023). We have obtained their tabularized versions from the BRIDGE dataset (Laid- law et al. 2023). Most Atari and MiniGrid environments are either too large in terms of the number
43

---

Published as a conference paper at ICLR 2025
UCRL2
+
+
EULER
+
+
+
(Ours)
x10
Riverswim 5=10, H=40
x10
Riverswim S=20, H-80
8.0
Cumulative Regret
3.0
Cumulaaiie Regret
6.0
2.0
4.0
0.0
0.2
0.4
0.6
0.8
1.0
0.0
0.2
0.4
0.6
0.8
1.0
Episodes
le5
Episodes
1e5
x10º
Riverswim S=30, H= 120
x10
Riverswim $=40, H=160
12.0
15.0
Cumulative Regret
Cumulative Regret
12.5
8.0
10.0
4.0
2.0
2.5
0.0
0.0
1.0
Episodes
le5
Episodes
1e5
Figure Cumulative regret under RiverSwim MDP with varying S and H.
UCBVI-BF
EULER
ORLC
I
MVP
EQO (Ours)
EOO Tuned (Ours)
Gap MDP, 16
Gap MDP, 32
2.0
2.0
Curulaatvv Regret
Cumulattio letive Regret
1.5
0.0
0.0
Episodes
1e5
Episodes
1e5
Figure 4: Cumulative regret under MDP described in Figure 2 of Dann et al. 202 with varying n.
of states to perform tabular learning or simple, where greedy policy performs best, diminishing
the purpose of comparing the efficiency of exploration strategies. These two specific environments
are selected from each group for their moderate sizes and complexities. Both MDPs have over 150 states and more than two actions, making them much more complex than the RiverSwim MDP. We note that instead of the conventional 25% chance of sticky actions (Machado al. 2018). we em- ploy 25% chance of random actions to preserve the Markov property.
We include PSRL (Osband et al., 2013), a randomized algorithm for tabular reinforcement learning, for more diverse comparison, while UCRL2 is excluded due to its high computational cost in large state spaces. We report the average cumulative regret and standard deviation over 10 runs of 5,000 episodes in Figure Considering these environments algorithm to achieve their best performance for each instance. For both settings, EQO consistently demonstrates competitive performance.
real-world-lit settings, tune each
44

---

Published as a conference paper at ICLR 2025
+
-
EULER
+
+ (Ours)
x10
Freeway H=10, S=198, A=3
x10 KeyCorridor H=20, S=169, A=6
1.6
1.0
1.4
Cumulative Regret
0.8
Cumulstive Regret
0.6
0.4
0.2
0.2
1000
2000
3000
4000
5000
1000
2000
3000
4000
5000
Episodes
Episodes
Figure 5: Cumulative regret under environments with larger state spaces.
Comparing with Bayesian algorithms. PSRL achieves a Bayesian regret guarantee for given prior distribution over the MDPs (Osband et al. 2013); however, the prior is available under the current experimental setting. While it is possible to construct an artificial prior, the performance of these algorithms depends on the prior; that is, they gain an advantage if the prior is informative. This makes it potentially unfair to compare them with algorithms that have frequentist regret guarantees, as the latter cannot use any prior information and must be more conservative. For example, RISVV, another randomized algorithm, requires constant-scale perturbations for a Bayesian guarantee (Os- band et al., 2016). However, the perturbations must be inflated by a factor of HSA to ensure frequentist regret bound (Zanette et al. 2020). Typically, the constant-scalee scaled version empirically performs much better for most reasonable MDPs.
One way make the comparison viable would be to tune the frequentist algorithms. As the pur- pose the experiment with the RiverSwim MDP is to compare the performance of algorithms with theoretical guarantees,
the parameters according to their theoretical values, and hence do not tune the parameters and cannot include PSRL for comparison (since it does not have theo- retical values for its parameters in this setting). In these two additional experiments, we consider their settings to be closer to real-world environments, where tuning the parameters becomes highly necessary. Therefore, we tune the algorithms and include PSRL. For EQO, tuning the algorithm is straightforward: treat C3 in Algorithm ass k-independent parameter as in Theorems I and and tune value. However, as mentioned earlier, the other algorithms have multiple terms with com- plicated structures as bonuses, and how they should be tuned is not clear. For the results of Figure a multiplicative factor for the whole bonus term set as a tuning parameter, therefore maintaining the same complexity EQO.
H EXPLOITING UNIFORM- SETTING
Although Assumption 1 generalizes the uniform-reward setting, algorithms may perform better when prior information that the reward at each time step at most available. Algorithm 3 describes how EQO may adapt to the uniform-rewart setting. We show that the theoretical guarantees enjoyed by Algorithm remain valid for Algorithm Junder the uniform-reward setting, and provide additional experimental results that compare the performance of the algorithms when all of them exploit the uniform reward structure. Our algorithm continues to exhibit its superiority over the other algorithms.
H.1 THEORETICAL GUARANTEES FOR UNIFORM-REWAN SETTING
In this subsection, rigorously demonstrate that under the sniform-rewarte setting, Algorithm enjoys the same theoretical guarantees as Theorems [ Set A as defined in each of the theorems and let d4 7 / At. that e, H Ck- We note that under this choice of parameters, the bonus
45

---

Published as a conference paper at ICLR 2025
Algorithm 3: EQO for Uniform-Reward Setting
Input: [x=
for k = 1,2,.... K do
Set N a). f* (s, and (5'1s, a) in Algorithm |
3
for h = H, 1,...,.,, do
foreach (s.a) E E do
(s, t ( - h (s,);
()) min (s, (s, PMV H - h+11 -1
if (s,
if N (s,a)
(s) + m (s, a) for all s E S:
(s) + argmax, 0 (s. a) for all 8 E S: Execute * and obtain - = (sf at. . sh a R #
term of Algorithm 3 is less than or equal to the bonus term of Algorithm I Therefore, the parts where we derive upper bounds for 6f (s, a) the analysis remain valid, and the only part where we need lower bounds for (s, a) is in the proof of Lemma where we show the quasi-optimism. We show that quasi-optimism holds under the different choice of bonus terms when the reward structure is uniform, which implies that Algorithm 3 enjooys the same theoretical guarantees.
First, the high-probability events of Lemmas 5 and 8 should be adjusted to the new bounds of Vh and R (s) is at most H - h + 1 for all 8 E S and R is at most 1. One can easily derive from the proofs that the inequalities of each lemma can be replaced with the following inequalities respectively:
(pp -P)iit 1x + H} 4(11 hh)
Var(Vi--)ss.c) 3(H ((H-1)61
-P- (5r 6(H -11-h)) -1 (*(,,a)
(*,,))) r(,,a) S Aer(s, + \s,a(s,,))
where we define ((h + the events of Lemmas 5 and are replaced by the events above.
h) to be 0 when h = H. Let E' be the counterpart of & such that
Now, we show that Algorithm enjoys quasi-optimism.
Lemma 38 (Quasi-optimism for Algorithm 3). Under El, it holds that for all S S, h E [H] and E N.
(s) Au - 11 (s).
Proof. We prove the following inequality by backward induction on h E [H + +1]
( 2(H--+1
(i) vZ)
(s) s A (v)
(VT)
It is easy to show that the inequality holds when / = H +1 or V/+ H h+ 1. Suppose h < H
and (s) < H + 1, and that the inequality holds for h + 1. Following the proof of Lemma with the refined concentration inequalities, we arrive at the following inequality:
V (s) (s) < (s, + (6(H h) 1)CIA + Apr(s,a") + 2A, 2V,
(s,")s,at)
1 (h + H} (Var(Vit)) P(Vi+t)
(42)
2(H h)
46

---

Published as a conference paper at ICLR 2025
We first note that as, 7(H 7(--1+1664
(x.N"(s,a") > (IH-A))1)612 therefore the sum of the first (x,""ssa"))
two terms is not greater than O. Now, we bound the last term. Note that (sr = - -PPV (8, (18,a))² non-positive, therefore we have that A (h # H) (Var(Vi+z))s,.f) ((Viit) 2(H h))
2(H h 1) (Var(V P(Vi+t) (o)
(43)
where the inequality also holds for h H as both sides are 0 in that case. Applying Lemma 27 obtain that
Var(V (*,
(v
+ 2(H - h 1)r(s,
(44)
Combining inequalities
42 1..4.. and 44), we conclude that
d
(s) (s) v Apr(s, 2 PV (
2(11 - h + (v)) + Axr(ssaa)
= Ax (v) 2(H - 11 + (V/ (v))
completing the induction argument.
H.2
ADDITIONAL EXPERIMENTS
E
UCBVI-BF E
EULER
I
ORLC
I
MVP
EQO (Ours)
x10
Riverswim 5-10, H-40
x10
Riverswim S-20, H-80
1.5
Cumulative Regret
Oumulative Regret
1.0
2.0
1.0
0.0
0.0
0.0
0.8
1.0
0.8
Episodes
le5
Episodes
le5
x10F
Riverswim S=30, H 120
x10
Riverswim 5=40, H
10.0
Cumulative Regret
Cumulaative Regret
12.5
8.0
10.0
7.5
2.5
0.0
0.0
0.2
0.4
0.6
0.8
1.0
0.0
0.2
0.4
0.6
0.8
1.0
Episodes
1e5
Episades
1e5
Figure 6: Cumulative regret of algorithms under the RiverSwim MDP with varying S and H. All algorithms are aware the uniform reward structure of the MDP.
We provide additional experimental results showing the performance of the algorithms when the uniform reward structure is exploited. Note that the RiverSwim MDP satisfies the uniform-rewan assumption. To fairly compare algorithms that are analyzed under more general assumptions, we adjust them according to the following criteria:
(a) If the algorithms clip the estimated values by H, we adjust it to h + 1, which the maximum possible value for any state at time step h.
47

---

Published as a conference paper at ICLR 2025
(b) If the algorithms have any terms proportional to H in their bonus, change them to H h, as is intuitive that the optimistic bonus term should not account for how many time steps have passed before the current step.
We note that in the experiment presented in Section 5 the algorithms are not allowed to exploit the uniform reward structure. Therefore, algorithms that originally exploit it underwent the opposite conversion for fair comparisons. We do not claim that these simple conversions ensure the validity of the analyses under the opposite assumptions. However, we believe that they are sufficient for numerical comparisons.
We display the results Figure 6 exclude UCRL2 as originally designed for MDPs without horizons, and could not find any straightforward conversions for it. With the additional informa- tion, all the algorithms exhibit significant improvements in their performance when compared with Figure We emphasize that algorithm continues demonstrate its superior performance the other algorithms.
48


Reviews:
[{"review_id": "whWVyEp658", "reviewer": "Reviewer_8Sjp", "summary": "The paper studies reinforcement learning in tabular finite-horizon MDPs. The authors introduce EQO (Exploration via Quasi-Optimism), a novel algorithm which is basically a variant of UCBVI with much simpler bonuses of the form b_k(s,a) = c / N_k(s,a) (ie not requiring any variance term and decaying at 1/k rate instead of 1/sqrt(k)). EQO is shown to be minimax optimal for both regret minimization and PAC identification of an epsilon-optimal policy. The main novelty in the analysis is a notion of \"quasi optimism\", which allows EQO to achieve strong theoretical guarantees despite not being exactly optimistic at every episode. On a simple numerical experiment, EQO outperforms existing baselines in terms of cumulative regret.", "questions": "1. What's the authors opinion about the impossibility of proving log(K) regret with EQO? Again, I am not 100% sure about it so I'd be happy to be proven wrong\n2. Is the assumption of time-homogeneous transition kernel important for the techniques developed here or could the proofs go through even with time-inhomogeneous dynamics?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. Making provably-efficient RL algorithms, even for the simplest setting of tabular MDPs, more practical is a relevant problem, and the paper makes a good contribution in this direction\n2. EQO achieves strong results despite its simplicity, which I think is a big plus\n3. I found the idea of \"quasi optimism\" novel and interesting. Most existing works do need \"strong\" optimism (ie Q functions are optimistic at any s,a,h,k) to derive theoretical guarantees, and it is good to see that this can be relaxed\n4. The paper is overall well written: the context is well motivated from the very beginning, sufficient intuition is given behind all results, and proofs/notation are clear (though I have to say that I only skimmed through the proofs quickly)\n5. Relaxing existing assumptions on reward/return/value distributions (Assumption 1 and 2) is also a relevant contribution (though I have never found them as limiting factors for existing approaches, but rather just tricks to simplify proofs/notation)", "weaknesses": "My main concern is about the way these novel bonuses are built: it seems that the price to pay for having b^k(s,a) decay as 1/N_k(s,a) is an inflation of the multiplicative constant (c_k) by a factor sqrt(K) or sqrt(k), whereas existing bonuses only have logarithmic dependences in this quantity. This may have a some important negative implications:\n1. If I am not mistaken, this will prevent deriving any sort of logarithmic (in K) / gap-dependent bound for the same algorithm, since a factor sqrt(K) in the regret may be unavoidable if forced into the confidence bonuses. If this is true, I think it is a quite big limitation, as one of the main directions to make these approaches \"practical\" is to show that they can adapt to the complexity of the specific MDP instance they face (mostly though logarithmic / gap-dependent bounds), instead of paying the cost of the hardest instance (which may not even be of practical relevance). \n2. There is a long line of works on instance-dependent results for regret minimization [1] and PAC RL [2,3,4,5] mostly studying algorithms that are quite similar to the baselines considered here. My concern is that the current algorithm cannot achieve results comparable to them, which means that comparing to existing baselines only in terms of worst-case results may not give a complete view of EQO's pros and cons. Also, in light of this, I feel that discussing literature on instance-dependent results is quite important, but at the moment all these papers are missing from the related literature\n3. This also break a bit the story about existing algorithms focusing only on minimax optimality. Eg the introduction states that \"Although provably efficient RL algorithms offer regret bounds that are nearly optimal (up to logarithmic or constant factors), they are often designed to handle worst-case scenarios. This focus on worst-case outcomes leads to overly conservative behavior\". But it is known that these algorithms can get guarantees which go beyond the minimax one, while (again, if the conjecture above is true) EQO may not. This would make EQO even more \"minimax-focused\" than existing literature.\n4. I was surprised to see EQO outperforming all existing baselines despite the sqrt(K) term in the confidence bounds. I wonder if the experiments focus too much on the \"low-K regime\", i.e., where the algorithms are still far from converging to a (near-) optimal policy and have to pay a sqrt(K) regret. I wonder what happens in the \"large-K regime\", where existing algorithms should essentially transition to logarithmic regret while the EQO should (probably) still suffer sqrt(K). Also, existing papers on instance-dependent RL show examples of MDPs where good adaptive algorithms would achieve sample-complexity/regret much smaller than minimax (eg when you have a very large sub-optimality gap in some state that allows the agent to quickly \"eliminate\" an entire branch of the MDP, see eg Figure 1 in [1]). I wonder how EQO compares to existing baselines on such \"favorable\" instances\n\nOther less important limitations:\n\n5. About the bound for best-policy identification (Theorem 4): one important thing to note is that the algorithm has no adaptive stopping criterion, which means that in practice we have to run it until K_0 to get the guarantee on the returned policy. That can be very conservative, as an algorithm with adaptive stopping may empirically take much less than the derived worst-case bound\n\n\n### REFERENCES\n\n\n[1] Dann, C., Marinov, T. V., Mohri, M., & Zimmert, J. (2021). Beyond value-function gaps: Improved instance-dependent regret bounds for episodic reinforcement learning. Advances in Neural Information Processing Systems, 34, 1-12.\n\n[2] Wagenmaker, A. J., Simchowitz, M., & Jamieson, K. (2022, June). Beyond no regret: Instance-dependent pac reinforcement learning. In Conference on Learning Theory (pp. 358-418). PMLR.\n\n[3] Tirinzoni, A., Al Marjani, A., & Kaufmann, E. (2022). Near instance-optimal pac reinforcement learning for deterministic mdps. Advances in neural information processing systems, 35, 8785-8798.\n\n[4] Wagenmaker, A., & Jamieson, K. G. (2022). Instance-dependent near-optimal policy identification in linear mdps via online experiment design. Advances in Neural Information Processing Systems, 35, 5968-5981.\n\n[5] Al-Marjani, A., Tirinzoni, A., & Kaufmann, E. (2023, July). Active coverage for pac reinforcement learning. In The Thirty Sixth Annual Conference on Learning Theory (pp. 5044-5109). PMLR.", "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": "4lepkCJFAW", "reviewer": "Reviewer_pA4T", "summary": "The authors proposed a novel algorithm for reinforcement learning in finite episodic MDPs based on the principle of Quasi-Optimism. In particular, they showed that simple exploration bonuses without any variance information can achieve the minimax optimal regret bound. Additionally, the method is easy to implement and shows good empirical performance.", "questions": "- Why the time-homogeneous setting was selected? What limits the application of these techniques to a time-inhomogeneous setting?\n- The experiments do not compare randomized exploration methods such as PSRL and RLSVI. Could you add these additional comparisons?\n- How does the regret bound change under the sparse regret setting $R^k_h \\leq 1$?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 4, "strengths": "- To my knowledge, it is the first result on a bonus-based RL algorithm that does not use variance information to achieve a minimax optimal regret bound. It is a major improvement over the prior work since, before, only posterior-sampling-based algorithms could achieve minimax optimal bound without the direct usage of the variance estimates (see, e.g., Tiapkin et al. 2022).\n\n\n\nTiapkin, D., Belomestny, D., Calandriello, D., Moulines, É., Munos, R., Naumov, A., ... & Ménard, P. (2022). Optimistic posterior sampling for reinforcement learning with few samples and tight guarantees. Advances in Neural Information Processing Systems, 35, 10737-10751.", "weaknesses": "- The algorithm cannot adapt to deterministic environments. In particular, the usage of variance information allows the Bernstein bonuses to become of order almost $H/N$ in the case of deterministic environments since the variance, in this case, will be learned to be zero. In contrast, the bonuses of the presented algorithm always have order $H\\sqrt{K}/N$, which is much larger than adaptive variance-dependent bonuses.\n- The main technical novelty presentation should be improved. In particular, I would prefer to see the full proof of quasi-optimism in the main text since it is the most insightful part of the paper that shows why the scaling of the additional term is $\\lambda_k H$ and not $\\lambda_k H^2$, how it may follow from a naive analysis that uses precisely the statement of Lemma 1 for the induction. In particular, very subtle work with variance and second moments looks to be a crucial part of the paper that allows the errors not to accumulate through the horizon, and this part should be acknowledged in the paper much better. I consider raising my score if the presentation of the proof in the main text shows this critical aspect.", "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": "1go4bVzgA8", "reviewer": "Reviewer_HgJ4", "summary": "This paper studies regret minimization in tabular RL. They propose an algorithm based on the principle of “quasi-optimism” that, rather than satisfying standard optimism, satisfies a relaxed version of optimism (their estimates are not truly optimistic, but deviate from optimism by a bounded amount). They show that this relaxation of optimism allows them to obtain the tightest known bounds on regret minimization in tabular RL (in the time homogeneous setting), while also simplifying the algorithm substantially as compared to existing optimal algorithms for tabular RL. Furthermore, they show that their algorithm leads to better empirical performance than all existing algorithms for tabular RL with theoretical guarantees.", "questions": "None.", "limitations": "", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "1. This paper introduces novel algorithmic and proof techniques for tabular RL, which allow it to obtain the tightest known bounds. As the majority of minimax optimal algorithms for tabular RL rely essentially on standard optimism, it was interesting to see these new techniques. In particular, the fact that you can achieve optimal regret without variance-dependent bonuses is surprising. I believe the insights and techniques presented here are a valuable and interesting contribution to the tabular RL literature. \n\n2. The simplicity of the algorithm is also very nice. The algorithms with the best known guarantees tend to be quite complex and it is not obvious that one can achieve optimality with a very simple algorithm. This paper demonstrates this is possible (and indeed, achieves bounds tighter than the previously best known bounds), which is an exciting conclusion.", "weaknesses": "1. The motivation for this paper could be cleaned up somewhat. It is motivated by saying that we want algorithms for tabular RL which are both theoretically optimal but also perform well practically, and that we don’t currently have this. To my knowledge, there are essentially no real-world applications of tabular RL, however; it is more of a theoretical exercise. I do not think this is an issue, but it would be better to not overstate the importance of having a practically useful algorithm (or better justification for why this is important should be given). \n\n2. Furthermore, I do not think the experimental results sufficiently validate the proposed algorithm’s practicallity or superior empirical performance over existing works. The algorithm is only validated on one environment (though the size and horizon are varied). If the authors want to convincingly make the argument that their approach yields better empirical performance, I would suggest benchmarking on additional environments (for example, those from the BRIDGE dataset of [1]). I do not think this is necessary—I think the theoretical results are sufficient on their own—I would just suggest toning down the claims on empirical performance without further experiments.\n\n3. It would also be nice to see an empirical comparison against a posterior sampling-style approach (e.g. the algorithm of [2]).\n\n4. I found the proof sketch in Section 4.4 to be fairly mechanical—some more intuitive explanation here would help elicit the key takeaways (for example it seems like the version of Freedman’s inequality here is playing a large role and giving an improvement over more traditional Bernstein-style bounds—this could be made more explicit).\n\nMinor typos:\n- Line 252: I believe there should be brackets around $c_k$.\n- Line 523: “that the our algorithm” -> “that our algorithm”.\n\n[1] Laidlaw, Cassidy, Stuart J. Russell, and Anca Dragan. \"Bridging rl theory and practice with the effective horizon.\" Advances in Neural Information Processing Systems 36 (2023): 58953-59007.\n\n[2] Osband, Ian, Daniel Russo, and Benjamin Van Roy. \"(More) efficient reinforcement learning via posterior sampling.\" Advances in Neural Information Processing Systems 26 (2013).", "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": "N7jP1TGVTO", "reviewer": "Reviewer_ud3P", "summary": "This paper studies the tabular MDP setting. They propose a new type of bonus for the UCRL algorithm, and prove that the regret of the algorithm matches the lower bound. They also show an upper bound to the PAC sample complexity, which matches to the lower bound as well.", "questions": "1. Is there any way we can tighten the low order term from $S^2A$ into $SA$ to match the lower bound?\n\n2. Can you obtain first order regret bound (regret bound in terms of $V^*$) and second order regret bound (regret bound in terms of $\\mathrm{Var}(V^*)$)?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. The paper is well written. The proofs are correct.\n\n2. The algorithms have regret which match the lower bound, and the algorithm is much simpler to those minimax optimal algorithms in previous literatures (e.g. [Azar et al,. 2017]) and do not need to estimate the variance explicitly.", "weaknesses": "1. In terms of the minimax optimality, this algorithm only matches the lower bound in the dominate terms. The low order terms does not match, while the regret of the algorithm in [1] matches the lower bound even for low order terms (the setting in [1] is time-inhomogenous, but the algorithm seems to work for time-homogenous setting as well)\n\n2. The bonus terms added in Algorithm 1 and Algorithm 2 seem to be similar to the bonus term in Eq. (4) in [2] and Theorem 2 and 3 in [3]. There is no comparison to these related works in the paper.\n\n3. The numerical experiments in this paper is only for the toy example. There is no experiments for real world applications.\n\n[1] Zhang, Zihan, et al. \"Settling the sample complexity of online reinforcement learning.\" The Thirty Seventh Annual Conference on Learning Theory. PMLR, 2024.\n\n[2] Simchi-Levi, David, Zeyu Zheng, and Feng Zhu. \"A Simple and Optimal Policy Design with Safety against Heavy-tailed Risk for Stochastic Bandits.\" arXiv preprint arXiv:2206.02969 (2022).\n\n[3] Simchi-Levi, David, Zeyu Zheng, and Feng Zhu. \"Regret distribution in stochastic bandits: Optimal trade-off between expectation and tail risk.\" arXiv preprint arXiv:2304.04341 (2023).", "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)