Policy Optimization Achieves Data-Dependent Regret Bounds in MDPs with Unknown Transitions

Unknown

Conceptio › Archive › arXiv CS

arXiv CSopen access

Policy Optimization Achieves Data-Dependent Regret Bounds in MDPs with Unknown Transitions

Unknown · 2026 · arxiv_cs

arXiv CS · Papers · License: Open Access · 2026

Open Source ↗Direct PDF ↓

machine learning, deep learning, neural networks

Policy Optimization Achieves Data-Dependent Regret Bounds in MDPs with Unknown Transitions

arXiv:2606.31769v1 [cs.LG] 30 Jun 2026

Mingyi Li Department of Mathematical Informatics, The University of Tokyo [email protected] Taira Tsuchiya Department of Mathematical Informatics, The University of Tokyo Center for Advanced Intelligence Project, RIKEN [email protected] Kenji Yamanishi Department of Mathematical Informatics, The University of Tokyo [email protected]

Abstract We study policy optimization for online episodic tabular Markov decision processes with unknown transition kernels, aiming for best-of-both-worlds guarantees together with data-dependent regret bounds. Recent work (Dann et al., 2023; Li et al., 2026) has shown that policy optimization can adapt to both adversarial and stochastic losses with first-order, second-order, and path-length bounds, but only under known transitions, leaving open whether such data-dependent guarantees are achievable by policy optimization when the transition kernel is unknown. We resolve this by developing a new algorithm based on optimistic follow-the-regularized-leader that attains these guarantees under unknown transitions. The key ingredient is a new design of optimistic Q-function estimators together with a data-dependent transition bonus that controls estimator bias through the loss-prediction error. Our analysis further identifies an unavoidable transition-dependent complexity term that captures the intrinsic cost of estimating the transition kernel. As a result, we obtain first-order, second-order, and path-length bounds with the transition-dependent complexity term while simultaneously achieving gap-dependent polylog(T ) regret in the stochastic regime.

Introduction

We study policy optimization for online finite-horizon episodic tabular Markov decision processes (MDPs) with unknown transitions. In this setting, the learner interacts with an MDP over T episodes. In each episode, the environment selects a loss function while the learner selects a policy. The learner then executes it and receives feedback on the loss function. The goal is to minimize the regret, the gap between the cumulative loss of the learner and that of the best fixed policy in hindsight. Policy optimization directly updates the policy and is a central paradigm in reinforcement learning (e.g., Schulman et al. 2015, 2017). For tabular MDPs, this approach updates a separate action distribution for each state (Shani et al., 2020; Luo et al., 2021), which is often more computationally efficient and practical than global optimization over the occupancy-measure space. The difficulty of tabular MDPs depends on √ how the loss sequence is generated. In the adversarial e T ) (Jin et al., 2020; Luo et al., 2021). In contrast, in the regime, the worst-case regret scales as O( Preprint.

Table 1: Comparison of regret upper bounds based on policy optimization. Here, Λ(π) = 1:T min{L(π), HT − L(π), Q∞ , V1 } is the loss-dependent complexity, Qπtrans (ℓ) is the transitionπ1:T dependent complexity satisfying E[Qtrans (ℓ)] ≤ H(L(π) + RegT (π)) for any policy π, and FO indicates that only first-order adaptivity is achieved. For the stochastic regime √ with adversarial corruption, we report only the leading term U in bounds of the form O(U + U C). Reference Luo et al. (2021) Dann et al. (2023, Theorem 4.2) Dann et al. (2023, Theorem 4.3) Li et al. (2026) This work (Theorem 4.1) This work (Theorem 4.2)

Adversarial regime √ e H 4 S 2 AT ) O( √ e H 4 S 2 AT ) O( p e H 2 SAL(π)) O( p e H 2 SAΛ(π)) O( p p 1:T e H 2 SAΛ(π) + S 2 AE[Qπtrans O( (ℓ)) p p 1:T e H 3 S 2 AΛ(π) + S 2 AE[Qπtrans O( (ℓ)])

Stochastic regime with adversarial corruption

– H 4 S 2 A log2 (T ) ∆min

P P s

Unknown transition

✓ ✓

H 2 log2 (T ) ∆(s,a) H 2 log2 (T ) a̸=π ⋆ (s) ∆(s,a) a̸=π ⋆ (s)

H 2 S 2 A log2 (T ) ∆min H 2 S 4 A log2 (T ) ∆min

Datadependent

Bandit feedback

✓ ✓ FO

✓

stochastic regime, one can often achieve much faster gap-dependent polylog(T ) regret (Simchowitz and Jamieson, 2019; Chen et al., 2025). This contrast has motivated best-of-both-worlds algorithms, which aim to achieve near-optimal guarantees in both the adversarial and stochastic regimes with a single algorithm (Jin and Luo, 2020; Jin et al., 2021; Dann et al., 2023). Beyond adapting to the underlying regime, another natural goal is to obtain regret bounds that scale with the difficulty of the realized loss sequence in the adversarial regime. Algorithms only with worst-case regret guarantees ignore the structure of losses and are often overly pessimistic in practical environments. Motivated by this, data-dependent bounds, such as first-order, second-order, and path-length bounds, have been actively studied in online learning, including prediction with expert advice and multi-armed bandits (Cesa-Bianchi et al., 1996; Allenberg et al., 2006; Neu, 2015; Wei and Luo, 2018; Bubeck et al., 2019). These depend, respectively, on the comparator’s cumulative loss, the magnitude of the loss fluctuations, and the temporal variation of the losses. Such data-dependent bounds have also been studied in episodic MDPs, but existing data-dependent guarantees in episodic MDPs are limited either in the algorithmic approach or in the transition model. Under unknown transitions, Lee et al. (2020) obtained a first-order bound, but only through occupancy-measure-based global optimization rather than policy optimization. For policy optimization, such data-dependent bounds have so far been obtained only under known transitions: Dann et al. (2023) established best-of-both-worlds guarantees with a first-order bound, and Li et al. (2026) provided algorithms achieving first-order, second-order, and path-length bounds simultaneously. Consequently, whether policy optimization can attain any data-dependent bound under unknown transitions, let alone combine first-order, second-order, and path-length adaptivity with best-of-bothworlds guarantees, was left open by Dann et al. (2023); Li et al. (2026). This raises the following question. Can policy optimization achieve data-dependent bounds such as first-order, second-order, and path-length bounds in episodic MDPs with unknown transitions? Contributions of this paper. We answer this question affirmatively by developing a policy optimization algorithm for episodic tabular MDPs with unknown transitions under bandit feedback, the harder setting in which the learner must estimate both the losses and the transition kernel from the realized trajectories. In the adversarial regime, its regret adapts to min{L(π), HT − L(π), Q∞ , V1 }, covering first-order, second-order, and path-length complexities, together with a 1:T transition-dependent complexity term Qπtrans (ℓ) in (2) that captures the intrinsic cost of estimating the transition kernel and can be connected to the first-order complexity L(π) (see Appendix B.2 for details). The same algorithm also enjoys gap-dependent polylog(T ) regret in the stochastic regime, achieving the best-of-both-worlds guarantee (see Theorem 4.2). To our knowledge, this is the first data-dependent guarantee for policy optimization under unknown transitions. It is worth noting that this is also the first algorithm for tabular MDPs achieving best-of-both-worlds and datadependent bounds simultaneously under unknown transitions. A detailed comparison with prior policy-optimization results is given in Table 1. As a by-product, our algorithm carries over to the easier full-information setting, where it retains these data-dependent and best-of-both-worlds guarantees and, in the worst case, recovers

√ e H 2 S 2 AT ) rate of occupancy-measure-based methods (Rosenberg and Mansour, 2019; Jin the O( et al., 2021) (see Theorem 4.1). This implies that the extra H factor often attributed to Q-function estimation is not inherent for policy optimization in the full-information setting under unknown transitions. Technically, our algorithms build on the optimistic follow-the-regularized-leader framework, with new prediction terms and optimistic Q-function estimators designed for unknown transitions tailored for each feedback setting (see Section 3). For the full-information setting, the Q-function estimator uses the most optimistic transition kernel in the confidence set. For the bandit setting, we incorporate a new data-dependent transition bonus defined in (12) and (13) into the Q-function estimator. This bonus keeps the Q-function estimator optimistic while reducing the estimator bias to the loss-prediction error, with the remaining worst-case terms contributing only lower-order terms. 1:T Our analysis identifies the new transition-dependent complexity term Qπtrans (ℓ), which captures the cost of estimating the unknown transition kernel. We show that this term is unavoidable under unknown transitions: even for a time-invariant loss sequence with Q∞ = V1 = 0, any algorithm still incurs regret from estimating the unknown transition kernel (see Proposition 4.3). This explains why data-dependent regret bounds under unknown transitions cannot be characterized solely by the loss-complexity measures used in the known-transition setting of Li et al. (2026). Due to space constraints, we defer a more detailed discussion of related work to Appendix B.1.

Preliminaries

Episodic tabular MDPs. We study an episodic tabular Markov decision process (MDP) M = (S, A, P, H, s0 ), where S is a finite state space with S = |S|, A is a finite action space with A = |A|, H is the horizon length, and s0 is the initial state. The transition kernel P is fixed but unknown to the learner. For each state-action pair (s, a), P (s′ | s, a) denotes the probability of moving to state s′ after taking action a in state s. We adopt the standard layered MDP assumption (Neu et al., 2010; Jin et al., 2020; Luo et al., 2021), where the state space is partitioned into H + 1 disjoint layers S0 , S1 , . . . , SH . Here, S0 = {s0 } is the initial layer and SH = {sH } is a terminal absorbing layer. For simplicity, we exclude sH from S, so that H ≤ S. Transitions occur only between consecutive layers. Specifically, for any (s, a) ∈ Sh × A with h ∈ {0, . . . , H − 1}, the distribution P (· | s, a) is supported on Sh+1 . We write h(s) for the layer index of state s. The learner interacts with the MDP for T episodes, indexed by t = 1, . . . , T . At the beginning of episode t, the environment selects a loss function ℓt : S × A → [0, 1]. The learner then selects a policy πt based on past observations, executes it from s0 under P , and incurs the losses along the realized trajectory. Here, a stochastic policy maps each state s to a distribution π(· | s) over actions, and for a deterministic policy π, we write π(s) ∈ A for its selected action at state s. At the end of the episode, the learner receives feedback on ℓt . In the full-information setting, the feedback is the entire loss function ℓt , whereas in the bandit setting, it is limited to the realized 1 losses {(st,h , at,h , ℓt (st,h , at,h ))}H−1 h=0 . We assume T ≥ max{2, S, A} for notational convenience. For a policy π and a loss function ℓ, the value functions are defined recursively, with terminal condition V π (sH ; ℓ) = 0. Specifically, the value function V π (s; ℓ) and the Q-function Qπ (s, a; ℓ) satisfy V π (s; ℓ) = Ea∼π(·|s) [Qπ (s, a; ℓ)] and Qπ (s, a; ℓ) = ℓ(s, a) + Es′ ∼P (·|s,a) [V π (s′ ; ℓ)]. We may overload notation by allowing any function g : S × A → R to play the role of the loss function, in which case V π (s; g) and Qπ (s, a; g) are defined accordingly. The goal is to minimize the regret PT PT RegT (π) := E t=1 V πt (s0 ; ℓt ) − t=1 V π (s0 ; ℓt ) against any fixed comparator policy π, and PT we denote by π̊ ∈ arg minπ E t=1 V π (s0 ; ℓt ) an optimal policy in hindsight. Additional notation. For N ∈ N, let [N ] := {1, . . . , N }, given a vector x, let ∥x∥p be its ℓp -norm for p ∈ [1, ∞], and for a scalar z, let [z]+ := max{z, 0}. For a set K, let ∆(K) denote the set of probability distributions over K. If f and g are functions with g(x) > 0, we write f ≲ g or f = O(g) e when f (x) ≤ cg(x) holds on the relevant domain for some universal constant c > 0, and use O(·) to hide logarithmic factors. Let {Ft }t≥0 be the natural filtration generated by all observations up to the end of episode t − 1, and define Et [·] = E[· | Ft ]. We use 1[·] for indicators, which equal 1 The assumptions T

≥ S and T ≥ A are not essential. If they fail, the analysis remains valid after replacing log(T ) with log(SAT ) or log(AT ).

1 on the event and 0 otherwise. Let It (s, a) = 1[(st,h , at,h ) = (s, a), ∃h ∈ {0, . . . , H − 1}] denote whether a state-action pair (s, a) is visited in episode t under policy πt and transition kernel P , P and let It (s) = a It (s, a). For each layer h, write ℓt (h) ∈ [0, 1]Sh ×A for the restriction of ℓt to Sh × A, and use the same convention for other functions on S × A. 2.1

Confidence sets of the transition

Following Jin et al. (2020), we construct confidence sets for the unknown transition kernel. Let nt (s, a, s′ ) be the number of observed transitions from (s, a) to s′ up to episode t−1, and let nt (s, a) be the corresponding visitation count. Whenever nt (s, a) = 0, we set it to 1 in any denominator. ′ ) The empirical transition estimate is then defined by Pbt (s′ | s, a) = nnt (s,a,s for all h and (s, a, s′ ) ∈ t (s,a) Sh × A × Sh+1 . The confidence set of the true transition at episode t is then defined as s ( Pbt (s′ | s, a)ι 14ι ′ ′ Pt = Pe : Pe(s | s, a) − Pbt (s | s, a) ≤ min 2 + ,1 , nt (s, a) 3nt (s, a) ) ′ ∀(s, a, s ) ∈ Sh × A × Sh+1 , ∀h = 0, . . . , H − 1, Pe(· | s, a) ∈ ∆(Sh+1 ). , (1) where ι = log(SAT /δ). Throughout the paper, we set δ = 1/T 2 . By Jin et al. (2020, Lemma 2), the true transition kernel P belongs to Pt for all episodes t = 1, . . . , T with probability at least 1 − 4δ. We note that the set Pt is rectangular, since its constraints are imposed independently for each state-action pair (s, a). For a transition kernel Pe and a policy π, let q P ,π (s, a) be the probability of visiting (s, a) within e e an episode. We also use q P ,π (s′ | s, a) and q P ,π (s′ , a′ | s, a) for the corresponding conditional occupancy measures given that (s, a) has been visited and set them to zero whenever h(s′ ) < h(s). P e e e e For each state s, define q P ,π (s) := a q P ,π (s, a), so that q P ,π (s, a) = q P ,π (s)π(a | s). When π Pe = P , we simply write q . We also define the upper and lower occupancies q πt (s) and q πt (s) with respect to the confidence set Pt , and for the learner’s policy πt , the smoothed occupancy qt (s) and relative occupancy width ρt (s) using an exploration rate γt > 0: e

q πt (s) := max q P ,π (s), q πt (s) := min q P ,π (s), qt (s) := q πt t (s) + γt , ρt (s) := e

e∈Pt P

qt (s) − q πt t (s) qt (s)

These quantities can be computed efficiently by the dynamic-programming procedure of Jin et al. (2020, Algorithm 3). Similarly, for any transition kernel Pe, policy π, and function g : S × A → R, e e we write V P ,π (s; g) and QP ,π (s, a; g) for the value and Q-functions computed under Pe and π. When Pe = P , we again omit the transition kernel and write V π (s; g) and Qπ (s, a; g). 2.2

Regime of environments

We consider three regimes for the loss sequence ℓ1 , . . . , ℓT . In the adversarial regime, we impose no assumption on the losses. At the beginning of each episode t, the environment selects an arbitrary loss function ℓt ∈ [0, 1]S×A , which may depend on the learner’s algorithm, as well as on past trajectories and observed losses, but not on the learner’s internal randomness. In the stochastic regime, the loss functions ℓ1 , . . . , ℓT are sampled i.i.d. from a fixed but unknown distribution D. The stochastic regime with adversarial corruption interpolates between these two settings. In this regime, there is an underlying (non-corrupted) loss sequence ℓ′1 , . . . , ℓ′T sampled i.i.d. from an unknown distribution D, while the learner observes a possibly corrupted loss sequence ℓ1 , . . . , ℓT . The corruptions may depend arbitrarily on the past trajectories and PT P observed losses, and H−1 their total magnitude is measured by C := E t=1 h=0 ∥ℓ′t (h)−ℓt (h)∥∞ ∈ [0, HT ]. When C = 0, this regime reduces to the stochastic regime; when C is arbitrary, it coincides with the adversarial regime. For the stochastic and corrupted stochastic regimes, let µ(s, a) := Eℓ′ ∼D [ℓ′ (s, a)] be the mean uncorrupted loss function. Assume that the optimal policy for µ is unique, and let it be denoted by π ⋆ . We define the suboptimality gap of a state-action pair (s, a) by ∆ : S × A → [0, H] ⋆ ⋆ as ∆(s, a) := Qπ (s, a; µ) − mina′ ∈A Qπ (s, a′ ; µ) and let ∆min := mins,a̸=π⋆ (s) ∆(s, a) > 0. 4

2.3

Complexity measures in online MDPs

We use the following data-dependent complexity measures to state refined The PT regret bounds. first-order quantity introduced by Lee et al. (2020) is L(π) := E t=1 V π (s0 ; ℓt ) , which is the cumulative loss of a fixed comparator policy π. The second-order quantity Q∞ := PT PH−1 2 minℓ⋆ ∈[0,1]S×A E t=1 h=0 ∥ℓt (h) − ℓ⋆ (h)∥∞ , which is small when the losses stay close to PT −1 a fixed baseline loss, and the path-length quantity V1 := E t=1 ∥ℓt+1 − ℓt ∥1 , which is small when the losses vary slowly over time, are defined as in Li et al. (2026). Under unknown transitions, our regret bounds contain a transition-dependent complexity term that reflects the difficulty of estimating the transition kernel. For a loss sequence ℓ = {ℓt }Tt=1 and a policy sequence π1:T = {πt }Tt=1 , define 1:T Qπtrans (ℓ) :=

sup

T X X

q πt (s, a)Vars′ ∼P (·|s,a) [V πt (s′ ; ϕt )] ∈ [0, H 2 T ].

(2)

∀t,s,a: |ϕt (s,a)|=ℓt (s,a) t=1 s,a

This quantity measures the variance of future cumulative losses across next states. Thus, transition πt ′ uncertainty affects regret only when possible next states have different values πV⋆ ′(s ; ϕt ). This mirrors transition-variance terms in stochastic MDPs, such as Vars′ ∼P (·|s,a) V (s ; µ) (Zanette and Brunskill, 2019; Simchowitz and Jamieson, 2019). Our definition replaces the optimal stochastic ⋆ value V π ( · ; µ) with learner-induced value functions so that the same idea applies to arbitrary loss sequences. As discussed later, this transition-dependent term is unavoidable under unknown transitions, since learning the transition kernel can itself cause regret even when Q∞ = V1 = 0. Furthermore, this term recovers a first-order regret bound through a self-bounding argument. In 1:T (ℓ)] ≤ H(L(π)+RegTp (π)), together with a regret bound of the form particular, the E[Qπtrans prelation π1:T RegT (π) ≲ E[Qtrans (ℓ)] + J, implies RegT (π) ≲ HL(π) + J. Thus, the transition-dependent complexity is at least as adaptive as the first-order complexity, while it can be sharper because it only counts transition uncertainty that affects future cumulative losses. We defer a detailed explanation and a simple illustrative example to Appendix B.2.

Algorithm and technical components

We are now ready to present our policy optimization algorithm for both the full-information and bandit settings. The common template is given in Algorithm 1, with the feedback-dependent definitions specified in Figure 1. Both algorithms follow the same policy optimization template and use new Q-function estimators and prediction terms to handle unknown transitions and adversarial losses. We describe the key components below. 3.1

Common policy optimization template

Optimistic follow-the-regularized-leader. Our algorithms rely on the optimistic follow-theregularized-leader (OFTRL) framework (Chiang et al., 2012; Rakhlin and Sridharan, 2013; Steinhardt and Liang, 2014), which incorporates a prediction of the next loss vector into the standard FTRL. Our policy update is based on the OFTRL policy-optimization scheme of Li et al. (2026), which was developed for known transitions, and we modify it to handle unknown transitions. Policy optimization reduces the MDP problem to a separate multi-armed bandit problem at each state. By the performance-difference lemma (Kakade and Langford, P 2002), the regret can be written P as RegT (π) = E s q π (s) t ⟨πt (· | s) − π(· | s), Qπt (s, · ; ℓt )⟩ . Thus, the Q-function plays the role of the loss vector for updating the action distribution at each state. Under unknown transitions, we first form the loss prediction mt ∈ [0, 1]S×A and then compute its Q-function using an optimistic transition kernel from the confidence set. The OFTRL update with a convex regularizer ψt is defined, for each state s ∈ S, by t−1 X Pm ,πt b t πt (· | s) = arg min π(· | s), Qτ (s, ·) − Bτ (s, ·) + Q (s, ·; mt ) + ψt (π(· | s)) . π(·|s)∈∆(A)

τ =1

(3)

b τ is a Q-function estimator, Bτ is a dilated exploration bonus, and QP t ,πt (s, ·; mt ) is Here, Q the optimistic prediction of Qπt (s, ·; ℓt ). The transition kernel P m t ∈ Pt is chosen to minimize e Pm t ,πt (s, ·; m ) are QP ,πt (s, a; mt ) over Pe ∈ Pt for each state-action pair (s, a). Both P m t t and Q computable by backward dynamic programming over the layers, since for s ∈ Sh , computing this Q-function only requires later-layer values and policies. In our algorithms, we use the log-barrier P 1 1 regularizer ψt (π(· | s)) = a∈A ηt (s,a) log π(a|s) , where ηt (s, a) > 0 are state-action-wise time-varying, data-dependent learning rates. In both the full-information and bandit settings, the b t , Bt , and ηt (s, a). algorithm uses the same update rule (3), and differs only in the construction of Q m

The optimistic prediction QP t ,πt (s, ·; mt ) is obtained from a loss prediction sequence mt . We construct mt from the realized trajectory, starting with m1 (s, a) = 1/2 for all (s, a) and setting (1 − ξ)mt (s, a) + ξℓt (s, a), if It (s, a) = 1, mt+1 (s, a) = (4) mt (s, a), if It (s, a) = 0, where ξ ∈ (0, 1/2) is a step size. Since the transition kernel is unknown, we use this predictor even in the full-information setting, where it is useful for deriving path-length bounds. Dilated exploration bonus. In policy optimization, a naive state-wise update of the action distributions can lead to insufficient exploration. To address this, Luo et al. (2021) introduced a dilated exploration bonus Bt (s, a), which is constructed in the same form as a Q-function, 1 ′ ′ Bt (s, a) = bt (s) + 1 + (5) max E ′ e ′ [Bt (s , a )]. ′ H Pe∈Pt s ∼P (·|s,a),a ∼πt (·|s ) Since Bt is subtracted from the Q-function estimator in (3), a state-action pair (s, a) with a larger dilated exploration bonus is evaluated more optimistically and is therefore more likely to be visited. This leads to the following lemma. Lemma 3.1 (Luo et al. 2021, Lemma B.2). Suppose that bt (s) is a nonnegative function. Suppose also that, for a comparator policy π, there exists J π ≥ 0 such that " # T X X X E q π (s) (πt (a | s) − π(a | s))(Qπt (s, a; ℓt ) − Bt (s, a)) s

t=1

# T 1 XXX π ≤J +E q (s)bt (s) + E q (s)πt (a | s)Bt (s, a) . (6) H t=1 s a t=1 s hP i B T P t ,πt Then, it holds that RegT (π) ≤ J π + 3 E (s0 ; bt ) + E HT 1[P ∈ / Pt , ∃t ∈ [T ]] , t=1 V π

" T XX

where P t ∈ Pt simultaneously attains the maxima in (5) for all (s, a). From this lemma, once the condition (6) is verified, it remains only to evaluate the value function B V P t ,πt (s0 ; bt ) of the bonus under the learner’s own policies πt , rather than a comparator policy π. For further intuition on the dilated bonus, we refer the reader to Luo et al. (2021); Dann et al. (2023). 3.2

Feedback-dependent Q-function estimator

The main new component is the Q-function estimator. The estimator differs between the fullinformation and bandit settings, and this choice also affects the learning-rate update and the local exploration bonus bt . We collect the definitions in Figure 1 and explain the idea below. Note that the quantities P ℓt , P m t , Bt , and Ct in Figure 1 are efficiently computable by backward dynamic programming with a state-action-wise greedy procedure over the confidence set, as in Jin et al. (2020); Luo et al. (2021). Full-information feedback. In the full-information setting, the learner observes the entire loss function ℓt after each episode, so the Q-function estimator can be formed directly from the entire e loss ℓt . We choose P ℓt ∈ Pt so that it minimizes QP ,πt (s, a; ℓt ) over Pe ∈ Pt for all state-action pairs (s, a), and design the new optimistic Q-function estimator by (7). On the event that P ∈ Pt for 6

Algorithm 1 Data-Dependent Policy Optimization with Unknown Transitions P 1 1 1 1 1 1 Input: γt = 1t , η1 = 12H 3 , m1 = 2 , ξ = 4 , ψt (π(· | s)) = a∈A ηt (s,a) log π(a|s) 2 for t = 1, 2, . . . do 3 Update Pt by (1). 4 For each s ∈ S, compute πt by the OFTRL update (3). √ 1 5 Set Yt ← 1 in the full-information setting, and Yt ← 1 maxs,a ηqt t(s,a) (s) ≤ 50 H 3 S 3 A in the bandit setting. 6 If Yt = 0, insert a virtual episode and shift the indices of real episodes. 7 If Yt = 1, execute πt , observe {(st,h , at,h )}H−1 h=0 , and receive the corresponding loss feedback. b 8 Compute Qt , ηt+1 , and bt as in Figure 1, and compute Bt by (5). 9 Compute loss prediction mt+1 (s, a) by (4). all t, this estimator is optimistic, and the resulting bias is one-sided. This is the only additional bias 1:T caused by unknown transitions, and it is controlled by the transition-dependent complexity Qπtrans (ℓ) in the regret analysis. The corresponding learning-rate update and local exploration bonus are given in (8) and (9). The update of the learning rate is designed so that the penalty term (1/ηt+1 (s, a) − 1/ηt (s, a)) log(T ) matches the stability term ηt (s, a)ζt (s, a), where ζt is defined in (10). Thus, both terms are controlled through the same data-dependent quantity ζt . The local exploration bonus bt is directly induced by this learning-rate update, with transition-estimation error included through ζt , so no separate transition bonus is needed in the full-information setting. Since the estimator uses the observed loss directly, the stability condition typically needed when analyzing OFTRL is easy to satisfy without introducing virtual episodes. Accordingly, Algorithm 1 sets Yt = 1 throughout the full-information setting. Bandit feedback. In the bandit setting, the learner observes losses only along the realized trajectory. To deal with this, our new Q-function estimator (11) therefore combines three ingredients: the m optimistic prediction QP t ,πt (s, a; mt ), estimator of the prediction-error Qπt (s, a; ℓt − mt ), and the transition bonus Ct (s, a). The main challenge is designing the transition bonus. It has to account for both loss-estimation error from bandit feedback and transition-estimation error from the unknown transition kernel. More precisely, the local transition bonus ct (s, a) must upper bound the estimator bias, while ct (s, a) itself remains controllable by data-dependent quantities. In particular, it should satisfy a relation of the form Et [ct (s, a)] ≥ ρt (s)|Qπt (s, a; ℓt − mt )| for all t, s, a. The simpler local transition bonus ct√ (s) = ρt (s)H used in Dann et al. (2023) controls the estimator bias only e T ) bound and thus does not yield the desired data-dependent bound. through a worst-case O( To tackle this challenge, we instead define the data-dependent local transition bonus ct (s, a) in (12) and its recursive version Ct (s, a) in (13), both constructed from the bandit feedback. The key point in our estimator is that, in the local transition bonus ct (s, a), the part that does not depend on the prediction error scales as ρt (s)2 rather than ρt (s). This makes the worst-case contribution of the estimator bias only polylog(T ), and the other terms can be bounded by data-dependent quantities. In m addition, we use the prediction term QP t ,πt (s, a; mt ), which is not automatically a lower estimate πt of Q (s, a; ℓt ), as also noted by Li et al. (2026). We therefore define Ct with an extra margin, so that the estimator remains optimistic without losing data-dependent control. The learning-rate update and local exploration bonus are given in (14) and (15). As in the fullinformation setting, the penalty term of regret (1/ηt+1 (s, a) − 1/ηt (s, a)) log(T ) is chosen to match the log-barrier stability term ηt (s, a)ζt (s, a)/qt (s)2 , where ζt is defined in (16). The local exploration bonus bt contains the term induced by this learning-rate update, together with an additional term involving Ct (s, a)2 , which accounts for transition-estimation error. Virtual episodes. In the bandit setting, Bt (s, a) can scale as 1/qt (s)2 through (15), so the resulting bonus-induced stability term cannot be controlled by the adaptive learning-rate update alone when qt (s) is small. Therefore, following Dann et al. (2023), √ we insert virtual episodes to control the ratio ηt (s, a)/qt (s). If maxs,a ηt (s, a)/qt (s) > 1/(50 H 3 S 3 A) at the beginning of episode t, we set

Full-information. Q-function estimator. ℓ

b t (s, a) = QP t ,πt (s, a; ℓt ) Q

with

P ℓt ∈ arg min QP ,πt (s, a; ℓt ) for all (s, a). e

(7)

e ∈Pt P

Learning rate and exploration bonus. ηt (s, a)ζt (s, a) 1 1 = + , (8) ηt+1 (s, a) ηt (s, a) log(T ) X 1 1 bt (s) = 7 − log(T ), (9) η (s, a) η (s, a) t+1 t a ℓ 2 X m where ζt (s, a) = πt (a | s)(1 − πt (a | s)) πt (b | s) QP t ,πt (s, b; ℓt ) − QP t ,πt (s, b; mt ) . (10) b

Bandit feedback. PH−1 P ′ ′ ′ ′ Q-function estimator. Let Lt,h = H−1 h′ =h mt (st,h , at,h ), and Dt,h = h′ =h ℓt (st,h , at,h ), Mt,h = PH−1 ′ ′ ′ ′ h′ =h |ℓt (st,h , at,h ) − mt (st,h , at,h )|, and define It (s, a) Lt,h(s) − Mt,h(s) Pm ,πt t b Qt (s, a) = Q (s, a; mt ) + Yt − Ct (s, a)Yt , (11) qt (s)πt (a | s) where

ct (s, a) = ρt (s)

It (s, a)Dt,h(s) + ρt (s)2 H, qt (s)πt (a | s)

(12)

Ct (s, a) = ct (s, a) + max Es′ ∼Pe (·|s,a), a′ ∼πt (·|s′ ) ct (s′ , a′ ) + Ct (s′ , a′ ) .

(13)

e ∈Pt P

Learning rate and exploration bonus. Let (s†t , a†t ) be any maximizer of ηt (s, a)/qt (s), and define  t (s,a)  1 + ηt (s,a)ζ , if t is a real episode, 2 ηt (s,a) 1 ) qt (s) log(T † † = 1 {(st ,at )=(s,a)} 1  ηt+1 (s, a) 1 + 324H log(T ) , if t is a virtual episode, ηt (s,a) X X 1 1 − log(T ) + 3 bt (s) = 6 ηt (s, a)πt (a | s)2 Ct (s, a)2 Yt , η (s, a) η (s, a) t+1 t a a 2 where ζt (s, a) = (It (s, a) − πt (a | s)It (s))2 Lt,h(s) − Mt,h(s) .

(14)

(15) (16)

b t , the learning-rate update ηt+1 , and the local Figure 1: Definitions of the Q-function estimator Q exploration bonus bt used in Algorithm 1. Yt = 0, make episode t virtual, and shift the indices of all subsequent real episodes. The algorithm then uses the zero loss function and only updates the pair (s†t , a†t ) ∈ arg maxs,a ηt (s, a)/qt (s), b t , bt , and Bt , but keeps the prediction multiplying 1/ηt (s†t , a†t ) by 1+ 324H 1log(T ) . It still computes Q mt and the confidence set Pt unchanged. Since the number of virtual episodes is O(HSA log2 (T )), their effect is lower-order, and we still use T to denote the total number of episodes.2

Main results

Regret upper bounds. We now state the guarantees of Algorithm 1. The first theorem is for the full-information setting, and the second is for the bandit setting. In both cases, the algorithm achieves first-order, second-order, and path-length bounds in the adversarial regime, and at the same time achieves a gap-dependent polylog(T ) bound in the stochastic regime. The transition-dependent 1:T complexity Qπtrans (ℓ) captures transition uncertainty that affects future cumulative losses and can imply first-order dependence on L(π) through self-bounding. 2 The data-dependent complexity measures in the main statements are defined only over real episodes.

Theorem 4.1. In the full-information setting, for any comparator policy π, Algorithm 1 guarantees q RegT (π) ≲ H 2 SA log2 (T ) min{L(π), HT − L(π), Q∞ , V1 } q 3 1:T (ℓ)] + HS 3 A 2 log2 (T ). + S 2 A log2 (T )E[Qπtrans Under the stochastic regime with adversarial corruption, it simultaneously ensures RegT (π) ≲ √ 2 2 3 log2 (T ) . U + U C + HS 3 A 2 log2 (T ), where U = H S ∆Amin √ e H 2 S 2 AT ) worst-case rate of occupancy-measure-based algoThe above bound recovers the O( rithms (Rosenberg and Mansour, 2019; Jin et al., 2021). To our knowledge, this is the first policyoptimization result to remove the extra H factor (Luo et al., 2021; Dann et al., 2023). In the stochastic regime, the leading gap-dependent term also has sharper dependence on H, S, and A than that of Jin et al. (2021), up to logarithmic factors. Theorem 4.2. In the bandit setting, for any comparator policy π, Algorithm 1 guarantees q RegT (π) ≲ H 3 S 2 A log2 (T ) min{L(π), HT − L(π), Q∞ , V1 } q 3 7 3 1:T (ℓ)] + H 2 S 2 A 2 log2 (T ). + S 2 A log2 (T )E[Qπtrans Under the stochastic regime with adversarial corruption, it simultaneously ensures RegT (π) ≲ √ 2 4 7 3 3 log2 (T ) . U + U C + H 2 S 2 A 2 log2 (T ), where U = H S ∆Amin In the worst case, the bound for the adversarial regime recovers the worst-case rate of Dann et al. 1:T (2023). For the first-order bound, the Qπtrans (ℓ) term is absorbed by the first-order term through the self-bounding argument. Thus, the final bound does not contain an explicit transition-dependent term. In the stochastic regime, the gap-dependent term incurs an additional factor S 2 /H 2 compared with Dann et al. (2023) due to the transition bonus, and whether this dependence can be improved remains open. However, the main contribution of Theorems 4.1 and 4.2 is their data-dependent regret bounds under unknown transitions. Together, these theorems give the first policy-optimization guarantees under unknown transitions with first-order, second-order, and path-length adaptivity. Lower bounds. We show that the data-dependent terms in our adversarial guarantees cannot be avoided in general. First, by running a standard hard instance for adversarial MDPs with unknown transitions (Jin et al., 2018; Domingues et al., 2021) for the first T ′ ≤ T episodes and setting all ′ ′ later losses to zero, the complexities satisfy L(π) = O(HT ′ ), Q √∞ = O(HT ), V1 = O(SAT ), π1:T 2 ′ 2 ′ and E[Q T ), while maxπ RegT (π) ≥ p Ω( H SAT ). Thus, one can obptrans (ℓ)] = O(H √ √ 1:T tain Ω( HSAL(π)), Ω( HSAQ∞ ), Ω( H 2 V1 ) and Ω( SAE[Qπtrans (ℓ)]) for the adversarial regime. Closing the remaining gaps is not specific to our data-dependent setting, and remains open even for worst-case policy optimization (Luo et al., 2021). The following proposition further shows that a transition-dependent term is necessary under unknown transitions. This follows from the lower-bound constructions of Jin et al. (2018, Theorem 3) and Domingues et al. (2021, Theorem 9) use time-invariant loss sequences, so the regret arises solely from transition uncertainty. Proposition 4.3. There exists an episodic MDP with unknown transitions and a time-invariant loss √ sequence such that Q∞ = V1 = 0, while any algorithm suffers maxπ RegT (π) = Ω( H 2 SAT ). This lower bound holds even under full-information feedback.

Proof overview

We sketch the proof for the bandit setting, which contains the main ideas also used in the fullinformation setting. The complete proofs are deferred to Appendix F for the full-information setting and Appendix G for the bandit setting. We use Lemma 3.1 as the main reduction for policy optimization. Recall that once the inequality in (6) is verified, the lemma reduces the regret B PT analysis to bounding t=1 V P t ,πt (s0 ; bt ). We prove (6) by decomposing its left-hand side into

P E s q π (s)(regπ (s) + biasπ (s) + errorπ (s)) , where regπ (s) =

X b t (s, a)−Bt (s, a) , (πt (a | s)−π(a | s)) Q

t,a X b t (s, a)+QP m t ,πt (s, a; m )−Qπt (s, a; m ) , bias (s) = (πt (a | s)−π(a | s)) Qπt (s, a; ℓt )− Q t t π

t,a X m error (s) = (πt (a | s)−π(a | s)) Qπt (s, a; mt )−QP t ,πt (s, a; mt ) . π

t,a π

Here, bias (s) is the estimator bias, while errorπ (s) comes from evaluating the prediction using π Pm t instead of the true transition kernel. The standard analysis in Lemma G.7 bounds reg (s) as " T # " # T X 1 XX π 2 E[reg (s)] ≤ O HS A log(T ) + E πt (a | s)Bt (s, a) . bt (s) + E H t=1 a t=1 The remaining terms are controlled in Lemmas G.8 and G.9 by v # " " # u X X X u e π etH 2 S 2 Aι2 E q πt (s, a) max QP ,πt (s, a; (ℓt − mt )2 ) , E q π (s)bias (s) ≲ O s

t:Y =1 s,a

t " # p X 1:T e E q π (s)errorπ (s) ≲ O S 2 Aι2 E[Qπtrans (m)] .

e∈Pt P

The key point is that biasπ (s) is reduced to the prediction error ℓt − mt . This follows from the 2 design of cP t (s, a), where P the part independent of the prediction error scales with ρt (s) rather than ρt (s), and t:Yt =1 s q πt (s)ρt (s)2 is only polylogarithmic in T (see Lemma G.5). The error term 1:T 1:T 1:T 1:T is captured by Qπtrans (m), which can be reduced to Qπtrans (ℓ) through Qπtrans (m) ≤ 2Qπtrans (ℓ) + P 2 πt 2H t:Yt =1 V (s0 ; (ℓt −mt ) ) in Lemma D.12. Thus, all remaining terms reduce to the prediction 1:T error ℓt − mt and Qπtrans (ℓ), yielding the desired first-order, second-order, and path-length bounds. For the stochastic regime with adversarial corruption, we use the same decomposition as above. We show in Lemmas terms can be bounded by factors of the form q PG.8 and G.9 that theqindividual P P P P π t E t:Yt =1 q (s, a) or E t:Yt =1 s,a [q πt (s, a) − q π̊ (s, a)]+ . These quans a̸=π ⋆ (s) tities are then controlled by a self-bounding argument following Dann et al. (2023), yielding the desired gap-dependent bound under adversarial corruption.

Conclusion

In this work, we resolved the open problem raised by Dann et al. (2023) on data-dependent regret bounds for policy optimization in MDPs with unknown transitions. Our algorithms achieve refined best-of-both-worlds guarantees, adapting to L(π), Q∞ , and V1 in the adversarial regime while attaining a gap-dependent polylog(T ) bound in the stochastic regime with adversarial corruption. A natural future direction is to obtain variance-aware gap-dependent bounds as in Chen et al. (2025), and to investigate whether the refined data-dependent guarantees can be achieved under aggregate feedback.

Acknowledgements TT is supported by JSPS KAKENHI Grant Number JP26K21297 and KY is partially supported by JSPS KAKENHI Grant Number JP24H00703.

References Chamy Allenberg, Peter Auer, László Györfi, and György Ottucsák. Hannan consistency in on-line learning in case of unbounded losses under partial monitoring. In International Conference on Algorithmic Learning Theory, pages 229–243. Springer, 2006. 10

Jean-Yves Audibert, Rémi Munos, and Csaba Szepesvári. Tuning bandit algorithms in stochastic environments. In Algorithmic Learning Theory, pages 150–165. Springer Berlin Heidelberg, 2007. Peter Auer and Chao-Kai Chiang. An algorithm with nearly optimal pseudo-regret for both stochastic and adversarial bandits. In 29th Annual Conference on Learning Theory, volume 49, pages 116–120. PMLR, 2016. Peter Auer, Nicoló Cesa-Bianchi, Yoav Freund, and Robert E Schapire. The nonstochastic multiarmed bandit problem. SIAM Journal on Computing, 32(1):48–77, 2002. Mohammad Gheshlaghi Azar, Ian Osband, and Rémi Munos. Minimax regret bounds for reinforcement learning. In Proceedings of the 34th International Conference on Machine Learning, volume 70, pages 263–272. PMLR, 2017. Sébastien Bubeck, Yuanzhi Li, Haipeng Luo, and Chen-Yu Wei. Improved path-length regret bounds for bandits. In Proceedings of the Thirty-Second Conference on Learning Theory, volume 99, pages 508–528. PMLR, 2019. Sébastien Bubeck and Aleksandrs Slivkins. The best of both worlds: Stochastic and adversarial bandits. In Proceedings of the 25th Annual Conference on Learning Theory, volume 23, pages 42.1–42.23. PMLR, 2012. Nicolo Cesa-Bianchi, Philip M Long, and Manfred K Warmuth. Worst-case quadratic loss bounds for prediction using linear functions and gradient descent. IEEE Transactions on Neural Networks, 7(3):604–619, 1996. Shulun Chen, Runlong Zhou, Zihan Zhang, Maryam Fazel, and Simon Shaolei Du. Sharp gapdependent variance-aware regret bounds for tabular MDPs. In Advances in Neural Information Processing Systems, volume 38. Curran Associates, Inc., 2025. Chao-Kai Chiang, Tianbao Yang, Chia-Jung Lee, Mehrdad Mahdavi, Chi-Jen Lu, Rong Jin, and Shenghuo Zhu. Online optimization with gradual variations. In Proceedings of the 25th Annual Conference on Learning Theory, volume 23, pages 6.1–6.20. PMLR, 2012. Christoph Dann, Teodor Vanislavov Marinov, Mehryar Mohri, and Julian Zimmert. Beyond valuefunction gaps: Improved instance-dependent regret bounds for episodic reinforcement learning. Advances in Neural Information Processing Systems, 34:1–12, 2021. Christoph Dann, Chen-Yu Wei, and Julian Zimmert. Best of both worlds policy optimization. In International Conference on Machine Learning, pages 6968–7008. PMLR, 2023. Omar Darwiche Domingues, Pierre Ménard, Emilie Kaufmann, and Michal Valko. Episodic reinforcement learning in finite MDPs: Minimax lower bounds revisited. In Proceedings of the 32nd International Conference on Algorithmic Learning Theory, volume 132, pages 578–598. PMLR, 2021. Eyal Even-Dar, Sham M Kakade, and Yishay Mansour. Online Markov decision processes. Mathematics of Operations Research, 34(3):726–736, 2009. Elad Hazan and Satyen Kale. Better algorithms for benign bandits. Journal of Machine Learning Research, 12(35):1287–1311, 2011. Shinji Ito. Parameter-free multi-armed bandit algorithms with hybrid data-dependent regret bounds. In Proceedings of Thirty Fourth Conference on Learning Theory, volume 134, pages 2552–2583. PMLR, 2021. Shinji Ito, Taira Tsuchiya, and Junya Honda. Adversarially robust multi-armed bandit algorithm with variance-dependent regret bounds. In Conference on Learning Theory, pages 1421–1422. PMLR, 2022. Shinji Ito, Kevin Jamieson, Haipeng Luo, Arnab Maiti, and Taira Tsuchiya. Adapting to stochastic and adversarial losses in episodic MDPs with aggregate bandit feedback. In Advances in Neural Information Processing Systems, volume 38. Curran Associates, Inc., 2025. 11

Thomas Jaksch, Ronald Ortner, and Peter Auer. Near-optimal regret bounds for reinforcement learning. Journal of Machine Learning Research, 11(51):1563–1600, 2010. Chi Jin, Zeyuan Allen-Zhu, Sebastien Bubeck, and Michael I Jordan. Is Q-learning provably efficient? In Advances in Neural Information Processing Systems, volume 31, pages 4863–4873. Curran Associates, Inc., 2018. Chi Jin, Tiancheng Jin, Haipeng Luo, Suvrit Sra, and Tiancheng Yu. Learning adversarial Markov decision processes with bandit feedback and unknown transition. In Proceedings of the 37th International Conference on Machine Learning, volume 119, pages 4860–4869. PMLR, 2020. Tiancheng Jin and Haipeng Luo. Simultaneously learning stochastic and adversarial episodic MDPs with known transition. In Advances in Neural Information Processing Systems, volume 33, pages 16557–16566. Curran Associates, Inc., 2020. Tiancheng Jin, Longbo Huang, and Haipeng Luo. The best of both worlds: stochastic and adversarial episodic MDPs with unknown transition. In Advances in Neural Information Processing Systems, volume 34, pages 20491–20502. Curran Associates, Inc., 2021. Tiancheng Jin, Junyan Liu, Chloé Rouyer, William Chang, Chen-Yu Wei, and Haipeng Luo. Noregret online reinforcement learning with adversarial losses and transitions. In Advances in Neural Information Processing Systems, volume 36, pages 38520–38585. Curran Associates, Inc., 2023. Sham Kakade and John Langford. Approximately optimal approximate reinforcement learning. In Proceedings of the Nineteenth International Conference on Machine Learning, pages 267–274, 2002. Tal Lancewicki and Yishay Mansour. Near-optimal regret using policy optimization in online MDPs with aggregate bandit feedback. In Proceedings of the 42nd International Conference on Machine Learning, volume 267, pages 32467–32491. PMLR, 2025. Chung-Wei Lee, Haipeng Luo, Chen-Yu Wei, and Mengxiao Zhang. Bias no more: high-probability data-dependent regret bounds for adversarial bandits and mdps. In Advances in Neural Information Processing Systems, volume 33, pages 15522–15533. Curran Associates, Inc., 2020. Mingyi Li, Taira Tsuchiya, and Kenji Yamanishi. Data- and variance-dependent regret bounds for online tabular MDPs. In International Conference on Machine Learning, 2026. Nick Littlestone and Manfred K Warmuth. The weighted majority algorithm. Information and Computation, 108(2):212–261, 1994. Haipeng Luo, Chen-Yu Wei, and Chung-Wei Lee. Policy optimization in adversarial MDPs: Improved exploration via dilated bonuses. In Advances in Neural Information Processing Systems, volume 34, pages 22931–22942. Curran Associates, Inc., 2021. Saeed Masoudian and Yevgeny Seldin. Improved analysis of the Tsallis-INF algorithm in stochastically constrained adversarial bandits and stochastic bandits with adversarial corruptions. In Proceedings of Thirty Fourth Conference on Learning Theory, volume 134, pages 3330–3350. PMLR, 2021. Gergely Neu. First-order regret bounds for combinatorial semi-bandits. In Proceedings of the 28th Conference on Learning Theory, volume 40, pages 1360–1375. PMLR, 2015. Gergely Neu, András György, and Csaba Szepesvári. The online loop-free stochastic shortest-path problem. In Proceedings of the 23rd Conference on Learning Theory, pages 231–243, 2010. Alexander Rakhlin and Karthik Sridharan. Online learning with predictable sequences. In Proceedings of the 26th Annual Conference on Learning Theory, volume 30, pages 993–1019. PMLR, 2013. Aviv Rosenberg and Yishay Mansour. Online convex optimization in adversarial Markov decision processes. In Proceedings of the 36th International Conference on Machine Learning, volume 97, pages 5478–5486. PMLR, 2019.

John Schulman, Sergey Levine, Pieter Abbeel, Michael Jordan, and Philipp Moritz. Trust region policy optimization. In Proceedings of the 32nd International Conference on Machine Learning, volume 37, pages 1889–1897. PMLR, 2015. John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms. arXiv preprint arXiv:1707.06347, 2017. Yevgeny Seldin and Gábor Lugosi. An improved parametrization and analysis of the EXP3++ algorithm for stochastic and adversarial bandits. In Proceedings of the 2017 Conference on Learning Theory, volume 65, pages 1743–1759. PMLR, 2017. Yevgeny Seldin and Aleksandrs Slivkins. One practical algorithm for both stochastic and adversarial bandits. In Proceedings of the 31st International Conference on Machine Learning, volume 32, pages 1287–1295. PMLR, 2014. Lior Shani, Yonathan Efroni, Aviv Rosenberg, and Shie Mannor. Optimistic policy optimization with bandit feedback. In Proceedings of the 37th International Conference on Machine Learning, volume 119, pages 8604–8613. PMLR, 2020. Max Simchowitz and Kevin G Jamieson. Non-asymptotic gap-dependent regret bounds for tabular MDPs. In Advances in Neural Information Processing Systems, volume 32, pages 1153–1162. Curran Associates, Inc., 2019. Jacob Steinhardt and Percy Liang. Adaptivity and optimism: An improved exponentiated gradient algorithm. In Proceedings of the 31st International Conference on Machine Learning, volume 32, pages 1593–1601. PMLR, 2014. Daniil Tiapkin, Evgenii Chzhen, and Gilles Stoltz. Narrowing the gap between adversarial and stochastic MDPs via policy optimization. In The 28th International Conference on Artificial Intelligence and Statistics, 2025. Chen-Yu Wei and Haipeng Luo. More adaptive algorithms for adversarial bandits. In Proceedings of the 31st Conference On Learning Theory, volume 75, pages 1263–1291. PMLR, 2018. Haike Xu, Tengyu Ma, and Simon Du. Fine-grained gap-dependent bounds for tabular MDPs via adaptive multi-step bootstrap. In Proceedings of Thirty Fourth Conference on Learning Theory, volume 134, pages 4438–4472. PMLR, 2021. Jia Yuan Yu, Shie Mannor, and Nahum Shimkin. Markov decision processes with arbitrary reward processes. In Recent Advances in Reinforcement Learning, pages 268–281. Springer Berlin Heidelberg, 2008. Andrea Zanette and Emma Brunskill. Tighter problem-dependent regret bounds in reinforcement learning without domain knowledge using value function bounds. In International Conference on Machine Learning, pages 7304–7312. PMLR, 2019. Alexander Zimin and Gergely Neu. Online learning in episodic Markovian decision processes by relative entropy policy search. In Advances in Neural Information Processing Systems, volume 26, pages 1583–1591. Curran Associates, Inc., 2013. Julian Zimmert and Yevgeny Seldin. Tsallis-INF: An optimal algorithm for stochastic and adversarial bandits. Journal of Machine Learning Research, 22(28):1–49, 2021. Martin Zinkevich. Online convex programming and generalized infinitesimal gradient ascent. In the Twentieth International Conference on Machine Learning, pages 928–935, 2003.

Contents 1

Introduction

Preliminaries

2.1

Confidence sets of the transition . . . . . . . . . . . . . . . . . . . . . . . . . . .

2.2

Regime of environments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2.3

Complexity measures in online MDPs . . . . . . . . . . . . . . . . . . . . . . . .

Algorithm and technical components

3.1

Common policy optimization template . . . . . . . . . . . . . . . . . . . . . . . .

3.2

Feedback-dependent Q-function estimator . . . . . . . . . . . . . . . . . . . . . .

Main results

Proof overview

Conclusion

A Summary of notation

B Additional related work and discussion

B.1 Additional related work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

B.2 Discussion of the transition-dependent complexity . . . . . . . . . . . . . . . . . .

C High probability event

D Auxiliary lemmas

D.1 Technical lemmas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

D.2 Data-dependent and self-bounding lemmas . . . . . . . . . . . . . . . . . . . . . .

E General lemma of optimistic follow-the-regularized-leader

F Regret analysis for the full-information setting (Theorem 4.1)

F.1

Auxiliary lemmas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

F.2

Common regret analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

F.3

Proof for the adversarial regime . . . . . . . . . . . . . . . . . . . . . . . . . . .

F.4

Proof for the stochastic regime with adversarial corruption . . . . . . . . . . . . .

G Regret analysis for the bandit setting (Theorem 4.2)

G.1 Auxiliary lemmas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

G.2 Common regret analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

G.3 Proof for the adversarial regime . . . . . . . . . . . . . . . . . . . . . . . . . . .

G.4 Proof for the stochastic regime with adversarial corruption . . . . . . . . . . . . .

Summary of notation

For the reader’s convenience, Table 2 collects the main notation used throughout the paper. Table 2: Summary of notation. Symbol

Meaning

Tabular MDPs M = (S, A, P, H, s0 ) S, S A, A P H T h(s) st,h , at,h ℓt (s, a) πt RegT (π) It (s, a) nt (s, a) V π (s; ℓ) Qπ (s, a; ℓ) q π (s), q π (s, a) q π (s′ , a′ | s, a) π̊ ℓ′t (s, a) C µ(s, a) π⋆ ∆(s, a), ∆min

Episodic tabular MDP State space and its size S = |S| Action space and its size A = |A| Transition kernel Horizon length Number of episodes Layer index of state s State / action at step h in episode t Loss assigned to (s, a) in episode t Policy in episode t Regret over T episodes with comparator π Visitation indicator of (s, a) in episode t Number of visits to (s, a) up to episode t − 1 Value function under policy π from state s with loss ℓ Q-function under policy π from (s, a) with loss ℓ Occupancy measure under policy π Conditional occupancy from (s, a) to (s′ , a′ ) under π Optimal policy for the regret Uncorrupted i.i.d. loss Corruption budget Mean of ℓ′t (s, a) Optimal deterministic policy under µ Suboptimality gap at (s, a), and minimum positive gap

Data-dependent complexity measures L(π) Q∞ V1 π1:T Qtrans (ℓ)

First-order complexity Second-order complexity Path-length complexity Transition-dependent complexity in (2)

Notation for Algorithm 1 ψt ηt (s, a) mt (s, a) ζt (s, a) b t (s, a) Q bt (s), Bt (s, a) ct (s, a), Ct (s, a) Yt ∈ {0, 1} Tr , Tv q πt (s), q πt (s) γt , qt (s) := q πt t (s) + γt ρt (s) := (qt (s) − q πt t (s))/qt (s) Lt,h(s) , Mt,h(s) Dt,h(s) Pt P ℓt Pm t B Pt C Pt

Regularizer in episode t Learning rate for (s, a) in episode t Loss prediction for (s, a) Data-dependent term for updating ηt (s, a) Q-function estimator Exploaration bonus and its recursive Q-function version Transition bonus and its recursive Q-function version Episode indicator (Yt = 1 real, Yt = 0 virtual) Sets of real and virtual episodes Upper and lower occupancy measures Exploration rate and smoothed state occupancy relative occupancy width Realized / predicted suffix loss from layer h(s) Suffix prediction error from layer h(s) Confidence set at episode t Transition in Pt minimizing Q(s, a; ℓt ) for all (s, a) Transition in Pt minimizing Q(s, a; mt ) for all (s, a) Transition in Pt maximizing Bt (s, a) for all (s, a) Transition in Pt maximizing Ct (s, a) for all (s, a)

We formalize the conditional occupancy measure q πt (s′ , a′ | s, a) as follows:  0 if h(s′ ) < h(s),    0 if h(s′ ) = h(s) and (s′ , a′ ) ̸= (s, a),  1 if (s′ , a′ ) = (s, a),   ′ ′ Pr (st,h(s′ ) , at,h(s′ ) ) = (s , a ) | (st,h(s) , at,h(s) ) = (s, a) , if h(s′ ) > h(s). B

For P ℓt , P m t , P t , and P t , we choose kernels in Pt that attain the required state-action-wise minimum or maximum for all (s, a) simultaneously. This is possible since Pt is rectangular, and these kernels are efficiently computable by backward dynamic programming with a state-actionwise greedy procedure over the confidence set, as in Jin et al. (2020, Algorithm 3) and Luo et al. (2021, Algorithms 4–6).

Additional related work and discussion

B.1

Additional related work

Tabular MDPs. Adversarial MDPs have been studied since the works of Even-Dar et al. (2009); Yu et al. (2008), and the episodic formulation was later introduced by Zimin and Neu (2013). Algorithms for online tabular MDPs can be broadly divided into two approaches: occupancy-measure based global optimization and policy optimization. Global optimization solves an optimization problem over the set of occupancy measures, and has led to strong regret guarantees in several settings (Zimin and Neu, 2013; Jin et al., 2020). However, global optimization can be computationally demanding because it optimizes over the occupancy measure space of the MDP. Policy optimization takes a more local approach by optimizing an action distribution at each state, which is often practical and computationally efficient (Shani et al., 2020; Luo et al., 2021). Under known √ transitions and bandit feedback, global optimization achieves the minimax-optimal e HSAT ) (Zimin and Neu, 2013). In contrast, the best known bound for policy regret rate O( √ e H 3 SAT ), achieved via dilated exploration (Luo et al., 2021). Compared with optimization is O( the global optimization rate, this bound incurs an extra factor of H, often attributed to Q-function estimation. Unknown transitions introduce an additional difficulty, since the learner must also estimate the transition kernel. Among global optimization, the best known regret bounds were obtained by Rosenberg and Mansour √ (2019) for full-information feedback and Jin et al. (2020) for bandit feedback, both of e H 2 S 2 AT ). For policy optimization under bandit feedback, the best known guarantee order O( √ e H 4 S 2 AT ). On the other hand, minimax was established by Luo et al. (2021), with regret O( √ lower bounds of order Ω( H 2 SAT ) were established by Jin et al. (2018); Domingues et al. (2021), leaving gaps in the dependence on the horizon and the number of states. A line of work has sought to close these gaps, and Tiapkin et al. √ (2025) proposed a policy-optimization algorithm under fulle H 6 SAT ). More recent work has studied policy optimization information feedback with regret O( under more challenging feedback models, including aggregate feedback (Lancewicki and Mansour, 2025; Ito et al., 2025). In the stochastic setting, near-optimal regret guarantees have been established by both model-based and value-based methods (Jaksch et al., 2010; Azar et al., 2017; Jin et al., 2018; Zanette and Brunskill, 2019). Beyond such gap-independent guarantees, a line of work has studied gap-dependent polylog(T ) regret bounds for episodic tabular MDPs (Simchowitz and Jamieson, 2019; Dann et al., 2021; Xu et al., 2021). Best-of-both-worlds algorithms. The best-of-both-worlds guarantee aims to obtain near-optimal regret in both adversarial and stochastic regimes using a single algorithm. This idea was first studied for multi-armed bandits by Bubeck and Slivkins (2012), and was later developed in several directions (Seldin and Slivkins, 2014; Auer and Chiang, 2016; Seldin and Lugosi, 2017). A common approach is to use follow-the-regularized-leader with carefully chosen regularizers, which allows the algorithm to remain robust in the adversarial regime while improving automatically in the stochastic regime (Wei and Luo, 2018; Zimmert and Seldin, 2021; Ito, 2021). The stochastic-regime analysis is 16

often based on a self-bounding technique (Zimmert and Seldin, 2021; Masoudian and Seldin, 2021), and the same idea is useful for handling stochastic losses with adversarial corruption. Best-of-both-worlds guarantees have also been studied in tabular MDPs. For global optimization, Jin and Luo (2020); Jin et al. (2021) first developed best-of-both-worlds algorithms, with subsequent extensions to adversarial transitions and aggregate feedback (Jin et al., 2023; Ito et al., 2025). In policy optimization, Dann et al. (2023) established best-of-both-worlds guarantees under bandit feedback for several regularizers, including Tsallis entropy, Shannon entropy, and log-barrier regularization, while Li et al. (2026) later obtained refined data-dependent guarantees using the OFTRL framework under known transitions. Data-dependent bounds. Data-dependent regret bounds adapt to the realized loss sequence instead of depending only on worst-case parameters. They have been widely studied in online learning, including learning with expert advice (Littlestone and Warmuth, 1994), multi-armed bandits (Auer et al., 2002), and online convex optimization (Zinkevich, 2003). Typical examples in adversarial regimes include first-order bounds based on the comparator’s cumulative loss (Cesa-Bianchi et al., 1996; Allenberg et al., 2006; Neu, 2015), second-order bounds based on loss fluctuations (Hazan and Kale, 2011; Wei and Luo, 2018; Ito, 2021), and path-length bounds based on temporal variation (Wei and Luo, 2018; Bubeck et al., 2019; Ito, 2021). In tabular MDPs, it is also important to obtain regret bounds that adapt to data-dependent complexity measures. The first such result was obtained by Lee et al. (2020), who derived a first-order bound for MDPs with unknown transitions via global optimization. For policy optimization, Dann et al. (2023) established best-of-both-worlds guarantees under unknown transitions and first-order datadependent guarantees under known transitions, leaving open whether data-dependent guarantees are possible under unknown transitions. More recently, Li et al. (2026) showed that, under known transitions, OFTRL-based policy optimization can adapt to multiple complexity measures, including first-order, second-order, and path-length measures. A related line of work has studied gap-dependent bounds in stochastic regimes. For multi-armed bandits, Audibert et al. (2007) introduced variance-aware gap-dependent bounds, and related ideas have been incorporated into best-of-both-worlds analyses (e.g., Ito et al. 2022). For tabular MDPs, recent works have also studied variance-aware gap-dependent polylog(T ) regret bounds (Simchowitz and Jamieson, 2019; Dann et al., 2021; Chen et al., 2025; Li et al., 2026). These studies left open the case of data-dependent policy optimization under unknown transitions, especially when combined with best-of-both-worlds guarantees. Our work addresses these gaps by showing that policy optimization can achieve refined data-dependent and best-of-both-worlds guarantees under unknown transitions, up to an additional transition-dependent complexity term. B.2

Discussion of the transition-dependent complexity

1:T In this part, we discuss the role of the transition-dependent complexity Qπtrans (ℓ), which captures the difficulty caused by unknown transitions. By Lemma D.6, we have

1:T Qπtrans (ℓ) ≤ H

T X X

q πt (s, a)ℓt (s, a)2 .

(17)

t=1 s,a

Since ℓt (s, a) ∈ [0, 1], taking expectations gives # " T XX π1:T πt E[Qtrans (ℓ)] ≤ HE q (s, a)ℓt (s, a) = H(LT (π) + RegT (π))

(18)

t=1 s,a

for each policy π. From this inequality, we can show that the transition-dependent bound recovers a regret bound depending on the first-order complexity. Suppose that for the any comparator policy π, there exists an absolute constant c > 0 such that q 1:T RegT (π) ≤ c S 2 A log2 (T )E[Qπtrans (ℓ)] + J

for some J > 0, as the regret bounds in Theorems 4.1 and 4.2. Then, using the inequality (18), the regret is upper bounded as q RegT (π) ≤ c HS 2 A log2 (T )(L(π) + RegT (π)) + J q q ≤ c HS 2 A log2 (T )L(π) + c HS 2 A log2 (T )RegT (π) + J q 1 1 ≤ c HS 2 A log2 (T )L(π) + RegT (π) + c2 HS 2 A log2 (T ) + J 2 2 where the last inequality follows from the AM–GM inequality. Thus, we obtain q RegT (π) ≲ HS 2 A log2 (T )L(π) + HS 2 A log2 (T ) + J. 1:T This implies that Qπtrans (ℓ) is at least as adaptive as the first-order complexity. However, the com1:T parison in (17) can be loose. Transition uncertainty contributes to Qπtrans (ℓ) only when it creates variation in the future cumulative loss. 1:T The following example shows that Qπtrans (ℓ) can be small even when the cumulative loss is large. Consider an H = 3 layered MDP with layers S0 = {s0 }, S1 = {x1 , x2 }, and S2 = {y}, followed by the terminal state. For each action a, the transition P (· | s0 , a) may be stochastic and unknown over {x1 , x2 }. For every action, the transitions from x1 and x2 go deterministically to y, and the transition from y goes deterministically to the terminal state.

Let the losses at s0 , x1 and x2 be zero, and let the loss at y be one: ℓt (s0 , a) = 0,

ℓt (xi , a) = 0

(i ∈ {1, 2}),

ℓt (y, a) = 1,

∀a ∈ A, ∀t ∈ [T ].

Since every trajectory passes through y and the loss at y is one, the cumulative loss is linear in T , and in particular T X X

q πt (s, a)ℓt (s, a)2 = T.

t=1 s,a

However, for any sequence {ϕt }Tt=1 satisfying |ϕt (s, a)| = ℓt (s, a), we have V πt (x1 ; ϕt ) = V πt (x2 ; ϕt ). Hence, for every action a, Vars′ ∼P (·|s0 ,a) [V πt (s′ ; ϕt )] = 0. 1:T The other transitions are deterministic, so no transition contributes to Qπtrans (ℓ), and thus π1:T Qtrans (ℓ) = 0. 1:T In this example, the right-hand side of (17) is of order HT , whereas Qπtrans (ℓ) = 0. By adding 2 deterministic layers after y, the same construction gives an O(H T ) term on the right-hand side 1:T 1:T while keeping Qπtrans (ℓ) = 0. This shows that Qπtrans (ℓ) can be much smaller than the upper bound in (17) and (18).

High probability event

We define the following good event E = E1 ∩ E2 , which holds with high probability as shown in Definition C.4. E1 = {P ∈ Pt , ∀t = 1, . . . , T },   T  X πt X q (s, a) ≲ |Sh |A log T + log(H/δ), ∀h = 0, . . . , H − 1 . E2 =   nt (s, a) t=1 (s,a)∈Sh ×A

Lemma C.1 (Event E1 , Jin et al. 2020, Lemma 2). With probability at least 1 − 4δ, we have P ∈ Pt for all t = 1, . . . , T . Lemma C.2 (Jin et al. 2021, Corollary D.3.4). If P ∈ Pt , then for all Pe ∈ Pt ( s ) P (s′ | s, a)ι 40ι ′ ′ e P (s | s, a) − P (s | s, a) ≤ min 4 + ,1 nt (s, a) 3nt (s, a) Lemma C.3 (Event E2 , Jin et al. 2020, Lemma 10). We have with probability at least 1 − δ T X

t=1 (s,a)∈Sh ×A

q πt (s, a) ≲ |Sh |A log T + log(H/δ) nt (s, a)

for all layers h. Definition C.4. Define E to be the event that P ∈ Pt for all t and the bound in Lemma C.3 holds. In this case, Pr(E) ≥ 1 − 5δ.

Auxiliary lemmas

D.1

Technical lemmas

Lemma D.1 (Performance difference lemma). For any policies π1 and π2 , and any loss function ℓ : S × A → R, X X V π1 (s0 ; ℓ) − V π2 (s0 ; ℓ) = q π2 (s) (π1 (a | s) − π2 (a | s))Qπ1 (s, a; ℓ). s

Lemma D.2 (Dann et al. 2023, Lemma C.2). For any policies π1 and π2 , and any function L : S × A → R, define ℓ(s, a) = L(s, a) − Es′ ∼P (·|s,a), a′ ∼π1 (·|s′ ) [L(s′ , a′ )]. Then, for all (s, a), Qπ1 (s, a; ℓ) = L(s, a). Consequently, X X q π2 (s) (π1 (a | s) − π2 (a | s))L(s, a) = V π1 (s0 ; ℓ) − V π2 (s0 ; ℓ). s

Lemma D.3 (Occupancy measure difference, Jin et al., 2021, Lemma D.3.1). For any transition functions P1 , P2 and any policy π, h(s)−1

q P1 ,π (s) − q P2 ,π (s) =

X X X X

q P1 ,π (u, v)(P1 (w | u, v) − P2 (w | u, v))q P2 ,π (s | w)

h=0 u∈Sh v∈A w∈Sh+1 h(s)−1

X X X X

q P2 ,π (u, v)(P1 (w | u, v) − P2 (w | u, v))q P1 ,π (s | w).

h=0 u∈Sh v∈A w∈Sh+1

for all state-action pairs (s, a) ∈ Sh × A. Proof. Since Let

s′ ∈S

et (s′ | s, a) − P (s′ | s, a) = 0, we may subtract any constant from F . P h+1 c = Es′ ∼P (·|s,a) [F (s′ )].

Then, X

Pet (s′ | s, a) − P (s′ | s, a) F (s′ ) =

s′ ∈Sh+1

X Pet (s′ | s, a) − P (s′ | s, a) (F (s′ ) − c) s′ ∈Sh+1

Therefore, X

Pet (s′ | s, a) − P (s′ | s, a) F (s′ )

s′ ∈Sh+1

≤

Pet (s′ | s, a) − P (s′ | s, a) |F (s′ ) − c|

s′ ∈Sh+1

s ≲

X s′ ∈Sh+1

X P (s′ | s, a)ι |F (s′ ) − c| + nt (s, a) ′

s ∈Sh+1

ι |F (s′ ) − c| nt (s, a)

(by Lemma C.2 and the assumption that E holds) s ≤

s ≤

|Sh+1 |

2 ′ ′ s′ ∈Sh+1 P (s | s, a)(F (s ) − c) ι

2|Sh+1 |F ι nt (s, a) nt (s, a) (by the Cauchy–Schwarz inequality and |F (s′ ) − c| ≤ 2F ) +

Lemma D.5. Suppose that the event E holds. Let Pet be a transition kernel in Pt , and let gt (s, a) ∈ [0, G]. Then, it holds that T X X

q πt (s) − q Pt ,πt (s) πt (a | s)gt (s, a) ≲ e

1:T S 2 Aι2 Qπtrans (g) + HS 3 AGι2 ,

t=1 s,a

where 1:T (g) := Qπtrans

T X X

sup

q πt (s, a)Vars′ ∼P (·|s,a) [V πt (s′ ; ϕt )].

∀t,∀s,a |ϕt (s,a)|=gt (s,a) t=1 s,a

Proof. For each layer h ∈ {0, . . . , H − 1}, let Wh := Sh × AP × Sh+1 . P Throughout the proof, whenever summation indices are omitted, expressions such as u,v,w or x,y,z stand for PH−1 P h=0 (s,a,s′ )∈Wh . e Let ϕt (s, a) = sgn q πt (s) − q Pt ,πt (s) gt (s, a). According to Lemma D.3, we have X

q πt (s) − q Pt ,πt (s) πt (a | s)gt (s, a) e

s,a

e q πt (s) − q Pt ,πt (s) πt (a | s)ϕt (s, a)

X X

s,a

e q πt (u, v) P (w | u, v) − Pet (w | u, v) q Pt ,πt (s | w)πt (a | s)ϕt (s, a)

s,a u,v,w

q πt (u, v) P (w | u, v) − Pet (w | u, v) q πt (s | w)πt (a | s)ϕt (s, a)

s,a u,v,w

} XX X e + q πt (u, v) P (w | u, v) − Pet (w | u, v) q Pt ,πt (s | w) − q πt (s | w) πt (a | s)ϕt (s, a) . term1

a u,v,w

term2

}

We first bound term1 . X X term1 ≤ q πt (u, v) P (w | u, v) − Pet (w | u, v) q πt (s, a | w)ϕt (s, a) u,v,w

s,a

q (u, v) P (w | u, v) − Pet (w | u, v) V πt (w; ϕt )

πt

u,v,w

≤

q πt (u, v)

u,v

≤

X P (w | u, v) − Pet (w | u, v) V πt (w; ϕt ) s

H−1 X

πt

q (u, v)

h=0 (u,v)∈Sh ×A

(by Lemma D.4) =

H−1 X

q πt (u, v)

h=0 (u,v)∈Sh ×A

|Sh+1 |Varw∼P (·|u,v) [V πt (w; ϕt )]ι nt (u, v) {z } term1a

H−1 X

|Sh+1 |HGι

h=0

q πt (u, v) nt (u, v) (u,v)∈Sh ×A {z } X

term1b

For term1a , T X

term1a ≤

T H−1 X X

q πt (u, v)

t=1 h=0 (u,v)∈Sh ×A

t=1

v uX X u T H−1 ≤t

|Sh+1 |

t=1 h=0 (u,v)∈Sh ×A

v uX X u T H−1 ×t

|Sh+1 |Varw∼P (·|u,v) [V πt (w; ϕt )]ι nt (u, v)

q πt (u, v)ι nt (u, v)

q πt (u, v)Varw∼P (·|u,v) [V πt (w; ϕt )]

t=1 h=0 (u,v)∈Sh ×A

(by the Cauchy–Schwarz inequality) v ! T ! u H−1 XX u X t 2 π π t t ≲ |Sh+1 ||Sh |Aι q (u, v)Varw∼P (·|u,v) [V (w; ϕt )] t=1 u,v

h=0

(by Lemma C.3 and the assumption that E holds) v ! u T X X u t 2 2 π π q t (u, v)Varw∼P (·|u,v) [V t (w; ϕt )] , ≤ S Aι (19) t=1 u,v

where the last inequality uses

PH−1

h=0 |Sh+1 ||Sh | ≤ S

For term1b , T X

term1b ≤

t=1

T H−1 X X

|Sh+1 |HGι

t=1 h=0

≲

T H−1 X X

X (u,v)∈Sh ×A

|Sh ||Sh+1 |HAGι2

q πt (u, v) nt (u, v)

(by Lemma C.3 and the assumption that E holds)

t=1 h=0 2

≤ HS AGι2 .

(20) 21

Thus, combining (19) and (20), we obtain v ! u T X T X X u q πt (u, v)Varw∼P (·|u,v) [V πt (w; ϕt )] + HS 2 AGι2 . term1 ≲ tS 2 Aι2 t=1 u,v

t=1

≤G

u,v,w

X X s

πt

q (u, v) P (w | u, v) − Pet (w | u, v)

u,v,w

πt

e q (x, y | w) P (z | x, y) − Pet (z | x, y) q Pt ,πt (s | z)

x,y,z

(by Lemma D.3) X X

≤ HG

q (u, v) P (w | u, v) − Pet (w | u, v)

u,v,w

πt

q (x, y | w) P (z | x, y) − Pet (z | x, y)

x,y,z

s X X

≲ HG

πt

q (u, v)

u,v,w x,y,z

! (s ) P (w | u, v)ι P (z | x, y)ι ι ι πt + q (x, y | w) min + ,1 nt (u, v) nt (u, v) nt (x, y) nt (x, y) (by Lemma C.2 and the assumption that E holds)

s ≤ HG

X X

q πt (u, v)

u,v,w x,y,z

P (w | u, v)ι πt q (x, y | w) nt (u, v) {z term2a

s X X

+ HG

q πt (u, v)

u,v,w x,y,z

P (z | x, y)ι nt (x, y) }

P (w | u, v)ι πt ι q (x, y | w) min , 1 nt (u, v) nt (x, y) {z } term2b

ι q πt (x, y | w) . + HG q (u, v) n t (u, v) u,v,w x,y,z | {z } X X

πt

term2c

For term2a , term2a s =

X X u,v,w x,y,z

q πt (u, v)P (z | x, y)q πt (x, y | w)ι nt (u, v)

q πt (u, v)P (w | u, v)q πt (x, y | w)ι nt (x, y)

v v u X X πt u u q (u, v)P (z | x, y)q πt (x, y | w)ι u X X q πt (u, v)P (w | u, v)q πt (x, y | w)ι t ≤t nt (u, v) nt (x, y) u,v,w x,y,z u,v,w x,y,z (by the Cauchy–Schwarz inequality) v v u X πt u u q (u, v)ι u X q πt (x, y)ι tH ≤ tH nt (u, v) nt (x, y) u,v,w x,y,z ≤ HS

X q πt (u, v)ι u,v

nt (u, v)

(21)

P where the third line follows from the facts that (x,y,z)∈Wh q πt (x, y | w)P (z | x, y) ≤ 1 and P πt πt P,πt (x, y) for any layer h ∈ {0, . . . , H − 1}. (u,v,w)∈Wh q (u, v)P (w | u, v)q (x, y | w) ≤ q For term2b , term2b X X ≤ q πt (u, v) P (w | u, v) + u,v,w x,y,z

ι ι q P,πt (x, y | w) min , 1 nt (u, v) nt (x, y) 22

≤

X X

q πt (u, v)P (w | u, v)q πt (x, y | w)

u,v,w x,y,z

≤H

q πt (x, y)

x,y,z

≲ S2

X ι ι +S q πt (u, v) nt (x, y) n (u, v) t u,v,w

X q πt (u, v)ι u,v

nt (u, v)

X X ι ι + q πt (u, v) q πt (x, y | w) nt (x, y) u,v,w x,y,z nt (u, v)

(22)

term2c ≤ S

q πt (u, v)

u,v,w

X q πt (u, v)ι ι ≤ S2 . nt (u, v) nt (u, v) u,v

(23)

Combining (21)–(23), we obtain term2 ≲ HS 2 G

X q πt (u, v)ι u,v

nt (u, v)

Therefore, by Lemma C.3, T X

term2 ≲

t=1

H−1 X

HS 2 G|Sh |Aι2 ≤ HS 3 AGι2 .

h=0

Combining the bounds on term1 and term2 , we conclude that T X X

q πt (s) − q Pt ,πt (s) πt (a | s)gt (s, a) e

t=1 s,a

v ! u T X X u t 2 2 π π t t ≲ S Aι q (u, v)Varw∼P (·|u,v) [V (w; ϕt )] + HS 3 AGι2 . t=1 u,v

Here, we define 1:T (g) := Qπtrans

sup

T X X

q πt (u, v)Varw∼P (·|u,v) [V πt (w; ϕt )],

∀t,∀s,a |ϕt (s,a)|=gt (s,a) t=1 u,v

which completes the proof. Lemma D.6. For any nonnegative functions gt : S × A → R≥0 , 1:T Qπtrans (g) :=

sup

T X X

q πt (s, a)Vars′ ∼P (·|s,a) [V πt (s′ ; ϕt )]

∀t,∀s,a |ϕt (s,a)|=gt (s,a) t=1 s,a

satisfies 1:T Qπtrans (g) ≤ H

T X X

q πt (s, a)gt (s, a)2 .

t=1 s,a

Proof. Since |ϕt (s, a)| = gt (s, a) for all s, a, it suffices to prove that for each t and each such function ϕt , X X q πt (s, a)Vars′ ∼P (·|s,a) [V πt (s′ ; ϕt )] ≤ H q πt (s, a)ϕt (s, a)2 . s,a

s,a

Let (Xt,0 , At,0 , Xt,1 , At,1 , . . . , Xt,H ) be the random trajectory generated by (P, πt ). For h = 0, 1, . . . , H and x ∈ Sh , define Vt,H = 0 and Mt,H = 0 and H−1 X

Gt,h :=

ϕt (Xt,h′ , At,h′ ),

2 Mt,h (x) := Eπt [Gt,h | Xt,h = x].

Vt,h (x) := Eπt [Gt,h | Xt,h = x],

h′ =h

Since Gt,h = ϕt (Xt,h , At,h ) + Gt,h+1 , we have for any state x ! X

Vt,h (x) =

πt (a | x) ϕt (x, a) +

′

P (x | x, a)Vt,h+1 (x ) ,

x′

and ! Mt,h (x) =

πt (a | x) ϕt (x, a) + 2ϕt (x, a)

′

P (x | x, a)Vt,h+1 (x )

x′

πt (a | x)

P (x′ | x, a)Mt,h+1 (x′ ).

x′

Then, we have Mt,h (x) − Vt,h (x)2 ! =

πt (a | x) ϕt (x, a) + 2ϕt (x, a)

′

P (x | x, a)Vt,h+1 (x ) +

x′

′

P (x | x, a)Mt,h+1 (x )

x′

!!2 −

πt (a | x) ϕt (x, a) +

′

P (x | x, a)Vt,h+1 (x )

x′

′

πt (a | x)

P (x′ | x, a) Mt,h+1 (x′ ) − Vt,h+1 (x′ )2

x′

 X πt (a | x) P (x′ | x, a)Vt,h+1 (x′ )2 −

!2  X

x′

P (x′ | x, a)Vt,h+1 (x′ )



x′

!2 +

πt (a | x) ϕt (x, a) +

′

P (x | x, a)Vt,h+1 (x )

x′

!!2 −

πt (a | x) ϕt (x, a) +

πt (a | x)

P (x | x, a)Vt,h+1 (x )

P (x′ | x, a) Mt,h+1 (x′ ) − Vt,h+1 (x′ )2

x′

′

x′

≥

′

πt (a | x)Varx′ ∼P (·|x,a) [Vt,h+1 (x′ )],

where the last inequality follows from Jensen’s inequality !!2 X

πt (a | x) ϕt (x, a) +

′

P (x | x, a)Vt,h+1 (x )

x′

!2 ≤

πt (a | x) ϕt (x, a) +

′

P (x | x, a)Vt,h+1 (x )

x′

Thus, we have X πt (a | x)Varx′ ∼P (·|x,a) [Vt,h+1 (x′ )] ≤ Mt,h (x) − Vt,h (x)2 a

−

X a

πt (a | x)

X x′

P (x′ | x, a) Mt,h+1 (x′ ) − Vt,h+1 (x′ )2 .

By multiplying q πt (x) and sum over x ∈ Sh , we obtain X X q πt (x, a)Varx′ ∼P (·|x,a) [Vt,h+1 (x′ )] ≤ q πt (x) Mt,h (x) − Vt,h (x)2 x∈Sh

(x,a)∈Sh ×A

−

q πt (x′ ) Mt,h+1 (x′ ) − Vt,h+1 (x′ )2 .

x′ ∈Sh+1

Summing over h = 0, 1, . . . , H − 1 and Vt,h+1 (x′ ) = V πt (x′ ; ϕt ), we obtain X q πt (s, a)Vars′ ∼P (·|s,a) [V πt (s′ ; ϕt )] ≤ Mt,0 (s0 ) − Vt,0 (s0 )2 ≤ Mt,0 (s0 ).

(24)

s,a

Finally, 

H−1 X

Mt,0 (s0 ) = Eπt 

!2  ϕt (Xt,h , At,h )



h=0

≤ HEπt

"H−1 X

# 2

ϕt (Xt,h , At,h )

q πt (s, a)ϕt (s, a)2 ,

(25)

s,a

h=0

where the inequality follows from the Cauchy–Schwarz inequality. Combining (24) and (25) completes the proof. By following the same argument as for term2 in the proof of Lemma D.5, we obtain the following bound, whose lower-order term improves that of Dann et al. (2023) by a factor of S. Lemma D.7. Suppose that the event E holds. Let Pets be a transition kernel in Pt which may depend on s, and let gt (s) ∈ [0, G]. Then v u T X T X u X X es ,πt πt P t 2 2 t q (s) − q (s) gt (s) ≲ HS Aι q πt (s)gt (s)2 + HS 3 AGι2 . t=1

t=1

Lemma D.8. Suppose that the event E holds. Let Pets,es be a transition kernel in Pt which may depend on s, se, and let gt (s) ∈ [0, G]. Then T X X t=1

q πt (e s)

s es,e ,πt

q πt (s | se) − q Pt

(s | se) gt (s)

s e

v u T X u X ≲ tH 3 S 2 Aι2 q πt (s)gt (s)2 + HS 3 AGι2 . t=1

Proof. For each layer h ∈ {0, . . . , H − 1}, let Wh := Sh × AP × Sh+1 . P Throughout the proof, whenever summation indices are omitted, expressions such as u,v,w or x,y,z stand for PH−1 P h=0 (s,a,s′ )∈Wh . First, we prove that for any se, and policy π, s X s

q (s | se) − q

s es,e P ,π t

(s | se) ≲

X X s

q (u, v | se)

u,v,w

X q π (u, v | se)ι P (w | u, v)ι π q (s | w) + HS 2 . nt (u, v) nt (u, v) u,v

By Lemma D.3, we have X

s e s,e ,π

q π (s | se) − q Pt

(s | se)

≤

e q π (u, v | se) P (w | u, v) − Pets,es (w | u, v) q Pt

(by Lemma D.3)

u,v,w

u,v,w

X X

(s | w)

q P,π (u, v | se) P (w | u, v) − Pets,es (w | u, v) q π (s | w)

X X

,π

u,v,w

X X s

≤

s,e s

X X

q π (u, v | se) P (w | u, v) − Pets,es (w | u, v) q π (s | w)

u,v,w

X X s

q π (u, v | se) P (w | u, v) − Pets,es (w | u, v)

u,v,w

s,e s

e q π (x, y | w) P (z | x, y) − Pets,es (z | x, y) q Pt

,π

(s | z)

x,y,z

(by Lemma D.3) ≤

X X s

(u, v | se) P (w | u, v) − Pets,es (w | u, v) q π (s | w)

u,v,w

q π (u, v | se) P (w | u, v) − Pets,es (w | u, v)

u,v,w

q π (x, y | w) P (z | x, y) − Pets,es (z | x, y)

x,y,z

(by Lemma C.2 and the assumption that E holds) s ≤

X X s

q π (u, v | se)

u,v,w

X X s

P (w | u, v)ι π q (s | w) nt (u, v)

ι q π (s | w) nt (u, v) {z }

q π (u, v | se)

u,v,w

term1

s +H

X X

q (u, v | se)

u,v,w x,y,z

term2

s +H

s P (w | u, v)ι π P (z | x, y)ι q (x, y | w) nt (u, v) nt (x, y) {z }

X X

q π (u, v | se)

u,v,w x,y,z

P (w | u, v)ι π ι q (x, y | w) min , 1 nt (u, v) nt (x, y) {z } term3

ι +H q (u, v | se) q π (x, y | w) . n t (u, v) u,v,w x,y,z {z } | X X

term4

We bound term1 to term4 separately. X X q π (u, v | se)ι X q π (u, v | se)ι term1 ≤ ≤ S2 . nt (u, v) nt (u, v) s u,v,w u,v For term2 , we have term2 s =

X X u,v,w x,y,z

q π (u, v | se)P (z | x, y)q π (x, y | w)ι nt (u, v)

q π (u, v | se)P (w | u, v)q π (x, y | w)ι nt (x, y)

(26)

X q π (u, v | se)ι nt (u, v)

u,v

(27)

P where the third line follows from the facts that (x,y,z)∈Wh q π (x, y | w)P (z | x, y) ≤ 1 and P π e)P (w | u, v)q π (x, y | w) ≤ q π (x, y | se) for any layer h ∈ {0, . . . , H − 1}. (u,v,w)∈Wh q (u, v | s For term3 , we obtain X X π term3 ≤ q (u, v | se) P (w | u, v) + u,v,w x,y,z

X X

≤

ι ι π q (x, y | w) min ,1 nt (u, v) nt (x, y)

q π (u, v | se)P (w | u, v)q π (x, y | w)

u,v,w x,y,z

ι nt (x, y)

ι q π (x, y | w) n (u, v) t u,v,w x,y,z X X ι ι ≤H q π (x, y | se) +S q π (u, v | se) n (x, y) n (u, v) t t x,y,z u,v,w X X

≲ S2

q π (u, v | se)

X q π (u, v | se)ι u,v

nt (u, v)

(28)

q π (u, v | se)

u,v,w

X q π (u, v | se)ι ι ≤ S2 . nt (u, v) nt (u, v) u,v

(29)

Combining with (26)–(29), we obtain s X

q π (s | se) − q

s es,e P ,π t

(s | se) ≲

X X s

q π (u, v | se)

u,v,w

X q π (u, v | se)ι P (w | u, v)ι π q (s | w) + S 2 . nt (u, v) nt (u, v) u,v (30)

We now apply (30). Then T X X t=1

q πt (e s)

s es,e ,πt

q πt (s | se) − q Pt

(s | se) gt (s)

s e

πt

X X

πt

(31) 27

We first bound the first term in (31). Fix h. Then   s T X X X P (w | u, v)ι  H q πt (s | w)gt (s) q πt (u, v) n (u, v) t t=1 s (u,v,w)∈Wh  T X X X πt  ≤H q (u, v) αP (w | u, v)gt (s)2 + t=1

(u,v,w)∈Sh ×A×Sh+1

 ι q πt (s | w) αnt (u, v)

(holds for any α > 0 by the AM-GM inequality) = αH

T X X t=1

q πt (u, v)P (w | u, v)q πt (s | w)gt (s)2

(u,v,w)∈Sh ×A×Sh+1

H XX α t=1 s

≤ αH

T X X t=1

≲ αH

(u,v,w)∈Sh ×A×Sh+1

q πt (u, v)ι πt q (s | w) nt (u, v) T

q πt (s)gt (s)2 +

T X X t=1

q πt (s)gt (s)2 +

H 2 |Sh+1 | X α t=1

X (u,v)∈Sh ×A

q πt (u, v)ι nt (u, v)

H 2 |Sh+1 ||Sh |Aι2 α (by Lemma C.3 and the assumption that E holds)

v u T X u X ≲ tH 3 |Sh ||Sh+1 |Aι2 q P,πt (s)gt (s)2 t=1

(by picking the optimal α)

v u T X u X ≤ (|Sh | + |Sh+1 |)tH 3 Aι2 q P,πt (s)gt (s)2 .

(by the AM–GM inequality)

t=1

Summing over h gives H−1 X

v v u u T X T X u u X X t 3 2 π 2 t (|Sh | + |Sh+1 |) H Aι q (s)gt (s) ≲ tH 3 S 2 Aι2 q πt (s)gt (s)2 . t=1

h=0

t=1

(32)

It remains to bound the second term in (31). By Lemma C.3 and the event E, HS 2 G

T X πt X q (u, v)ι

nt (u, v)

t=1 u,v

≲ HS 3 AGι2 .

(33)

Combining (32) and (33), we complete the proof. D.2

Data-dependent and self-bounding lemmas

Lemma D.9. It holds that " T # " T # XX X e,πt 2 2 πt P πt E q (s, a) max Q (s, a; (ℓt − mt ) ) ≲ HE V (s0 ; (ℓt − mt ) ) + HS 3 Aι2 . t=1 s,a

e∈Pt P

t=1

PT P e Proof. On the eventĒ, t=1 s,a q πt (s, a) maxPe∈Pt QP ,πt (s, a; (ℓt − mt )2 ) = O(H 2 T ) gives a contribution O(H 2 T δ), which is absorbed by taking δ = O(1/T 2 ). Q

Hence, it suffices to prove the bound on E. For each t, let P t ∈ Pt be such that Q

QP t ,πt (s, a; (ℓt − mt ) ) = max QP ,πt (s, a; (ℓt − mt ) ) e

e∈Pt P

for all (s, a). Then, T X X

q πt (s, a)QP t ,πt (s, a; (ℓt − mt ) )

t=1 s,a

≤

T X X

q πt (s, a)Qπt (s, a; (ℓt − mt )

t=1 s,a

T X X

Q 2 2 q πt (s, a) QP t ,πt (s, a; (ℓt − mt ) ) − Qπt (s, a; (ℓt − mt ) ) .

(34)

t=1 s,a

For the first term, we have T X X

q πt (s, a)Qπt (s, a; (ℓt − mt ) )

t=1 s,a

T X X

q πt (s′ , a′ | s, a)(ℓt (s′ , a′ ) − mt (s′ , a′ ))

s′ ,a′

t=1 s,a

≤H

q πt (s, a)

T X X

q πt (s′ , a′ )(ℓt (s′ , a′ ) − mt (s′ , a′ ))

t=1 s′ ,a′

T X

V πt (s0 ; (ℓt − mt ) )

(35)

t=1

For the second term, we obtain T X Q X 2 2 q πt (s, a) QP t ,πt (s, a; (ℓt − mt ) ) − Qπt (s, a; (ℓt − mt ) ) t=1 s,a

T X X

q πt (s, a)

t=1 s,a

s′

T X X

t=1

q πt (s)

q P t ,πt (s′ | s, a) − q πt (s′ | s, a)

πt (a′ | s′ )(ℓt (s′ , a′ ) − mt (s′ , a′ ))

a′

X Q 2 πt (a′ | s′ )(ℓt (s′ , a′ ) − mt (s′ , a′ )) q P t ,πt (s′ | s) − q πt (s′ | s) a′

s′

v u T X X u 2 t 3 2 2 ≤ H S Aι q πt (s′ , a′ )(ℓt (s′ , a′ ) − mt (s′ , a′ )) + HS 3 Aι2

(by Lemma D.8)

t=1 s′ ,a′

v u T u X 2 = tH 3 S 2 Aι2 V πt (s0 ; (ℓt − mt ) ) + HS 3 Aι2 .

(36)

t=1

Combining (34)–(36), we obtain T X X

q πt (s, a)QP t ,πt (s, a; (ℓt − mt ) )

t=1 s,a

≤H

T X

v u T u X 2 2 πt V (s ; (ℓ − m ) ) + tH 3 S 2 Aι2 V πt (s ; (ℓ − m ) ) + HS 3 Aι2 0

≲H

T X

t=1

t=1 2

V πt (s0 ; (ℓt − mt ) ) + HS 3 Aι2 ,

t=1

where the last line follows from the AM–GM inequality since ax + a, b, x ≥ 0. Taking expectations completes the proof. 29

√

b bx ≤ ax + ax + 2a for

Lemma D.10 (Li et al. 2026, Lemma E.9). It holds that " T # " T # XX XX 2 2 2 E It (s, a)(Lt,h(s) − Mt,h(s) ) ≤ H E It (s, a)(ℓt (s, a) − mt (s, a)) . t=1 s,a

t=1 s,a

Lemma D.11 (Li et al. 2026, Lemma F.12). Suppose mt is defined in (4) with some constant ξ ∈ (0, 21 ). Then, for any comparator policy π, it holds that " T # " T # X XX 2 πt 2 E V (s0 ; (ℓt − mt ) ) = E It (s, a)(ℓt (s, a) − mt (s, a)) t=1 s,a

t=1

≲ min{L(π) + RegT (π), HT − L(π) − RegT (π), Q∞ , V1 } + SA. Lemma D.12. For any sequence of policies {πt }Tt=1 and any prediction sequence {mt }Tt=1 , it holds that 1:T 1:T Qπtrans (m) ≤ 2Qπtrans (ℓ) + 2H

T X

V πt (s0 ; (ℓt − mt )2 ).

t=1

Proof. Fix any sequence ϕt such that |ϕt (s, a)| = mt (s, a) for all t, s, a. Define ϕℓt (s, a) := sgn(ϕt (s, a))ℓt (s, a),

ℓ ϕ∆ t (s, a) := ϕt (s, a) − ϕt (s, a).

Then ϕℓt (s, a) = ℓt (s, a),

ϕ∆ t (s, a) = |ℓt (s, a) − mt (s, a)|.

Moreover, for any state s, V πt (s; ϕt ) = V πt (s; ϕℓt ) + V πt (s; ϕ∆ t ). By using Var(X + Y ) ≤ 2Var(X) + 2Var(Y ), we have T X X

q πt (s, a)Vars′ ∼P (·|s,a) [V πt (s′ ; ϕt )]

t=1 s,a

≤2

T X X

T X X q πt (s, a)Vars′ ∼P (·|s,a) V πt (s′ ; ϕℓt ) + 2 q πt (s, a)Vars′ ∼P (·|s,a) V πt (s′ ; ϕ∆ t )

t=1 s,a

1:T 1:T (|ℓ − m|). (ℓ) + 2Qπtrans ≤ 2Qπtrans

Since this holds for any sequence ϕt with |ϕt (s, a)| = mt (s, a), taking the supremum yields 1:T 1:T 1:T (|ℓ − m|). (ℓ) + 2Qπtrans Qπtrans (m) ≤ 2Qπtrans

Finally, Lemma D.6 with gt = |ℓt − mt | gives 1:T Qπtrans (|ℓ − m|) ≤ H

T X

V πt (s0 ; (ℓt − mt )2 ).

t=1

Therefore, 1:T 1:T Qπtrans (m) ≤ 2Qπtrans (ℓ) + 2H

T X

V πt (s0 ; (ℓt − mt )2 ).

t=1

Lemma D.13 (Dann et al. (2023, Lemma C.5)). For any two policies π1 and π2 , it holds that X X q π1 (s)|π1 (a | s) − π2 (a | s)|. |q π1 (s, a) − q π2 (s, a)| ≤ H s,a

s,a

Lemma D.14. For any policy π and layer h, it holds that h X X

⋆

q π (s, a) − q π (s, a) ≤ 2

q π (s, a).

h′ =0 s∈Sh′ a̸=π ⋆ (s)

(s,a)∈Sh ×A

Proof. Since π ⋆ is deterministic, we have X ⋆ q π (s, a) − q π (s, a) (s,a)∈Sh ×A

q π (s)π(a | s) − q π (s)1[a = π ⋆ (s)] ⋆

(s,a)∈Sh ×A

|q π (s)π(a | s) − q π (s)1[a = π ⋆ (s)]| +

≤

q (s, a) +

s∈Sh a̸=π ⋆ (s)

q π (s) − q π (s)

s∈Sh

(s,a)∈Sh ×A

⋆

(by the triangle inequality) X ⋆ q π (s) − q π (s) q (s)(1 − π(π (s) | s)) + π

⋆

s∈Sh

q π (s, a) +

s∈Sh a̸=π ⋆ (s)

s∈Sh

⋆

q π (s) − q π (s) .

(37)

s∈Sh

Next, by the triangle inequality, X ⋆ q π (s′ ) − q π (s′ ) s′ ∈Sh+1

X X

s′ ∈Sh+1 s∈Sh

≤

⋆ q π (s)π(a | s)P (s′ | s, a) − q π (s)1[a = π ⋆ (s)]P (s′ | s, π ⋆ (s))

⋆ q π (s)P (s′ | s, π ⋆ (s)) − q π (s)P (s′ | s, π ⋆ (s))

s′ ∈Sh+1 s∈Sh

q π (s)π(a | s)P (s′ | s, a) +

s′ ∈Sh+1 s∈Sh a̸=π ⋆ (s)

≤

q π (s)(π(π ⋆ (s) | s) − 1)P (s′ | s, π ⋆ (s))

s∈Sh

⋆

q π (s) − q π (s) P (s′ | s, π ⋆ (s))

s′ ∈Sh+1 s∈Sh

q π (s, a)|P (s′ | s, a) − P (s′ | s, π ⋆ (s))|

s′ ∈Sh+1 s∈Sh a̸=π ⋆ (s)

≤

⋆

q π (s) − q π (s) + 2

s∈Sh

a̸=π ⋆ (s)

where the last inequality follows from action pairs (s, a).

q π (s, a),

(38)

′ ′ ⋆ s′ ∈Sh+1 |P (s | s, a) − P (s | s, π (s))| ≤ 2 for all state-

⋆

Applying (38) recursively and using q π (s0 ) = q π (s0 ), we obtain X

π⋆

q (s) − q (s) ≤ 2

h−1 X

q π (s, a).

h′ =0 s∈Sh′ a̸=π ⋆ (s)

s∈Sh

Combining (37) and (39) yields X

⋆

q π (s, a) − q π (s, a) ≤ 2

h X X

h′ =0 s∈Sh′ a̸=π ⋆ (s)

(s,a)∈Sh ×A

This completes the proof. 31

q π (s, a).

(39)

Lemma D.15 (Jin et al. 2020, Section 2.1). Under the stochastic regime with adversarial corruption, for any sequence of policies {πt }Tt=1 , the regret satisfies the following (∆, 2C, T ) self-bounding constraint:   T X X X RegT (π̊) ≥ E q πt (s, a)∆(s, a) − 2C. s

t=1

a̸=π ⋆ (s)

Lemma D.16. Let G : S × A → R≥0 be any nonnegative function. Under the stochastic regime with adversarial corruption, for any α > 0, it holds that v " # u T u X X X G(s, a)2 X X t . q πt (s, a) ≤ α(RegT (π̊) + 2C) + G(s, a) E 4α∆(s, a) ⋆ ⋆ s s t=1 a̸=π (s)

a̸=π (s)

Proof. For each (s, a) with a ̸= π ⋆ (s), the AM–GM inequality and Lemma D.15 imply v " # u T u X X X G(s, a)tE q πt (s, a) s

t=1

a̸=π ⋆ (s)

  T X X X X X ≤ αE q πt (s, a)∆(s, a) + t=1

a̸=π ⋆ (s)

G(s, a)2 4α∆(s, a)

(by the AM–GM inequality with α > 0) ≤ α(RegT (π̊) + 2C) +

X X s

a̸=π ⋆ (s)

G(s, a)2 . 4α∆(s, a)

(by Lemma D.15)

Lemma D.17. Let G(h) be any nonnegative function defined on layer h. Under the stochastic regime with adversarial corruption, for any α > 0, it holds that v   u H−1 T Xu X X u tG(h)E [q πt (s, a) − q π̊ (s, a)]+  t=1 (s,a)∈Sh ×A

h=0

P ≤ α(RegT (π̊) + 4C) +

H−1 h=0

2 G(h)

4α∆min

Proof. Applying Lemma D.14, we obtain   T X X E q πt (s, a) − q π̊ (s, a) +  t=1 (s,a)∈Sh ×A

 = E  ≤ E



T 1X

2 t=1

(s,a)∈Sh ×A

T 1X

q πt (s, a) − q π̊ (s, a) 

 ⋆ ⋆ q πt (s, a) − q π (s, a) + q π̊ (s, a) − q π (s, a) 

2 t=1 (s,a)∈Sh ×A  T X h X X X ≤ E

 q πt (s, a) + q π̊ (s, a) .

t=1 h′ =0 s∈Sh′ a̸=π ⋆ (s)

We next bound the comparator contribution. Using the uncorrupted mean loss function µ, we have   T X X X E q π̊ (s, a)∆(s, a) s

t=1

a̸=π ⋆ (s)

" T # X π̊ π⋆ =E V (s0 ; µ) − V (s0 ; µ) t=1

" T # " T # X X π̊ π̊ π̊ π⋆ =E V (s0 ; ℓt ) − V (s0 ; ℓt ) V (s0 ; µ) − V (s0 ; ℓt ) + E t=1

t=1

" T X

# ⋆ ⋆ V π (s0 ; ℓt ) − V π (s0 ; µ) .

t=1

The middle term is nonpositive by the definition of π̊. Moreover, since E[ℓ′t ] = µ, for any policy π, " T # " T # X X π π π π ′ E |V (s0 ; ℓt ) − V (s0 ; µ)| ≤ E |V (s0 ; ℓt ) − V (s0 ; ℓt )| (by Jensen’s inequality) t=1

t=1

# " T H−1 XX ∥ℓt (h) − ℓ′t (h)∥∞ = C. ≤E t=1 h=0

Therefore,   T X X X q π̊ (s, a)∆(s, a) ≤ 2C. E t=1

(40)

a̸=π ⋆ (s)

Combining (40) with Lemma D.15, we get   T X X X E q πt (s, a) + q π̊ (s, a) ∆(s, a) ≤ RegT (π̊) + 4C. t=1

a̸=π ⋆ (s)

Then, for any α > 0, we have v  u T H−1 X Xu u tG(h)E

 X

[q πt (s, a) − q π̊ (s, a)]+ 

t=1 (s,a)∈Sh ×A

h=0

v   u H−1 T X X Xu X u tG(h)E ≤ (q πt (s, a) + q π̊ (s, a)) t=1

h=0

a̸=π ⋆ (s)

v   u H−1 T X X u Xp X u 1 ≤ G(h)t E (q πt (s, a) + q π̊ (s, a))∆(s, a) ∆min ⋆ t=1 s h=0

≤

H−1 Xp h=0

a̸=π (s)

s G(h)

RegT (π̊) + 4C ∆min P p

≤ α(RegT (π̊) + 4C) +

H−1 h=0

2 G(h)

4α∆min

where we use the AM–GM inequality. Lemma D.18. Let G > 0. Under the stochastic regime with adversarial corruption, for any α > 0, it holds that v " # u T X X u HG tGE π π̊ [q t (s, a) − q (s, a)]+ ≤ α(RegT (π̊) + 4C) + . 2α∆min t=1 s,a 33

Proof. Applying Lemma D.13 to compare any policy π with π ⋆ , we get T X X

⋆

q π (s, a) − q π (s, a) ≤ H

T X X

q π (s)|π(a | s) − π ⋆ (a | s)|

t=1 s,a

≤H

T X X X t=1

T X X t=1

≤ 2H

q π (s)π(a | s)

a̸=π ⋆ (s)

q π (s)(1 − π(π ⋆ (s) | s))

T X X X t=1

q π (s)π(a | s).

a̸=π ⋆ (s)

Using this bound with π = πt and π = π̊, for any α > 0 we obtain v " # u T X X u tGE [q πt (s, a) − q π̊ (s, a)] +

t=1 s,a

v " # u T X X u t π π̊ t ≤ GE |q (s, a) − q (s, a)| t=1 s,a

v " # u T X X u ⋆ ⋆ t π π π̊ π t ≤ GE (|q (s, a) − q (s, a)| + |q (s, a) − q (s, a)|) t=1 s,a

v   u T X X u X u ≤ t2HGE (q πt (s, a) + q π̊ (s, a) t=1

a̸=π ⋆ (s)

v   u T X X u X 1 u E (q πt (s, a) + q π̊ (s, a))∆(s, a) ≤ t2HG ∆min ⋆ t=1 s a̸=π (s)

s ≤

2HG

RegT (π̊) + 4C ∆min

≤ α(RegT (π̊) + 4C) +

(by Lemma D.15 and (40))

HG , 2α∆min

where the last inequality follows from the AM–GM inequality.

General lemma of optimistic follow-the-regularized-leader

In this section, we provide a regret analysis of optimistic follow-the-regularized-leader (OFTRL) for the MDP setting. Lemma E.1 (OFTRL with policy optimization, Li et al. 2026, Lemma C.4). Suppose that a sequence of probability vectors p1 , . . . , pT ∈ △(A) is given by OFTRL in (* t−1 + ) X X 1 1 pt = arg min p, ℓτ + mt + ψt (p) , ψt (p) = log ηt (a) p(a) ∆(A) a τ =1 +1 with η1 (a) = η1 for all a, and let losses {ℓt }Tt=1 , loss predictions {mt }Tt=1 and {xt }Tt=1 be such that 1 ηt (a)pt (a)(ℓt (a) − mt (a) + xt ) ≥ − 2

for all t, a. Then for any u ∈ △(A), the OFTRL algorithm achieves T T X X X A log AT 2 1 1 ⟨pt − u, ℓt ⟩ ≤ + − log AT 2 η1 ηt+1 (a) ηt (a) t=1 t=1 a +

T X X t=1

ηt (a)pt (a)2 (ℓt (a) − mt (a) + xt )2

T 1 X

T 2 t=1

1 −u + 1, ℓt A

+ 2∥mT +1 ∥∞ .

Regret analysis for the full-information setting (Theorem 4.1)

In this section, we prove the best-of-both-worlds results for the full-information setting. We present the bound for the adversarial regime in Theorem F.10 and the bound for the stochastic regime with adversarial corruption in Theorem F.11. Together, these results establish Theorem 4.1. F.1

Auxiliary lemmas

Building on the policy optimization framework of Luo et al. (2021); Dann et al. (2023), we use the following key lemma to derive our regret bounds. Lemma F.1 (Restatement of Lemma 3.1). Suppose that bt (s) is a nonnegative loss function. Suppose also that, for a comparator policy π, there exists J π ≥ 0 such that " # T X X X π πt E q (s) (πt (a | s) − π(a | s))(Q (s, a; ℓt ) − Bt (s, a)) s

t=1

" T XX

≤J +E

t=1

# T 1 XXX π q (s)πt (a | s)Bt (s, a) . q (s)bt (s) + E H t=1 s a #

(41)

Then, it holds that " T # X B RegT (π) ≤ J π + 3 E V P t ,πt (s0 ; bt ) + E[HT 1[P ∈ / Pt , ∃t ∈ [T ]]], t=1 B where P t ∈ Pt simultaneously attains the maxima in (5) for all (s, a).

To show (41), we choose bt in (9) and decompose the LHS of (41) as X X q π (s) (πt (a | s) − π(a | s))(Qπt (s, a; ℓt ) − Bt (s, a)) s

t,a

q (s)

b t (s, a) − Bt (s, a) (πt (a | s) − π(a | s)) Q

t,a

| +

X s

q π (s)

}

regπ (s)

b t (s, a) . (πt (a | s) − π(a | s)) Qπt (s, a; ℓt ) − Q

(42)

t,a

biasπ (s)

}

Lemma F.2 (full-information setting). The variables bt (s) in (9) and Bt (s, a) in (5) satisfy Bt (s, a) ≤ 2 for all episodes t and state-action pairs (s, a). Proof. We first upper bound the dilated bonus-to-go Bt (s, a) by unrolling the dilated recursion. Since (1 + 1/H)H ≤ 3, we obtain X B Bt (s, a) ≤ 3 q P t ,πt (s′ | s, a) bt (s′ ). (43) s′

By the definition of bt in (9) and the learning-rate update (8), X 1 1 log(T ) bt (s) = 7 − ηt+1 (s, a) ηt (s, a) a X ≤7 ηt (s, a)ζt (s, a) a

≤ 7η1 H 2 , where we used

a ζt (s, a) ≤ H

and ηt (s, a) ≤ η1 .

1 Using η1 = 12H 3 and (43), we get

Bt (s, a) ≤ 3

q P t ,πt (s′ | s, a)bt (s′ ) ≤ 21η1 H 3 ≤ 2.

s′

Lemma F.3 (Dann et al. 2023, Lemma G.3). Let η1 > 0, η2 , η3 , . . . be updated by 1 1 = + η t ϕt ηt+1 ηt

∀t ≥ 1

with 0 ≤ ϕt ≤ ηt−2 . Then, v u t+1 X 1u ϕτ . ≥ t ηt+1 2 τ =1 1

Lemma F.4 (full-information setting). Suppose that the learning rates are updated according to (8). Then, it holds p 2 log(T ) ηt (s, a) ≤ qP t τ =1 ζτ (s, a) for all episodes t and state-action pairs (s, a). t (s,a) Proof. Fix (s, a) and define ϕt (s, a) = ζlog(T ) . Then the update rule of learning rates can be written as 1 1 = + ηt (s, a)ϕt (s, a). ηt+1 (s, a) ηt (s, a)

1 To apply Lemma F.3, we verify that ϕt (s, a) ≤ ηt (s,a) 2 . Indeed,

ϕt (s, a)ηt (s, a)2 =

ηt (s, a)2 ζt (s, a) η2 H 2 H2 1 ≤ 1 ≤ · ≤ 1, log(T ) log(T ) log(T ) 144H 6

1 which follows from η1 = 12H 3.

Then, by Lemma F.3, we have p 2 log(T ) q ≤ P . t τ =1 ϕτ τ =1 ζτ (s, a)

2 ηt (s, a) ≤ qP t

F.2

Common regret analysis

In this part, we upper bound the right-hand side of (41).

Lemma F.5 (full-information setting). For each state s ∈ S and any comparator policy π, it holds that T T X 1 XX regπ (s) ≤ O H 3 A log(T ) + bt (s) + πt (a | s)Bt (s, a). H t=1 a t=1

b t (s, a) − Bt (s, a) for each s ∈ S. Proof. We will apply Lemma E.1 with pt = πt (· | s) and ℓt = Q To do so, in what follows, we will check the conditions of Lemma E.1. Let E D b t (s, ·) − QP m t ,πt (s, ·; m ) xt = −πt (· | s), Q t ℓ X m =− πt (a | s) QP t ,πt (s, a; ℓt ) − QP t ,πt (s, a; mt ) a

b t (s, a) − Bt (s, a) − QP m t ,πt (s, a; m ) + x and verify that for all (s, a), ηt (s, a)πt (a | s) Q ≥ t t −1/2. Indeed, b t (s, a) − Bt (s, a) − QP m t ,πt (s, a; m ) + x ηt (s, a)πt (a | s) Q t t ≥ ηt (s, a)πt (a | s)(−H − Bt (s, a) − H) 1 ≥ −4η1 H ≥ − , 2 b t (s, a) − QP m t ,πt (s, a; m ) ≤ H, B (s, a) ≤ 2 ≤ where the bounds in the second lines use −H ≤ Q t t 2H from Lemma F.2. Thus, Lemma E.1 implies that, for any comparator policy π, regπ (s) ≤

T X X A log AT 2 1 1 + − log AT 2 η1 ηt+1 (s, a) ηt (s, a) t=1 a +

T X X

2 ℓ m ηt (s, a)πt (a | s)2 QP t ,πt (s, a; ℓt ) − QP t ,πt (s, a; mt ) − Bt (s, a) + xt

t=1

T 1 X

m 1 b −π(· | s) + 1, Qt (s, ·) − Bt (s, ·) + 2 QP t ,πt (s, ·; mT +1 ) + 2 T t=1 A ∞ T XX 1 1 3A log(T ) 6H + 2H + 3 − ≤ + log(T ) η1 T η (s, a) η (s, a) t+1 t t=1 a m

( QP t ,πt (s, ·; mT +1 ) ∞ ≤ H) +2

T X X t=1

ℓ 2 m ηt (s, a)πt (a | s)2 QP t ,πt (s, a; ℓt ) − QP t ,πt (s, a; mt ) + xt ηt (s, a)πt (a | s)2 Bt (s, a)2

≤ O(H 3 A log(T )) + 3

T X X t=1

1 1 − ηt+1 (s, a) ηt (s, a)

log(T )

ℓ 2 m ηt (s, a)πt (a | s)2 QP t ,πt (s, a; ℓt ) − QP t ,πt (s, a; mt ) + xt

stability-term

}

1 XX πt (a | s)Bt (s, a). H t=1 a

(44)

Here, the second inequality follows from T 1 X 1 b −π(· | s) + 1, Q (s, ·) − B (s, ·) t t T 2 t=1 A ≤

T X 1 1 b t (s, ·) − Bt (s, ·) Q −π(· | s) + 1 T2 A 1 t=1

∞

2T · 3H 6H ≤ = , T2 T b t (s, a) ≤ H and Bt (s, a) ≤ 2 from Lemma F.2. where we used −π(· | s) + A1 1 1 ≤ 2, Q It remains to bound the stability-term. Define ℓ

Q(s, a) := QP t ,πt (s, a; ℓt ) − QP t ,πt (s, a; mt ). Since xt = −

πt (b | s)Q(s, b),

we have !2 Q(s, a) −

πt (b | s)Q(s, b)

2

 = (1 − πt (a | s))Q(s, a) −

πt (b | s)Q(s, b)

b̸=a

 2 X ≤ 2(1 − πt (a | s))2 Q(s, a)2 + 2 πt (b | s)Q(s, b) b̸=a 2

≤ 2(1 − πt (a | s)) Q(s, a) X + 2(1 − πt (a | s)) πt (b | s)Q(s, b)2 , b̸=a

Therefore, ℓ 2 m ηt (s, a)πt (a | s)2 QP t ,πt (s, a; ℓt ) − QP t ,πt (s, a; mt ) + xt ℓ 2 X m ≤ 2ηt (s, a)πt (a | s)(1 − πt (a | s)) πt (b | s) QP t ,πt (s, b; ℓt ) − QP t ,πt (s, b; mt ) b

≤ 2ηt (s, a)ζt (s, a), P where the last equality follows from the definition of ζt (s, a) = πt (a | s)(1 − πt (a | s)) b πt (b | ℓ 2 m s) QP t ,πt (s, b; ℓt ) − QP t ,πt (s, b; mt ) . Then, stability-term is evaluated as stability-term =

T X X t=1

≤2

T X X t=1

≤2

ℓ 2 m ηt (s, a)πt (a | s)2 QP t ,πt (s, a; ℓt ) − QP t ,πt (s, a; mt ) + xt

ηt (s, a)ζt (s, a)

T X X t=1

1 1 − ηt+1 (s, a) ηt (s, a)

log(T ),

where the last inequality follows from (8). Combining the above bound on the stability-term with (44), we obtain, for any policy π, T X X 1 1 − log(T ) regπ (s) ≤ O H 3 A log(T ) + 7 ηt+1 (s, a) ηt (s, a) t=1 a T

1 XX πt (a | s)Bt (s, a) H t=1 a T

T X

1 XX = O H A log(T ) + πt (a | s)Bt (s, a). bt (s) + H t=1 a t=1 3

Lemma F.6 (full-information setting). Suppose that the event E holds. Then, for any comparator policy π, it holds that X p 1:T q π (s)biasπ (s) ≲ S 2 Aι2 Qπtrans (ℓ) + HS 3 Aι2 . (45) s

Also, X

q π (s)biasπ (s) ≲

v T X u tH 2 |Sh ||Sh+1 |Aι2

H−1 Xu

[q πt (s, a) − q π (s, a)]+

t=1 (s,a)∈Sh ×A

h=0 2

+ HS Aι . Proof. X

q π (s)biasπ (s) =

q π (s)

(46)

X ℓ (πt (a | s) − π(a | s)) Qπt (s, a; ℓt ) − QP t ,πt (s, a; ℓt ) t,a

T X X

(q πt (s, a) − q π (s, a))zt (s, a),

t=1 s,a

where, for each t, Lemma D.2 is applied with ℓ

L(s, a) = Qπt (s, a; ℓt ) − QP t ,πt (s, a; ℓt ). Thus, ℓ

zt (s, a) = Qπt (s, a; ℓt ) − QP t ,πt (s, a; ℓt ) h i ℓ − Es′ ∼P (·|s,a),a′ ∼πt (·|s′ ) Qπt (s′ , a′ ; ℓt ) − QP t ,πt (s′ , a′ ; ℓt ) . Expanding the definition of zt (s, a), we obtain h ℓ i zt (s, a) = Es′ ∼P (·|s,a),a′ ∼πt (·|s′ ) [Qπt (s′ , a′ ; ℓt )] − Es′ ∼P ℓt (·|s,a),a′ ∼πt (·|s′ ) QP t ,πt (s′ , a′ ; ℓt ) h i ℓ − Es′ ∼P (·|s,a),a′ ∼πt (·|s′ ) Qπt (s′ , a′ ; ℓt ) − QP t ,πt (s′ , a′ ; ℓt ) h ℓ h ℓ i i = Es′ ∼P (·|s,a),a′ ∼πt (·|s′ ) QP t ,πt (s′ , a′ ; ℓt ) − Es′ ∼P ℓt (·|s,a),a′ ∼πt (·|s′ ) QP t ,πt (s′ , a′ ; ℓt ) i h ℓ i h ℓ = Es′ ∼P (·|s,a) V P t ,πt (s′ ; ℓt ) − Es′ ∼P ℓt (·|s,a) V P t ,πt (s′ ; ℓt ) . By the definition of P ℓt , which minimizes Q(s, a; ℓt ) for all (s, a), we have zt (s, a) ≥ 0.

First, we show (45). By the fact that zt (s, a) ≥ 0, T X X

(q πt (s, a) − q π (s, a))zt (s, a) ≤

t=1 s,a

T X

V πt (s0 ; zt )

t=1

≤

T X

ℓ V πt (s0 ; ℓt ) − V P t ,πt (s0 ; ℓt )

(by Lemma D.2)

t=1

T X X t=1

X ℓ q πt (s) − q P t ,πt (s) πt (a | s)ℓt (s, a). (47)

Applying Lemma D.5 to (47), we obtain T X X

(q πt (s, a) − q π (s, a))zt (s, a) ≲

1:T S 2 Aι2 Qπtrans (ℓ) + HS 3 Aι2 .

t=1 s,a

This proves (45). Next, we show (46). By Lemma D.4, ℓ X zt (s, a) = P (s′ | s, a) − P ℓt (s′ | s, a) V P t ,πt (s′ ; ℓt ) s′

s ≲

ℓ Sh(s)+1 Vars′ ∼P (·|s,a) V P t ,πt (s′ ; ℓt ) ι |Sh(s)+1 |Hι + . nt (s, a) nt (s, a)

Using zt (s, a) ≥ 0, we further have T X X

(q πt (s, a) − q π (s, a))zt (s, a)

t=1 s,a

≤

T X X

[q πt (s, a) − q π (s, a)]+ zt (s, a)

t=1 s,a

s

h=0

(s,a)∈Sh ×A

T X X

q πt (s, a)

t=1 s,a

|Sh(s)+1 |Hι . nt (s, a)

(48)

Here, by the Cauchy–Schwarz inequality, the first term in (48) is bounded as s ℓ T X X |Sh+1 |Vars′ ∼P (·|s,a) V P t ,πt (s′ ; ℓt ) ι πt π [q (s, a) − q (s, a)]+ nt (s, a) t=1 (s,a)∈Sh ×A v uX X u T ≤t [q πt (s, a) − q π (s, a)]+ t=1 (s,a)∈Sh ×A

v uX u T ×t

P ℓ ,π t (s′ ; ℓ ) ι t ′ ∼P (·|s,a) V |S |Var h+1 t s [q πt (s, a) − q π (s, a)]+ . nt (s, a)

t=1 (s,a)∈Sh ×A

The term inside the second square root is further bounded as T X

[q πt (s, a) − q π (s, a)]+

i h ℓ |Sh+1 |Vars′ ∼P (·|s,a) V P t ,πt (s′ ; ℓt ) ι nt (s, a)

t=1 (s,a)∈Sh ×A

≤ H 2 |Sh+1 |

T X

t=1 (s,a)∈Sh ×A

q πt (s, a)ι nt (s, a)

≲ H |Sh ||Sh+1 |Aι2 .

(by Lemma C.3)

The second term in (48) is bounded as T X X

q πt (s, a)

t=1 s,a

H−1 T X X |Sh(s)+1 |Hι ≤ |Sh+1 | nt (s, a) t=1 h=0

≲H

H−1 X

X (s,a)∈Sh ×A

q πt (s, a)

Hι nt (s, a)

|Sh+1 ||Sh |Aι2

h=0

≤ HS 2 Aι2 . Therefore, T X X (q πt (s, a) − q π (s, a))zt (s, a) t=1 s,a

≲

v T X u tH 2 |Sh ||Sh+1 |Aι2

H−1 Xu

[q πt (s, a) − q π (s, a)]+ + HS 2 Aι2

t=1 (s,a)∈Sh ×A

h=0

This proves (46), and hence completes the proof. Lemma F.7 (full-information setting). Suppose that the event E holds. Then, it holds that v u T T uX X X B 3 5 3 P t ,πt t V q πt (s)ζ (s, a) + H 2 S 2 A 2 log(T )ι. (s ; b ) ≲ log(T ) 0

s,a

t=1

Proof. By the definition of bt and the ηt , we have T X

V P t ,πt (s0 ; bt )

t=1

T X X t=1

≲

q P t ,πt (s)bt (s)

T X X

B q P t ,πt (s)

t=1 s,a

≲

T X X

1 1 − ηt+1 (s, a) ηt (s, a)

log(T )

q P t ,πt (s)ηt (s, a)ζt (s, a)

t=1 s,a

p p T X P B ,πt X q t (s) ζt (s, a) × ζt (s, a) qP (by Lemma F.4) t t=1 s,a ζ (s, a) τ =1 τ v v u T u T uX B X uX p ζt (s, a) t t ≤ log(T ) q P t ,πt (s)2 ζt (s, a) Pt ζ (s, a) τ =1 τ s,a t=1 t=1 (by the Cauchy–Schwarz inequality) ≲

log(T )

v u T X uX B t ≲ log(T ) q P t ,πt (s)ζ (s, a),

(49)

s,a

t=1

where the last inequality uses v v ! u u T T u uX X p ζt (s, a) t t ≤ 1 + log ζt (s, a) ≲ log(T ) Pt τ =1 ζτ (s, a) t=1 t=1 B

together with q P t ,πt (s)2 ≤ q P t ,πt (s). B PT We further bound t=1 q P t ,πt (s)ζt (s, a) for each fixed (s, a). We decompose it as T X

q P t ,πt (s)ζt (s, a) =

t=1

T X

q πt (s)ζt (s, a) +

t=1

T X

B q P t ,πt (s) − q πt (s) ζt (s, a).

(50)

t=1

To bound the second term, define gts,a (s′ ) := 1[s′ = s]ζt (s, a) ≤ H 2 . Applying Lemma D.7 with this choice of gts,a yields T X

T X X B B q P t ,πt (s′ ) − q πt (s′ ) gts,a (s′ ) q P t ,πt (s) − q πt (s) ζt (s, a) = t=1 s′

t=1

v u T X u X 2 ≲ tHS 2 Aι2 q πt (s′ )(gts,a (s′ )) + H 3 S 3 Aι2 t=1 s′

v u T u X = tHS 2 Aι2 q πt (s)ζt (s, a)2 + H 3 S 3 Aι2 t=1

v u T u X ≤ tH 3 S 2 Aι2 q πt (s)ζt (s, a) + H 3 S 3 Aι2 . t=1

Combining this with (50), we obtain T X

B P t ,πt

(s)ζt (s, a) ≲

t=1

T X

v u T u X πt q (s)ζt (s, a) + tH 3 S 2 Aι2 q πt (s)ζt (s, a) + H 3 S 3 Aι2

t=1

≲

T X

t=1

q πt (s)ζt (s, a) + H 3 S 3 Aι2 ,

(51)

t=1

where the second line follows from the AM–GM inequality since ax + a, b, x ≥ 0.

√

b bx ≤ ax + ax + 2a for

By (49) and (51), we obtain T X

v u T uX X B P t ,πt t V (s ; b ) ≲ log(T ) q πt (s)ζ (s, a) + H 3 S 3 Aι2 0

t=1

s,a

t=1

v u T X uX 3 5 3 t ≤ log(T ) q πt (s)ζ (s, a) + H 2 S 2 A 2 log(T )ι. t

s,a

t=1

This completes the proof.

Lemma F.8 (full-information setting). For any comparator policy π, Algorithm 1 guarantees v " T # u Xu X 3 2 3 2 2 t π t log (T )E q (s)ζ (s, a) Reg (π) ≲ HS A ι + t

s,a

+ min

( p

t=1

1:T S 2 Aι2 E[Qπtrans (ℓ)],

v  u T X u 2 tH |Sh ||Sh+1 |Aι2 E

)

H−1 Xu

[q πt (s, a) − q π (s, a)]+  .

t=1 (s,a)∈Sh ×A

h=0

Proof. By the definition of the regret decomposition in (42), " # X X π πt E q (s) (πt (a | s) − π(a | s))(Q (s, a; ℓt ) − Bt (s, a)) s

t,a

" =E

# X

q (s) · reg (s) + E

# X

q (s) · bias (s)

s 4

= O H A log(T ) + E

" T XX t=1

" X

# T 1 XX π X q (s) πt (a | s)Bt (s, a) q (s)bt (s) + E H t=1 s a #

# q π (s) · biasπ (s) ,

where we used Lemma F.5. Combining this with Lemma F.1 and δ = O(1/T 2 ), for any comparator policy π, we obtain " T # " # X X B π 4 P t ,πt π RegT (π) ≤ O H A log(T ) + 3E V (s0 ; bt ) + E q (s) · bias (s) . s

t=1 2

Here, by Lemma F.7 and Jensen’s inequality, with δ = 1/T , we obtain v " # # " T u T Xu X X B 3 5 3 P t ,πt t (s0 ; bt ) ≲ log(T ) E q πt (s)ζt (s, a) + H 2 S 2 A 2 log(T )ι E V s,a

t=1

+ O(δ) × O(HT ), B PT where we used the trivial bound t=1 V P t ,πt (s0 ; bt ) ≤ O(HT ) on Ē from Lemma F.2. Then, using δ = T12 , we have v " # " # u T Xu X X π π t π RegT (π) ≲ H S A log(T )ι + log(T ) E q t (s)ζt (s, a) + E q (s) · bias (s) , 3 2

5 2

3 2

s,a

t=1

(52) By (52) and Lemma F.6 and Jensen’s inequality, together with the trivial bound O(H 2 T ) on Ē and the choice δ = O(1/T 2 ), we obtain, for any policy π, v " # u T u X X 3 5 3 tE RegT (π) ≲ H 2 S 2 A 2 log(T )ι + log(T ) q πt (s)ζt (s, a) s,a

+ min

( p

t=1

1:T S 2 Aι2 E[Qπtrans (ℓ)],

v  u T X u 2 tH |Sh ||Sh+1 |Aι2 E

H−1 Xu

[q πt (s, a) − q π (s, a)]+ 

t=1 (s,a)∈Sh ×A

h=0 3

) X

+ HS Aι + O(δ) × O(H T ) v " T # u u X X 3 2 tlog (T )E ≲ HS 3 A 2 ι2 + q πt (s)ζ (s, a) t

s,a

+ min

( p

t=1

1:T S 2 Aι2 E[Qπtrans (ℓ)],

v  u T X u 2 tH |Sh ||Sh+1 |Aι2 E

H−1 Xu

) X

[q πt (s, a) − q π (s, a)]+  .

t=1 (s,a)∈Sh ×A

h=0

This completes the proof. F.3

Proof for the adversarial regime

Lemma F.9 (full-information setting). It holds that v " T # u Xu X tlog2 (T )E π t q (s)ζt (s, a) s,a

t=1

v # " T u XX u 2 e,πt 2 t π P t (s, a; (ℓt − mt ) ) . ≲ HSA log (T )E q (s, a) max Q e∈Pt P

t=1 s,a

Proof. By the definition of ζt (s, a), we have v " T # u Xu X tlog2 (T )E π t q (s)ζt (s, a) s,a

t=1

v " T # u Xu X X 2 ℓ ,π m ,π 2 t P P π t t t = log (T )E q (s, a)(1 − πt (a | s)) πt (b | s) Q t (s, b; ℓt ) − Q t (s, b; mt ) s,a

t=1

v # " T u u XX X 2 ℓ ,π m ,π 2 t P P π t t q t (s) π (b | s) Q t (s, b; ℓ ) − Q t (s, b; m ) , ≤ SA log (T )E t

t=1

where the inequality follows from the Cauchy–Schwarz inequality. ℓ

We next bound QP t ,πt (s, b; ℓt ) − QP t ,πt (s, b; mt ). ℓ

QP t ,πt (s, a; ℓt ) − QP t ,πt (s, a; mt ) ℓ m m m = QP t ,πt (s, a; ℓt ) − QP t ,πt (s, a; ℓt ) + QP t ,πt (s, a; ℓt ) − QP t ,πt (s, a; mt ) m

≤ 0 + QP t ,πt (s, a; ℓt − mt ) ≤ max QP ,πt (s, a; |ℓt − mt |). e

e∈Pt P

Similarly, ℓ

QP t ,πt (s, a; ℓt ) − QP t ,πt (s, a; mt ) ≥ − max QP ,πt (s, a; |ℓt − mt |) e

e∈Pt P

(53)

≤

q Pe,πt (s′ , a′ | s, a)

s′ ,a′

q Pe,πt (s′ , a′ | s, a)(ℓt (s′ , a′ ) − mt (s′ , a′ ))2

s′ ,a′

q ≤ HQPe,πt (s, a; (ℓt − mt )2 ). Therefore,

ℓ

QP t ,πt (s, a; ℓt ) − QP t ,πt (s, a; mt )

≤

2 e max QP ,πt (s, a; |ℓt − mt |)

e∈Pt P 2

≤ H max QP ,πt (s, a; (ℓt − mt ) ) e

(54)

e∈Pt P

Combining this with (53) completes the proof. Theorem F.10 (full-information setting). For any comparator policy π, Algorithm 1 guarantees q RegT (π) ≲ H 2 SA log2 (T ) min{L(π), HT − L(π), Q∞ , V1 } q 3 1:T (ℓ)] + HS 3 A 2 log2 (T ). + S 2 A log2 (T )E[Qπtrans Proof. By Lemmas D.9, F.8 and F.9 and the choice δ = 1/T 2 , which implies ι ≲ log(T ), we have, for any policy π, v # " T u XX u 3 2 e Reg (π) ≲ HS 3 A 2 log2 (T ) + tHSA log2 (T )E q πt (s, a) max QP ,πt (s, a; (ℓt − mt ) ) T

t=1 s,a

e∈Pt P

1:T S 2 A log2 (T )E[Qπtrans (ℓ)] v " T # u u X 2 2 2 3 32 ≲ HS A log (T ) + tH 2 SA log (T )E V πt (s0 ; (ℓt − mt ) )

t=1

1:T S 2 A log2 (T )E[Qπtrans (ℓ)].

Combining this with Lemma D.11, we obtain q RegT (π) ≲ H 2 SA log2 (T ) min{L(π) + RegT (π), HT − L(π) − RegT (π), Q∞ , V1 } q 3 1:T + S 2 A log2 (T )E[Qπtrans (ℓ)] + HS 3 A 2 log2 (T ). (55) Now, we derive the first-order bound. By (55), there exists an absolute constant c > 0 such that q q 3 RegT (π) ≤ cHS 3 A 2 log2 (T ) + c H 2 SA log2 (T )L(π) + c H 2 SA log2 (T )RegT (π) q 1:T + c S 2 A log2 (T )E[Qπtrans (ℓ)] q 3 c2 1 ≤ cHS 3 A 2 log2 (T ) + c H 2 SA log2 (T )L(π) + H 2 SA log2 (T ) + RegT (π) 2 2 q 1:T + c S 2 A log2 (T )E[Qπtrans (ℓ)], where the last inequality follows from the AM–GM inequality. Thus, we obtain q q 3 1:T RegT (π) ≲ HS 3 A 2 log2 (T ) + H 2 SA log2 (T )L(π) + S 2 A log2 (T )E[Qπtrans (ℓ)]. 45

(56)

Furthermore, we derive the bound in terms of HT − L(π). If RegT (π) < 0, the desired upper bound is trivial. Otherwise, RegT (π) ≥ 0 and (55) gives q q 3 1:T (ℓ)] RegT (π) ≲ HS 3 A 2 log2 (T ) + H 2 SA log2 (T )(HT − L(π) − RegT (π)) + S 2 A log2 (T )E[Qπtrans q q 3 1:T ≤ HS 3 A 2 log2 (T ) + H 2 SA log2 (T )(HT − L(π)) + S 2 A log2 (T )E[Qπtrans (ℓ)]. (57) Combining (55)–(57) completes the proof. F.4

Proof for the stochastic regime with adversarial corruption

Theorem F.11 (full-information setting). Under the stochastic regime with adversarial corruption, Algorithm 1 guarantees that, for any policy π, √ 3 RegT (π) ≲ U + U C + HS 3 A 2 log2 (T ), 2

log (T ) . where U = H S ∆Amin

Proof. Since RegT (π) ≤ RegT (π̊) for all π, it suffices to bound RegT (π̊). From Lemma F.8 and the choice δ = 1/T 2 , which implies ι ≲ log(T ), we have v " # u T X X u X 3 2 3 2 t π RegT (π̊) ≲ HS A log (T ) + 2H log(T ) E q t (s, a) s

a̸=π ⋆ (s)

t=1

v  u H−1 T Xu X u 2 tH |Sh ||Sh+1 |A log2 (T )E +

 [q πt (s, a) − q π̊ (s, a)]+ .

t=1 (s,a)∈Sh ×A

h=0

Applying Lemmas D.16 and D.17, for any α > 0, we get   X X H 2 log2 (T ) 3 RegT (π̊) ≤ α(2RegT (π̊) + 6C) + O + HS 3 A 2 log2 (T ) α∆(s, a) ⋆ s a̸=π (s)  2  q PH−1 2 2 H |Sh ||Sh+1 |A log (T )   h=0   + O . 4α∆min   Here, H−1 Xq

!2 2

H 2 |Sh ||Sh+1 |A log (T )

h=0

Then, using (58) and choosing α = min

!2 q 1 2 ≤ (|Sh | + |Sh+1 |) H 2 A log (T ) 2 h=0 (by the AM–GM inequality) q 2 = S H 2 A log2 (T ) = H 2 S 2 A log2 (T ). (58)

1 4,

H−1 X

q o U C

√ RegT (π̊) ≲ U +

log (T ) with U = H S ∆Amin , we get 3

U C + HS 3 A 2 log2 (T ).

Therefore, since RegT (π) ≤ RegT (π̊) for all π by the definition of π̊, the desired bound follows.

Regret analysis for the bandit setting (Theorem 4.2)

In this section, we prove the best-of-both-worlds results for the bandit setting. We present the bound for the adversarial regime in Theorem G.12 and the bound for the stochastic regime with adversarial corruption in Theorem G.13. Together, these results establish Theorem 4.2. Throughout this section, virtual episodes are inserted into the episode sequence, shifting the indices of subsequent real episodes. All algorithmic sums over t = 1, . . . , T include virtual episodes, while the data-dependent complexity measures in the main statements are defined only over real episodes. We denote by Tr = {t ∈ [T ] : Yt = 1} and Tv = {t ∈ [T ] : Yt = 0} the sets of real and virtual episodes, with sizes |Tr | and |Tv |, respectively. G.1

Auxiliary lemmas

Following the full-information setting, Lemma F.1 reduces the regret analysis to proving (41). With the choice of bt in (15), we decompose the left-hand side of (41) as X X q π (s) (πt (a | s) − π(a | s))(Qπt (s, a; ℓt ) − Bt (s, a)) s

t,a

q (s)

b t (s, a) − Bt (s, a) (πt (a | s) − π(a | s)) Q

t,a

| +

}

regπ (s)

q π (s)

X b t (s, a) + QP m t ,πt (s, a; m ) − Qπt (s, a; m ) (πt (a | s) − π(a | s)) Qπt (s, a; ℓt ) − Q t t

t,a

| +

q π (s)

}

biasπ (s)

X m (πt (a | s) − π(a | s)) Qπt (s, a; mt ) − QP t ,πt (s, a; mt ) .

(59)

t,a

}

errorπ (s)

Lemma G.1 (bandit setting). It holds that qt (s)πt (a | s)Ct (s, a) ≤ 6HS,

Et [Ct (s, a)] ≤ 4HS

(60)

for any episode t and state-action pair (s, a). Proof. We first prove a conditional occupancy property. For any Pe ∈ Pt , any states s, s′ with h(s′ ) > h(s), and any actions a, a′ , we have qt (s)πt (a | s)q P ,πt (s′ , a′ | s, a) ≤ qt (s′ )πt (a′ | s′ ). e

Hence, q πt t (s′ ) ≥ q πt t (s)πt (a | s)q P ,πt (s′ | s, a). e

Using qt (x) = q πt t (x) + γt and πt (a | s)q P ,πt (s′ | s, a) ≤ 1, we obtain e

= qt (s)πt (a | s)q P ,πt (s′ , a′ | s, a), e

which proves (61).

(61)

≤2

ρt (s′ )It (s′ , a′ )Dt,h(s′ ) + 2H

s′ ,a′

qt (s′ )πt (a′ | s′ )ρt (s′ )2 .

(62)

s′ ,a′

Since ρt (s′ ) ≤ 1, Dt,h(s′ ) ≤ H, X

ρt (s′ )It (s′ , a′ )Dt,h(s′ ) ≤ 2H 2 .

s′ ,a′

Moreover, using ρt (s′ ) ≤ 1 and

′ ′ ′ s′ ,a′ qt (s )πt (a | s ) ≤ S + Sγt ≤ 2S,

qt (s′ )πt (a′ | s′ )ρt (s′ )2 ≤ 4HS.

s′ ,a′

Combining the last three displays gives qt (s)πt (a | s)Ct (s, a) ≤ 6HS. This proves the first inequality in (60). C

We next prove the second inequality. Let P t be a measurable transition kernel that attains the maximum in (13). Then, it holds that X C q P t ,πt (s′ , a′ | s, a)ct (s′ , a′ ). Ct (s, a) ≤ 2 s′ ,a′ C

By using q P t ,πt (s′ , a′ | s, a) ≤ πt (a′ | s′ ), we get X Et [Ct (s, a)] ≤ 2 πt (a′ | s′ )Et [ct (s′ , a′ )]. s′ ,a′

Therefore, using Et [ct (s′ , a′ )] ≤ 2H, Et [Ct (s, a)] ≤ 2

πt (a′ | s′ ) · 2H = 4HS,

s′ ,a′

which proves the second inequality. Lemma G.2 (bandit setting). The variables bt (s) in (15) and Bt (s, a) in (5) satisfy √ 1 7 HS 3 A ηt (s, a)πt (a | s)Bt (s, a) ≤ , Bt (s, a) ≤ 6H γt for any episode t and state-action pair (s, a). Proof. Let Rt = maxs,a ηqt t(s,a) (s) . We first consider the case when t is a real episode. In real episodes, by the definition of bt , X X 1 1 bt (s) = 6 − log(T ) + 3 ηt (s, a)πt (a | s)2 Ct (s, a)2 η (s, a) η (s, a) t+1 t a a

For the first term, the learning-rate update gives X 1 1 − log(T ) 6 ηt+1 (s, a) ηt (s, a) a 6 X ηt (s, a)ζt (s, a) = qt (s)2 a 2 6 X 2 = ηt (s, a)(It (s, a) − πt (a | s)It (s)) Lt,h(s) − Mt,h(s) 2 qt (s) a ≤

X 6H 2 2 max η (s, a) (It (s, a) − πt (a | s)It (s)) t qt (s)2 a a

12H 2 max ηt (s, a) qt (s)2 a 12H 2 ηt (s, a) ≤ max . qt (s) a qt (s) ≤

(63)

For the second term, by Lemma G.1, 3

ηt (s, a)πt (a | s)2 Ct (s, a)2 = 3

X ηt (s, a)qt (s)2 πt (a | s)2 Ct (s, a)2

qt (s)2

P 2

108H 2 S a ηt (s, a) qt (s)2 108H 2 S 2 A ηt (s, a) ≤ max . a qt (s) qt (s) ≤

(by Lemma G.1) (64)

Combining (63) and (64), we obtain bt (s) ≤

12H 2 + 108H 2 S 2 A ηt (s, a) 120H 2 S 2 A ηt (s, a) max ≤ max a a qt (s) qt (s) qt (s) qt (s)

(65)

Using (43) and (65), we have Bt (s, a) ≤ 3

H−1 X

q P t ,πt (s′ | s, a)bt (s′ )

h=h(s) s′ ∈Sh

 ≤ 360H 2 S 2 ARt 

H−1 X

B P t ,πt

h=h(s) s′ ∈Sh

 ≤ 360H 2 S 2 ARt 

H−1 X

 1  (s′ | s, a) qt (s′ ) 

B P t ,πt

 (s′ | s, a) π B q t t (s)πt (a | s)q P t ,πt (s′ | s, a) + γt  X 1  q πt t (s)πt (a | s) + γt ′ q

h=h(s) s′ ∈Sh

 ≤ 360H 2 S 2 ARt 

H−1 X

h=h(s) s ∈Sh

1 ≤ 360H 2 S 3 ARt · πt q t (s)πt (a | s) + γt √ 3 7 HS A ≤ , γt

(66)

where in the last line we used Rt ≤ 50√H13 S 3 A that holds in real episodes. By using (66), we also have ηt (s, a)πt (a | s)Bt (s, a) ≤ 360H 2 S 3 ARt · 49

ηt (s, a)πt (a | s) q πt t (s)πt (a | s) + γt

≤ 360H 2 S 3 ARt ·

ηt (s, a) qt (s)

≤ 360H 2 S 3 ARt2 1 , ≤ 6H where we used q πt t (s)πt (a | s) + γt ≥ qt (s)πt (a | s), ηqt t(s,a) (s) ≤ Rt . We next consider the case when t is a virtual episode. In a virtual episode, only the single pair (s†t , a†t ) is updated, and thus X 1 1 bt (s) = 6 − log(T ) ηt+1 (s, a) ηt (s, a) a ≤

X 1{(s† , a† ) = (s, a)}

54Hqt (s)

54ηt (s, a)H

1{s†t = s} qt (s)

1 ′

′

,a ) maxs′ ,a′ ηtq(s ′ t (s )

1 ′

′

,a ) 54H maxs′ ,a′ ηtq(s ′ t (s )

(since (s†t , a†t ) ∈ arg maxs,a ηqt t(s,a) (s) )

(67)

Using (43) and (67), we have Bt (s, a) ≤ 3

H−1 X

q P t ,πt (s′ | s, a)bt (s′ )

h=h(s) s′ ∈Sh

≤

H−1 X X B 1 1{s†t = s′ } q P t ,πt (s′ | s, a) 18HRt qt (s′ ) ′ h=h(s) s ∈Sh

≤

H−1 X X B 1{s†t = s′ } 1 q P t ,πt (s′ | s, a) π B 18HRt q t (s)πt (a | s)q P t ,πt (s′ | s, a) + γt ′ h=h(s) s ∈Sh

≤

1 18HRt

H−1 X

h=h(s) s′ ∈Sh

{s†t = s′ }

q πt t (s)πt (a | s) + γt

1 1 18HRt q πt t (s)πt (a | s) + γt √ 3 HS 3 A ≤ , γt ≤

(68)

where in the last inequality we used Rt > 50√H13 S 3 A in a virtual episode. By using (68), we also have 1 ηt (s, a)πt (a | s) 18HRt q πt t (s)πt (a | s) + γt 1 ηt (s, a) ≤ 18HRt qt (s) 1 1 ≤ ≤ , 18H 6H

ηt (s, a)πt (a | s)Bt (s, a) ≤

where we used q πt t (s)πt (a | s) + γt ≥ qt (s)πt (a | s), ηqt t(s,a) (s) ≤ Rt . This completes the proof. The following two lemmas are based on the Li et al. (2026, Lemmas E.5 and E.6). We adapt the proof to our choice of γt and our virtual-episode rule, and include the details for completeness. 50

Lemma G.3 (bandit setting). Suppose that the learning rates are updated according to (14). Then, it holds p 2 log(T ) ηt (s, a) ≤ qP ζτ (s,a) τ ≤t:τ ∈Tr qτ (s)2

for any episode t and state-action pair (s, a). I{(s† ,a† )=(s,a)}

ζt (s,a) t t Proof. Let ϕt (s, a) = qt (s) 2 log(T ) in real episodes and ϕt (s, a) = 324η (s,a)2 H log(T ) in virtual t episodes. Then the update rule of learning rates can be written as

1 1 = + ηt (s, a)ϕt (s, a). ηt+1 (s, a) ηt (s, a) 1 To apply Lemma F.3, it suffices to show that ϕt (s, a) ≤ ηt (s,a) 2 . This is clear for virtual episodes. For real episodes, 2 ηt (s, a)2 ζt (s, a) H2 ηt (s, a) H2 1 ϕt (s, a)ηt (s, a)2 = ≤ ≤ · ≤ 1, 2 qt (s) log(T ) log(T ) qt (s) log(T ) 502 H 3 S 3 A √ 1 which follows from ζt (s, a) ≤ H 2 and ηqt t(s,a) (s) ≤ 50 H 3 S 3 A in real episodes.

Then, by Lemma F.3, we have ηt (s, a) ≤ qP

τ ≤t ϕτ

≤ qP

p log(T )

ζτ (s,a) τ ≤t:τ ∈Tr qτ (s)2

In the following lemma only, we use T to denote the number of real episodes rather than the total number of episodes. Lemma G.4 (bandit setting). When the number of real episodes is T , the number of virtual episodes |Tv | is upper bounded by |Tv | ≲ HSA log2 (T ). Proof. By the definition of virtual episodes, whenever t ∈ Tv , there exists a pair (s, a) such that ηt (s,a) √ 1 . Moreover, in virtual episodes, the corresponding learning rate will shrink by qt (s) > 50 H 3 S3 A 1 a factor of 1 + 324H log(|T for a state-action pair (s†t , a†t ). r |+|Tv |) Therefore, for each fixed (s, a), a virtual update on this pair can occur only while ηt (s, a) >

√

1 H 3 S 3 A(|Tr | + |Tv |)

Thus, the number of virtual updates on this√ pair is at most the number of multiplicative shrink steps needed to reduce ηt (s, a) from η1 to 1/(50 H 3 S 3 A(|Tr | + |Tv |)). Hence, √ log η1 H 3 S 3 A(|Tr | + |Tv |) |Tv | ≲ SA 1 log 1 + 324H log(|T r |+|Tv |) ≲ HSA log2 (|Tr | + |Tv |), where we used log(1 + x) ≥ x/2 for x ∈ (0, 1], η1 = 1/(12H 3 ), and H, S, A ≤ |Tr |. This implies |Tv | ≲ HSA log2 (|Tr |). Since |Tr | = T , the desired bound follows. 51

Lemma G.5 (bandit setting). Suppose that the event E holds. Then, it holds that XX q πt (s)ρt (s)2 ≲ HS 3 Aι2 . s

t∈Tr

Proof. Recall that ρt (s) = XX

qt (s) − q πt t (s) qt (s)

πt

q (s, a)ρt (s, a) ≤

t∈Tr s,a

and qt (s) = q πt t (s) + γt . Then, we have

q πt t (s) − q πt t (s) + γt

πt

q (s)

qt (s)

t∈Tr

 ≤

q πt (s)2

≤2

q πt t (s) − q πt t (s)

πt

q (s)

q πt t (s) − q πt t (s)

γt qt (s)

γt

 

!2 +2

qt (s)

t∈Tr

qt (s)

t∈Tr

We bound the first term. By Lemma D.7, we obtain !2 XX q πt t (s) − q πt t (s) πt q (s) qt (s) s t∈Tr

≤

X X t∈Tr

q πt (s) − q πt (s)

q πt t (s) − q πt t (s)

qt (s)

v !2 u πt πt (s) u XX (s) − q q t t + cHS 3 Aι2 . ≤ ctHS 2 Aι2 q πt (s) qt (s) s t∈Tr

(for some absolute constant c) √

Now use the fact that if x ≤ a x + b with x, a, b ≥ 0, then x ≤ 2a2 + 2b, we obtain !2 XX q πt t (s) − q πt t (s) πt q (s) ≲ HS 2 Aι2 + HS 3 Aι2 ≲ HS 3 Aι2 . q (s) t s t∈Tr

We also have 2

XX t∈Tr

Combining the above bounds gives XX t∈Tr

γt ≤ 2S log(T )

q πt (s)ρt (s)2 ≲ HS 3 Aι2 .

Lemma G.6 (bandit setting). Suppose that the event E holds. Then, it holds that XX qt (s)ρt (s)2 ≲ HS 3 Aι2 . t∈Tr

Proof. We decompose XX qt (s′ )ρt (s′ )2 t∈Tr s′

q πt (s′ )ρt (s′ )2 +

t∈Tr s′

(q πt t (s′ ) − q πt (s′ ))ρt (s′ )2 +

t∈Tr s′ terma

}

γt ρt (s′ )2 .

t∈Tr s′

termb

}

termc

}

For terma , by Lemma G.5, terma ≲ HS 3 Aι2 . For termb , applying Lemma D.7 with gt (s) = ρt (s)2 and Lemma G.5, we obtain s XX termb ≲ HS 2 Aι2 q πt (s)ρt (s)4 + HS 3 Aι2 t∈Tr

≲

HS 2 Aι2 · S 4 A log(T )ι + HS 3 Aι2

≲ HS 3 Aι2 , For termc , since ρt (s′ ) ≤ 1, termc ≤

γt ≲ S log(T ).

t∈Tr s′

Thus, we have XX t∈Tr

G.2

qt (s)ρt (s)2 ≲ HS 3 Aι2 .

Common regret analysis

Now we upper bound the right-hand side of (59). Lemma G.7 (bandit setting). For each state s ∈ S and any comparator π, it holds that " T # " # T X 1 XX π 2 E[reg (s)] ≤ O HS A log(T ) + E bt (s) + E πt (a | s)Bt (s, a) . H t=1 a t=1 b t (s, a) − Bt (s, a) for each s ∈ S. Proof. We will apply Lemma E.1 with pt = πt (· | s) and ℓt = Q To do so, in what follows, we will check the conditions of Lemma E.1. Let E D It (s)(Lt,h(s) − Mt,h(s) ) b t (s, ·) − QP m t ,πt (s, ·; m ) + C (s, ·)Y xt = −πt (· | s), Q Yt t t t =− qt (s) b t (s, a) − Bt (s, a) − QP m t ,πt (s, a; m ) + x ≥ and verify that for all (s, a), ηt (s, a)πt (a | s) Q t t −1/2. Recall that in a virtual episode we have Yt = 0 and ℓt (s, a) = 0 for all state-action pairs (s, a). Then, we have b t (s, a) − Bt (s, a) − QP m t ,πt (s, a; m ) + x ηt (s, a)πt (a | s) Q t t It (s, a)(Lt,h(s) − Mt,h(s) ) It (s)(Lt,h(s) − Mt,h(s) ) = ηt (s, a)πt (a | s) Yt − Yt qt (s)πt (a | s) qt (s) − Bt (s, a) − Ct (s, a)Yt 2ηt (s, a)H Yt − ηt (s, a)πt (a | s)Bt (s, a) − ηt (s, a)πt (a | s)Ct (s, a)Yt qt (s) 1 1 1 ≥− − ≥− . 3 6H 2 where we used 0 ≤ Lt,h(s) , Mt,h(s) ≤ H and Ct ≥ 0. The last inequality uses ηt (s, a)/qt (s) ≤ √ 1/(50 H 3 S 3 A) in real episodes, Lemmas G.1 and G.2. Indeed, ≥−

2ηt (s, a)H ηt (s, a) + ηt (s, a)πt (a | s)Ct (s, a) = (2H + qt (s)πt (a | s)Ct (s, a)) qt (s) qt (s) 2H + 6HS 1 ≤ √ ≤ , 3 50 H 3 S 3 A 53

and ηt (s, a)πt (a | s)Bt (s, a) ≤

1 . 6H

Hence, by Lemma E.1, we obtain E[regπ (s)] " T # X X A log AT 2 1 1 2 ≤ +E − log AT η1 ηt+1 (s, a) ηt (s, a) t=1 a " T # 2 XX m b t (s, a) − QP t ,πt (s, a; mt ) − Bt (s, a) + xt +E ηt (s, a)πt (a | s)2 Q a

t=1

# i h m 1 1 b +E 2 + 2E QP t ,πt (s, ·; mT +1 ) −π(· | s) + 1, Qt (s, ·) − Bt (s, ·) T t=1 A ∞ " T # XX 1 1 log(T ) ≤ O HS 2 A log(T ) + 3E − ηt+1 (s, a) ηt (s, a) t=1 a T X

(by QP t ,πt (s, ·; mT +1 ) ∞ ≤ H) + 3E

" T XX t=1

| + 3E

2 # It (s, a)(Lt,h(s) − Mt,h(s) ) It (s)(Lt,h(s) − Mt,h(s) ) Yt − Yt qt (s)πt (a | s) qt (s) {z } stability-term

" T XX t=1

ηt (s, a)πt (a | s)

# ηt (s, a)πt (a | s)2 (Ct (s, a)Yt )

+ 3E

" T XX t=1

# ηt (s, a)πt (a | s)2 Bt (s, a)2 .

(69) Here, the second inequality follows from " # T 1 b 1 X E 2 −π(· | s) + 1, Qt (s, ·) − Bt (s, ·) T t=1 A * " T #+ i X h 1 1 b t (s, ·) − Bt (s, ·) = 2 −π(· | s) + 1, E Et Q T A t=1 " T # i X h 1 1 b E Et Qt (s, ·) − Bt (s, ·) ≤ 2 −π(· | s) + 1 T A 1 t=1 ∞ √ 3 √ 2T (6HS + 7 HS AT ) 12HS ≤ = + 14 HS 3 A ≤ O HS 2 A log(T ) , 2 T T √ 1 b t (s, a)] ≤ 6HS and Bt (s, a) ≤ 7 HS 3 A from where we used −π(· | s) + A 1 1 ≤ 2, Et [Q γt hP h ii T b Lemmas G.1 and G.2, which together imply E ≤ T (6HS + t=1 Et Qt (s, ·) − Bt (s, ·) ∞ √ 3 7 HS AT ). We further evaluate the stability-term in the last inequality as 2 It (s)(Lt,h(s) − Mt,h(s) ) 2 It (s, a)(Lt,h(s) − Mt,h(s) ) ηt (s, a)πt (a | s) Yt − Yt qt (s)πt (a | s) qt (s) 2 It (s, a)(Lt,h(s) − Mt,h(s) ) πt (a | s)It (s)(Lt,h(s) − Mt,h(s) ) = ηt (s, a) − Yt qt (s) qt (s) ηt (s, a) = (It (s, a) − πt (a | s)It (s))2 (Lt,h(s) − Mt,h(s) )2 Yt qt (s)2 ηt (s, a)ζt (s, a) = Yt , qt (s)2 54

where the last equality follows from the definition of ζt (s, a) = (It (s, a)−πt (a | s)It (s))2 (Lt,h(s) − Mt,h(s) )2 . Thus, we have stability-term =

T X X ηt (s, a)(ζt (s, a)) t=1

≤

qt (s)2

T X X t=1

1 1 − ηt+1 (s, a) ηt (s, a)

log(T ),

where the last inequality follows from (14). Then, together with (69) and Lemma G.2, we obtain " T X X π 2 E[reg (s)] ≤ O HS A log(T ) + 6E t=1

+ 3E

" T XX t=1

+ 3E

log(T )

ηt (s, a)πt (a | s)2 Ct (s, a)2 Yt

" T XX t=1

1 1 − ηt+1 (s, a) ηt (s, a) #

# 2

ηt (s, a)πt (a | s) Bt (s, a)

" T X

# T X X 1 = O HS 2 A log(T ) + E bt (s) + E πt (a | s)Bt (s, a) . H t=1 a t=1

Lemma G.8 (bandit setting). For any comparator policy π, the following two bounds hold: " # X π π E q (s)bias (s) s

v # " u XX u e,πt P 2 2 2 2 π t t (s, a; (ℓt − mt ) ) + H 2 S 3 Aι2 q (s, a) max Q ≲ H S Aι E e∈Pt P

t∈Tr s,a

and " E

# X

q (s)bias (s)

v " # u XX u ≲ tH 3 S 2 Aι2 E [q πt (s, a) − q π (s, a)]+ t∈Tr s,a

v  u H−1 Xu X u 2 2 tH S |Sh ||Sh+1 |Aι2 E +

 X

[q πt (s, a) − q π (s, a)]+  + H 2 S 3 Aι2 .

t∈Tr (s,a)∈Sh ×A

h=0

Proof. By the definition of ct (s, a) (12), Et [ct (s, a)] = ρt (s)

q πt (s) πt Q (s, a; |ℓt − mt |) + ρt (s)2 H. qt (s)

b t , we have Thus, by the definition of Q i h b t (s, a) + QP m t ,πt (s, a; m ) − Qπt (s, a; m ) Et Qπt (s, a; ℓt ) − Q t t q πt (s) πt πt Pm ,πt t (s, a; mt ) + Q (s, a; ℓt − mt )Yt − Et [Ct (s, a)]Yt = Q (s, a; ℓt ) − Q qt (s) m

+ QP t ,πt (s, a; mt ) − Qπt (s, a; mt ) qt (s) − q πt (s)Yt πt Q (s, a; ℓt − mt ) + Et [Ct (s, a)]Yt = qt (s)  πt if Yt = 0,  −Q (s, a; mt ) = q (s) − q πt (s)   t Qπt (s, a; ℓt − mt ) + Et [Ct (s, a)] if Yt = 1. qt (s) When Yt = 1, by (71) and Ct (s, a) ≥ ct (s, a) pathwise, qt (s) − q πt (s) πt Q (s, a; ℓt − mt ) + Et [Ct (s, a)] qt (s) qt (s) − q πt (s) πt ≥− |Q (s, a; ℓt − mt )| + Et [ct (s, a)] ≥ 0. qt (s) When Yt = 0, using Qπt (s, a; mt ) ≤ H and the fact that the virtual episode has zero loss, we obtain i h b t (s, a) + QP m t ,πt (s, a; m ) − Qπt (s, a; m ) ≤ 0. −H ≤ Et Qπt (s, a; ℓt ) − Q t t Therefore, " # X E q π (s)biasπ (s) s

# " T i h XX m ,π π π πt P b t (s, a) + Q t t (s, a; mt ) − Q t (s, a; mt ) =E q (s)(πt (a | s) − π(a | s))Et Q (s, a; ℓt ) − Q t=1 s,a

# qt (s) − q πt (s) πt ≤E q (s)(πt (a | s) − π(a | s)) Q (s, a; ℓt − mt ) + Et [Ct (s, a)] qt (s) t∈Tr s,a " # XX π +E q (s)π(a | s)H XX

t∈Tv s,a

" =E

# XX

πt

(q (s, a) − q (s, a))zt (s, a) + H|Tv |.

t∈Tr s,a

The additive term H|Tv | ≲ H 3 SA log2 (T ) by Lemma G.4 is lower order and will be absorbed into the final lower-order term. The last equality follows by applying Lemma D.2, for each real episode t ∈ Tr , with L(s, a) =

qt (s) − q πt (s) πt Q (s, a; ℓt − mt ) + Et [Ct (s, a)]. qt (s)

Thus, zt (s, a) =

qt (s) − q πt (s) πt Q (s, a; ℓt − mt ) + Et [Ct (s, a)] qt (s) qt (s′ ) − q πt (s′ ) πt ′ ′ ′ ′ − Es′ ∼P (·|s,a),a′ ∼πt (·|s′ ) Q (s , a ; ℓt − mt ) + Et [Ct (s , a )] . qt (s′ ) (72)

We first reduce the bound to the high-probability event E. By Et [Ct (s, a)] ≤ O(HS) from Lemma G.1, Et [zt (s, a)] ≤ O(HS) holds. Therefore, we have " # XX E (q πt (s, a) − q π (s, a))zt (s, a) t∈Tr s,a

" ≤E

# XX

πt

(q (s, a) − q (s, a))zt (s, a) E + Pr Ē E

t∈Tr s,a

πt

(q (s, a) − q (s, a))zt (s, a) Ē

t∈Tr s,a

" ≤E

# XX

πt

(q (s, a) − q (s, a))zt (s, a) E + O(δ) × O(HT ) × O(HS)

t∈Tr s,a

" ≤E

(q (s, a) − q (s, a))zt (s, a) E + O

t∈Tr s,a

H 2S . T

(73)

In the following, we work on the event E and bound the first term on the right-hand side of (73). On E, since P ∈ Pt , we can upper bound Et [ct (s, a)] as Et [ct (s, a)] ≤ ρt (s)Qπt (s, a; |ℓt − mt |) + ρt (s)2 H ≤ ρt (s) max QP ,πt (s, a; |ℓt − mt |) + ρt (s)2 H e

e∈Pt P

≤

q πt t (s) − q πt t (s) qt (s)

max QP ,πt (s, a; |ℓt − mt |) + e

e∈Pt P

γt H + ρt (s)2 H. qt (s)

(74)

We next derive lower and upper bounds on zt (s, a). Since P ∈ Pt on E, the definition of Ct (s, a) (13) implies Et [Ct (s, a)] ≥ Et [ct (s, a)] + Es′ ∼P (·|s,a),a′ ∼πt (·|s′ ) [Et [ct (s′ , a′ ) + Ct (s′ , a′ )]].

(75)

Combining (71), (72) and (75), we have for any real episode t ∈ Tr qt (s) − q πt (s) πt Q (s, a; ℓt − mt ) + Et [ct (s, a)] qt (s) qt (s′ ) − q πt (s′ ) πt ′ ′ Q (s , a ; ℓ − m ) + Es′ ∼P (·|s,a),a′ ∼πt (·|s′ ) Et [ct (s′ , a′ )] − t t qt (s′ ) ≥ 0. (76)

zt (s, a) ≥

On the other hand, let P t be the measurable transition kernel that attains the maximum in (13) for the realized table ct . Then, for any real episode t ∈ Tr qt (s) − q πt (s) πt Q (s, a; ℓt − mt ) + Et [ct (s, a)] qt (s) h i + Et Es′ ∼P C (·|s,a),a′ ∼πt (·|s′ ) [ct (s′ , a′ ) + Ct (s′ , a′ )] t qt (s′ ) − q πt (s′ ) πt ′ ′ ′ ′ − Es′ ∼P (·|s,a),a′ ∼πt (·|s′ ) Q (s , a ; ℓt − mt ) + Et [Ct (s , a )] qt (s′ ) h i ≤ 2Et [ct (s, a)] + Et Es′ ∼P C (·|s,a),a′ ∼πt (·|s′ ) [ct (s′ , a′ ) + Ct (s′ , a′ )]

zt (s, a) =

−E

s′ ∼P (·|s,a),a′ ∼πt (·|s′ )

[−Et [ct (s′ , a′ )] + Ct (s′ , a′ )]

(by (70))

(77)

By the definition of Ct (s, a) (13), we have X X C q P t ,πt (s′ , a′ | s)ct (s′ , a′ ). πt (a | s)(ct (s, a) + Ct (s, a)) = 2

(78)

s′ ,a′

s′′ ,a′′

Therefore, by (76) and (79), XX (q πt (s, a) − q π (s, a))zt (s, a) t∈Tr s,a

≤

[q πt (s, a) − q π (s, a)]+ zt (s, a)

(by (76))

t∈Tr s,a

≤2

XX [q πt (s, a) − q π (s, a)]+ Et [ct (s, a)] t∈Tr s,a

}

term1

[q πt (s, a) − q π (s, a)]+ Es′ ∼P (·|s,a),a′ ∼πt (·|s′ ) [Et [ct (s′ , a′ )]]

t∈Tr s,a

{z }   XX X X C C +2 [q πt (s, a) − q π (s, a)]+ Et  P t (s′ | s, a) − P (s′ | s, a) q P t ,πt (s′′ , a′′ | s′ )ct (s′′ , a′′ ) . term2

s′′ ,a′′

s′

t∈Tr s,a

}

term3

Let G

πt

) ( 2 X X e,πt P πt π πt := min (s, a; |ℓt − mt |) , H [q (s, a) − q (s, a)]+ . q (s, a) max Q e∈Pt P

s,a

(80) We first bound term1 . By (74), XX term1 = [q πt (s, a) − q π (s, a)]+ Et [ct (s, a)] t∈Tr s,a

≤

X X t∈Tr s,a

[q πt (s, a) − q π (s, a)] e + q πt t (s) − q πt t (s) max QP ,πt (s, a; |ℓt − mt |) e∈Pt qt (s) P {z } term1a

X X γt +H [q πt (s, a) − q π (s, a)]+ q (s) t t∈Tr s,a | {z } term1b

πt

[q (s, a) − q π (s, a)]+ ρt (s)2 .

t∈Tr s,a

}

term1c

We first control term1a . Define X [q πt (s, a) − q π (s, a)]+ e (1) gt (s) := max QP ,πt (s, a; |ℓt − mt |) ≤ H. e q (s) t P ∈Pt a 58

Thus, by Lemma D.7, term1a =

X X t∈Tr

(1) q πt t (s) − q πt t (s) gt (s)

s ≲

HS 2 Aι2

XX t∈Tr

2 (1) q πt (s) gt (s) + H 2 S 3 Aι2 .

Here, by the Cauchy–Schwarz inequality, 2 X (1) q πt (s) gt (s) s

≤

X [q πt (s, a) − q π (s, a)]+

πt

q (s)

X [q πt (s, a) − q π (s, a)]+

qt (s) qt (s) a 2 X e ≤ [q πt (s, a) − q π (s, a)]+ max QP ,πt (s, a; |ℓt − mt |) s

max Q

2 ! (s, a; |ℓt − mt |)

e∈Pt P

s,a

≤H

e,πt P

X e [q πt (s, a) − q π (s, a)]+ max QP ,πt (s, a; (ℓt − mt )2 )

(by (54))

e∈Pt P

s,a πt

≤ HG , Therefore, s H 2 S 2 Aι2

term1a ≲

Gπt + H 2 S 3 Aι2 .

(81)

t∈Tr

Next, term1b can be bounded by XX

term1b ≤ H

t∈Tr

γt

X q πt (s) ≤ HS γt ≲ HS log(T ). qt (s)

(82)

t∈Tr

Finally, term1c can be bounded by using Lemma G.5, XX term1c ≤ H q πt (s)ρt (s)2 ≲ H 2 S 3 Aι2 . t∈Tr

(83)

Combining (81)–(83), we obtain s term1 ≲

H 2 S 2 Aι2

Gπt + H 2 S 3 Aι2 .

(84)

t∈Tr

We next bound term2 . By (74), we have XX term2 = [q πt (s, a) − q π (s, a)]+ Es′ ∼P (·|s,a),a′ ∼πt (·|s′ ) [Et [ct (s′ , a′ )]] t∈Tr s,a

≤

πt

[q (s, a) − q (s, a)]+ Es′ ∼P (·|s,a),a′ ∼πt (·|s′ )

" π q t t (s′ ) − q πt t (s′ ) qt (s′ )

t∈Tr s,a

[q πt (s, a) − q π (s, a)]+ Es′ ∼P (·|s,a)

t∈Tr s,a

| +H

}

term2b

γt qt (s′ )

[q πt (s, a) − q π (s, a)]+ Es′ ∼P (·|s,a) ρt (s′ )2 .

t∈Tr s,a

}

term2c

max Q

′

(s , a ; |ℓt − mt |)

e∈Pt P

}

term2a

# e,πt P

a′

Therefore, by Lemma D.7, X X

term2a =

(2) q πt t (s′ ) − q πt t (s′ ) gt (s′ )

t∈Tr s′

s HS 2 Aι2

≲

2 (2) q πt (s′ ) gt (s′ ) + H 2 S 3 Aι2 .

t∈Tr s′

Moreover, by using the Cauchy–Schwarz inequality, we obtain 2 X (2) q πt (s′ ) gt (s′ ) s′

!2 ≤

πt

′

q (s )

e,πt P

πt (a | s ) max Q

′

(s , a ; |ℓt − mt |)

e∈Pt P

2 e,πt ′ ′ P (s , a ; |ℓt − mt |) q (s , a ) max Q πt

′

e∈Pt P

s′ ,a′

≤H

′

a′

s′

≤

′

q πt (s′ , a′ ) max QP ,πt (s′ , a′ ; (ℓt − mt )2 ),

(85)

e∈Pt P

s′ ,a′

where the last inequality follows from (54). Simultaneously, it holds that 2 X (2) q πt (s′ ) gt (s′ ) s′

≤H

q πt (s′ )

P (s′ | s, a)πt (a′ | s′ )

s,a,a′

s′

[q πt (s, a) − q π (s, a)]+ e max QP ,πt (s′ , a′ ; |ℓt − mt |) e∈Pt qt (s′ ) P

[q (s, a) − q π (s, a)]+ P (s′ | s, a)πt (a′ | s′ ) πt

s,a,s′ ,a′

[q πt (s, a) − q π (s, a)]+ .

(86)

s,a

From (85) and (86), we have X

2 (2) q πt (s′ ) gt (s′ ) ≤ HGπt .

s′

Hence, s term2a ≲

H 2 S 2 Aι2

Gπt + H 2 S 3 Aι2 .

(87)

t∈Tr

Next, term2b can be bounded by P πt π ′ XX X s,a [q (s, a) − q (s, a)]+ P (s | s, a) term2b ≤ H γt ≤ HS γt ≲ HS log(T ). qt (s′ ) ′ t∈Tr s

t∈Tr

(88)

Finally, by the Lemma G.5, term2c ≤ H

[q πt (s, a) − q π (s, a)]+ P (s′ | s, a)ρt (s′ )2

t∈Tr s,a

≤

q πt (s′ )ρt (s′ )2 ≲ H 2 S 3 Aι2 .

(89)

s′

Combining (87)–(89), we obtain s H 2 S 2 Aι2

term2 ≲

Gπt + H 2 S 3 Aι2 .

(90)

t∈Tr

We finally bound term3 . Here, for any transition Pet ∈ Pt , we use X X e P (s′ | s, a)q Pt ,πt (s′′ , a′′ | s′ ) ≤ Hq πt t (s′′ )πt (a′′ | s′′ ). [q πt (s, a) − q π (s, a)]+

(91)

s′

s,a

By the definition of the confidence set, we have term3   s ! ′ | s, a)ι XX X X C P (s ι ≲ [q πt (s, a) − q π (s, a)]+ Et  + q P t ,πt (s′′ , a′′ | s′ )ct (s′′ , a′′ ) n (s, a) n (s, a) t t ′′ ′′ ′ s,a s

t∈Tr

s ,a

(by Lemma C.2) ≲

X X

[q πt (s, a) − q π (s, a)]+ αPt (s′ | s, a) +

t∈Tr s,a,s′

ι αnt (s, a)

[q πt (s, a) − q π (s, a)]+

X s′

t∈Tr s,a

i (s′′ , a′′ | s′ )ct (s′′ , a′′ )

(for any α ∈ (0, 1])  X

q P t ,πt (s′′ , a′′ | s′ )ct (s′′ , a′′ )

s′′ ,a′′

| +

P (s′ | s, a)Et 

Et q

C P t ,πt

s′′ ,a′′

 ≲α

}   X X C Et  q P t ,πt (s′′ , a′′ | s′ )ct (s′′ , a′′ ) .

term3a

1 X X πt ι [q (s, a) − q π (s, a)]+ α n (s, a) t t∈Tr s,a | {z

s′ s′′ ,a′′

}

term3b

C For term3a , using (91) with Pet = P t , XX term3a ≤ H q πt t (s)πt (a | s)Et [ct (s, a)] t∈Tr s,a

≤H

X X

e q πt t (s) − q πt t (s) πt (a | s) max QP ,πt (s, a; |ℓt − mt |) e∈Pt P

t∈Tr s,a

| + H2

}

term3a,1

XX t∈Tr

γt +H 2

term3a,2

XX t∈Tr

}

q πt t (s)ρt (s)2 .

term3a,3

}

(by (74))

By Lemma D.7 and the Cauchy–Schwarz inequality, v !2 u u X XX e t π (a | s) max QP ,πt (s, a; |ℓ − m |) + H 2 S 3 Aι2 term ≲ HS 2 Aι2 q πt (s) t

3a,1

t∈Tr

e∈Pt P

v u 2 XX u ≤ tHS 2 Aι2 q πt (s, a) max QPe,πt (s, a; |ℓt − mt |) + H 2 S 3 Aι2 e∈Pt P

t∈Tr s,a

s H 2 S 2 Aι2

≤

q πt (s, a) max QPe,πt (s, a; (ℓt − mt )2 ) + H 2 S 3 Aι2 . (by (54)) e∈Pt P

t∈Tr s,a

Furthermore, by the definition of γt and Lemma G.6, term3a,2 ≲ S log(T ), term3a,3 ≲ HS 3 Aι2 . Therefore, term3a ≲

s XX H 4 S 2 Aι2 q πt (s, a) max QPe,πt (s, a; (ℓt − mt )2 ) + H 3 S 3 Aι2 .

(92)

e∈Pt P

t∈Tr s,a C

For term3b , since q P t ,πt (s′′ , a′′ | s′ ) ≤ πt (a′′ | s′′ ), [q πt (s, a) − q π (s, a)]+ ≤ q πt (s, a), we have term3b ≤

H−1 X X

h=0 t∈Tr (s,a)∈Sh ×A

≲ HS

H−1 X

|Sh+1 |

H−1 X

πt (a′′ | s′′ )Et [ct (s′′ , a′′ )]

s ∈Sh+1 s′′ ,a′′

q πt (s, a)ι nt (s, a)

t∈Tr (s,a)∈Sh ×A

h=0

≲ HS

q πt (s, a)ι X nt (s, a) ′

(by Et [ct (s′′ , a′′ )] ≤ 2H)

|Sh+1 ||Sh |Aι2

(by Lemma C.3)

h=0 3 2

≲ HS Aι .

(93)

Combining (92) and (93), we obtain, for any α ∈ (0, 1], s XX q πt (s, a) max QPe,πt (s, a; (ℓt − mt )2 ) term3 ≲ α H 4 S 2 Aι2 e∈Pt P

t∈Tr s,a

+ αH 3 S 3 Aι2 +

HS 3 Aι2 . α

Choosing α = 1/H gives s XX term3 ≲ H 2 S 2 Aι2 q πt (s, a) max QPe,πt (s, a; (ℓt − mt )2 ) + H 2 S 3 Aι2 .

(94)

e∈Pt P

t∈Tr s,a

We also derive a bound in terms of the positive occupancy difference. Recall that term3 can be upper-bounded by   s ! ′ X XX X C P (s | s, a)ι ι + q P t ,πt (s′′ , a′′ | s′ )ct (s′′ , a′′ ). [q πt (s, a) − q π (s, a)]+ Et  n (s, a) n (s, a) t t ′′ ′′ ′ s,a s ,a

t∈Tr

C P t ,πt

Since q (s′′ , a′′ | s′ ) ≤ πt (a′′ | s′′ ), s′′ )Et [ct (s′′ , a′′ )] ≲ HS, we have term3 ≲ HS

H−1 X X

s′ ∈Sh+1

p P P (s′ | s, a) ≤ |Sh+1 |, and s′′ ,a′′ πt (a′′ | s

πt

[q (s, a) − q (s, a)]+

h=0 t∈Tr (s,a)∈Sh ×A

term3c

|Sh+1 |ι nt (s, a) }

+ HS

H−1 X X

[q πt (s, a) − q π (s, a)]+

h=0 t∈Tr (s,a)∈Sh ×A

term3d

|Sh+1 |ι . nt (s, a) }

For term3c , by the Cauchy–Schwarz inequality and Lemma C.3, v H−1 u X X sX X u term3c ≤ [q πt (s, a) − q π (s, a)]+ t|Sh+1 |

t∈Tr (s,a)∈Sh ×A

h=0

H−1 Xs X ≲ |Sh ||Sh+1 |Aι2

q πt (s, a)ι nt (s, a)

[q πt (s, a) − q π (s, a)]+ .

t∈Tr (s,a)∈Sh ×A

h=0

For term3d , by Lemma C.3, term3d ≤

≲

H−1 X

h=0

t∈Tr (s,a)∈Sh ×A

|Sh+1 |

H−1 X

q πt (s, a)ι nt (s, a)

|Sh+1 ||Sh |Aι2 ≲ S 2 Aι2 .

h=0

Therefore, term3 ≲

H−1 Xs

H 2 S 2 |Sh ||Sh+1 |Aι2

[q πt (s, a) − q π (s, a)]+ + HS 3 Aι2 .

(95)

t∈Tr (s,a)∈Sh ×A

h=0

The desired bound follows by combining (73), the definition of Gπt in (80), and the bounds in (84), (90), (94) and (95), and then applying Jensen’s inequality. Lemma G.9 (bandit setting). For any comparator policy π, it holds that " # X p 1:T (m)] + HS 3 Aι2 . E q π (s)errorπ (s) ≲ S 2 Aι2 E[Qπtrans

(96)

Also, " E

# X

q (s)error (s)

≲

v  u X u 2 tH |Sh ||Sh+1 |Aι2 E

H−1 Xu

 X

[q πt (s, a) − q π (s, a)]+  + H 2 S 2 Aι2 .

(97)

t∈Tr (s,a)∈Sh ×A

h=0

Proof. The proof is identical to that of Lemma F.6, with the loss sequence ℓt replaced by the prediction sequence mt . The only additional point is that we first separate the contribution of virtual episodes. X

q π (s)errorπ (s)

≤

≲

q π (s)

t=1 π

q (s)

T X X a

XX t∈Tr

q π (s)

m (πt (a | s) − π(a | s)) Qπt (s, a; mt ) − QP t ,πt (s, a; mt )

XX t∈Tr

m (πt (a | s) − π(a | s)) Qπt (s, a; mt ) − QP t ,πt (s, a; mt ) + 2H 2 |Tv | m (πt (a | s) − π(a | s)) Qπt (s, a; mt ) − QP t ,πt (s, a; mt ) + H 3 SA log2 (T ),

where we used Lemma G.4. The resulting virtual-episode contribution is absorbed into the lowerorder term. It remains to bound the first term in expectation, which follows from Lemma F.6. Applying the first bound of Lemma F.6 with ℓt replaced by mt gives, on E, X p 1:T q π (s)errorπ (s) ≲ S 2 Aι2 Qπtrans (m) + HS 3 Aι2 . s

Taking expectations, using Jensen’s inequality, and combining with the trivial bound O(H 2 T ) on Ē with δ = O(1/T 2 ), we obtain " # X p π π 1:T E q (s)error (s) ≲ S 2 Aι2 E[Qπtrans (m)] + HS 3 Aι2 + δH 2 T s

≲

1:T S 2 Aι2 E[Qπtrans (m)] + HS 3 Aι2 ,

which proves (96). Similarly, applying the second bound of Lemma F.6 with ℓt replaced by mt gives, on E, H−1 X Xs X X q π (s)errorπ (s) ≲ H 2 |Sh ||Sh+1 |Aι2 [q πt (s, a) − q π (s, a)]+ s

t∈Tr (s,a)∈Sh ×A

h=0 2

+ H S Aι . Taking expectations, applying Jensen’s inequality, and combining with the trivial bound O(H 2 T ) on Ē with δ = O(1/T 2 ), we obtain " # X π π E q (s)error (s) s

≲

v  u X u 2 tH |Sh ||Sh+1 |Aι2 E

H−1 Xu

 X

[q πt (s, a) − q π (s, a)]+  + H 2 S 2 Aι2 + δH 2 T

t∈Tr (s,a)∈Sh ×A

h=0

v  u H−1 Xu X u 2 tH |Sh ||Sh+1 |Aι2 E ≲

 X

[q πt (s, a) − q π (s, a)]+  + H 2 S 2 Aι2 .

t∈Tr (s,a)∈Sh ×A

h=0

This proves (97). Lemma G.10 (bandit setting). It holds that # " XX B 3 7 3 P t ,πt 2 2 E q (s)ηt (s, a)πt (a | s) Ct (s, a) ≲ H 2 S 2 A 2 ι2 . t∈Tr s,a

Proof. By the decomposition of qt (s)πt (a | s)Ct (s, a) in (62), we have qt (s)πt (a | s)Ct (s, a) X X ≤2 ρt (s′ )It (s′ , a′ )Dt,h(s′ ) + 2H qt (s′ )πt (a′ | s′ )ρt (s′ )2 . s′ ,a′

s′ ,a′

Thus, we obtain  2  " # X X   Et qt (s)2 πt (a | s)2 Ct (s, a)2 ≲ SAEt  ρt (s′ )It (s′ , a′ )Dt,h(s′ )   s′ ,a′

s,a

2

 + H 2 SA

X s′ ,a′

qt (s′ )πt (a′ | s′ )ρt (s′ )2  .

(98)

For the first term of (98), the Cauchy–Schwarz inequality gives    2  X X   2  ρt (s′ )2 It (s′ , a′ )Dt,h(s ρt (s′ )It (s′ , a′ )Dt,h(s′ )   ≤ HEt  Et  ′) s′ ,a′

s′ ,a′



 ≤ H 3 Et 

ρt (s′ )2 It (s′ , a′ )

s′ ,a′

= H3

q πt (s′ )ρt (s′ )2

s′

≤H

qt (s′ )πt (a′ | s′ )ρt (s′ )2 .

s′ ,a′

For the second term of (98), since X

qt (s′ )πt (a′ | s′ )ρt (s′ )2 ≤ S,

s′ ,a′

we have 2

 X

qt (s′ )πt (a′ | s′ )ρt (s′ )2  ≤ S



qt (s′ )πt (a′ | s′ )ρt (s′ )2 .

s′ ,a′

Hence, " E





# XX

qt (s)2 πt (a | s)2 Ct (s, a)2 ≲ H 2 S 2 AE

t∈Tr s,a

t∈Tr

qt (s′ )πt (a′ | s′ )ρt (s′ )2 

s′ ,a′

" 2

= H S AE

′

′ 2

qt (s )ρt (s )

(99)

t∈Tr s′

Combining Lemma G.6 with the trivial bound " # XX ′ ′ 2 E qt (s )ρt (s ) ≲ HS 3 Aι2 + δ · O(HT ) ≲ HS 3 Aι2 , t∈Tr s′

and (99), we get " E

# XX

≲ H 2 S 2 A · HS 3 Aι2

qt (s) πt (a | s) Ct (s, a)

t∈Tr s,a

≲ H 3 S 5 A2 ι 2 . Therefore, " E

(100)

P t ,πt

(s)ηt (s, a)πt (a | s) Ct (s, a)

t∈Tr s,a

ηt (s, a)qt (s)2 πt (a | s)2 Ct (s, a)2 =E q (s) qt (s)2 t∈Tr s,a # " XX ηt (s, a) 2 2 2 ≤E qt (s) πt (a | s) Ct (s, a) max s,a qt (s) t∈Tr s,a " # XX 1 ≤E qt (s)2 πt (a | s)2 Ct (s, a)2 · √ 50 H 3 S 3 A t∈Tr s,a XX

≲ H 3 S 5 A2 ι 2 · √ 3

P t ,πt

1 H 3S3A

(by t is a real episode) (by (100))

= H 2 S 2 A 2 ι2 .

Lemma G.11 (bandit setting). It holds that v " " T # # u Xu X X B 7 3 3 P t ,πt t V ζt (s, a) + H 2 S 2 A 2 ι2 . E (s0 ; bt ) ≲ log(T ) E s,a

t=1

t∈Tr

Proof. We have " T # X B E V P t ,πt (s0 ; bt ) t=1

" T # XX B P t ,πt =E q (s)bt (s) t=1

# 1 1 − log(T ) ≲E q ηt+1 (s, a) ηt (s, a) t∈Tr s,a " # XX B 1 1 +E q P t ,πt (s) − log(T ) ηt+1 (s, a) ηt (s, a) t∈Tv s,a " # XX B +E q P t ,πt (s)ηt (s, a)πt (a | s)2 Ct (s, a)2 B

P t ,πt

(s)

t∈Tr s,a

" XX

≲E

P t ,πt

t∈Tr s,a

# " # XX B 3 7 3 ηt (s, a)ζt (s, a) 1{(s†t , a†t ) = (s, a)} P t ,πt (s) +E q (s) + H 2 S 2 A 2 ι2 qt (s)2 η (s, a)H t s,a t∈Tv

(by Lemma G.10) " ≤E

X X ηt (s, a)ζt (s, a)

≲E

X X ηt (s, a)ζt (s, a) qt (s)

t∈Tr s,a

" +E

qt (s)

t∈Tr s,a

# +

B P t ,πt

X q (s†t ) † † t∈Tv ηt (st , at )H

X√

# 3

≲

HS 3 A + H 2 S 2 A 2 ι2

t∈Tv

(by √



+ H 2 S 2 A 2 ι2

ηt (s†t ,a†t ) > 50√H13 S 3 A in virtual episodes) qt (s)



p ζt (s,a) × ζt (s, a)  qt (s)

X X qP log(T )E

ζτ (s,a) τ ≤t:τ ∈Tr qτ (s)2

t∈Tr s,a

+

√

HS 3 A|Tv | + H 2 S 2 A 2 ι2 (by Lemma G.3)

v  u X uX p t ≲ log(T )E P s,a

t∈Tr



ζt (s,a) sX 3 7 3 qt (s)2 ζt (s, a) + H 2 S 2 A 2 ι2 ζτ (s,a) t∈Tr τ ≤t:τ ∈Tr qτ (s)2

(by the Cauchy–Schwarz inequality and Lemma G.4)   X sX 3 7 3 ≲ log(T )E ζt (s, a) + H 2 S 2 A 2 ι2 , s,a

t∈Tr

where the last inequality follows from v v u u ζt (s,a) uX u 2 q (s) t t t1 + log ≤ P ζτ (s,a) t∈Tr

τ ≤t:τ ∈Tr qτ (s)2

X ζτ (s, a) τ ∈Tr

Finally, the desired bound follows from Jensen’s inequality.

qτ (s)2

! ≲

log(T ).

We now summarize the bounds in the bandit setting proved above and plug them into the regret decomposition. By the definition of the regret decomposition in (59), " # X X E q π (s) (πt (a | s) − π(a | s))(Qπt (s, a; ℓt ) − Bt (s, a)) s

t,a

" =E

# X

q (s) · reg (s) + E

# X

q (s) · bias (s) + E

" X

q (s) · error (s)

# T 1 XX π ≤ O H S A log(T ) + E q (s)bt (s) + E q (s)πt (a | s)Bt (s, a) H t=1 a t=1 " # " # X X π +E q π (s) · bias (s) + E q π (s) · errorπ (s) 2

" T X

# π

where we used Lemma G.7. Combining this with Lemma F.1 and δ = T12 , for any comparator policy π, Algorithm 1 guarantees # " T X B V P t ,πt (s0 ; bt ) RegT (π) ≤ O H 2 S 2 A log(T ) + 3E t=1

# X

q (s) · bias (s) + E

q (s) · error (s)

v " # u X u X 3 7 3 2 tE ≲ H 2 S 2 A 2 ι + log(T ) ζt (s, a) s,a

" +E

t∈Tr

# X

q π (s) · biasπ (s) + E

# X

q π (s) · errorπ (s) ,

where the second line follows from Lemma G.11. G.3

Proof for the adversarial regime

Theorem G.12 (bandit setting). For any comparator policy π, Algorithm 1 guarantees q RegT (π) ≲ H 3 S 2 A log2 (T ) min{L(π), HT − L(π), Q∞ , V1 } q 3 7 3 1:T + S 2 A log2 (T )E[Qπtrans (ℓ)] + H 2 S 2 A 2 log2 (T ). Proof. By (101) and Lemmas G.8 and G.9, for any comparator policy π, we have v " # u Xu X 7 3 3 2 t Reg (π) ≲ H 2 S 2 A 2 ι + log(T ) E ζt (s, a) T

s,a

t∈Tr

v " # u XX u 2 e 2 2 2 π P ,π t + H S A log (T )E q t (s, a) max Q t (s, a; (ℓt − mt ) ) t∈Tr s,a

1:T S 2 Aι2 E[Qπtrans (m)].

e∈Pt P

(101)

Here, since δ = O(1/T 2 ), we have ι ≲ log(T ). Hence, v " # u Xu X 2 t RegT (π) ≲ H S A log (T ) + log(T ) E ζt (s, a) 3 2

7 2

3 2

s,a

t∈Tr

term1

}

v # " u X u 2 2 π 3 2 t t + H S A log (T )E V (s0 ; (ℓt − mt ) ) t∈Tr

| +

}

term2

1:T S 2 A log2 (T )E[Qπtrans (m)], | {z }

(102)

term3

where the last inequality uses Lemma D.9 on E together with the trivial bound O(H 2 T ) on Ē, whose contribution is absorbed since δ = O(1/T 2 ). For term1 , by the definition of ζt (s, a), we have v " # u Xu X tlog2 (T )E term1 = (It (s, a) − πt (a | s)It (s))2 (Lt,h(s) − Mt,h(s) )2 s,a

t∈Tr

v " # u XX u (It (s, a) − πt (a | s)It (s))2 (Lt,h(s) − Mt,h(s) )2 ≤ tSA log2 (T )E t∈Tr s,a

(by the Cauchy–Schwarz inequality) v " # u XX u ≤ tSA log2 (T )E 2It (s, a)(Lt,h(s) − Mt,h(s) )2 t∈Tr s,a

v " # u XX u 2 2 2 t It (s, a)(ℓt (s, a) − mt (s, a)) , ≲ H SA log (T )E

(103)

t∈Tr s,a

P where the third line uses a (It (s, a) − πt (a | s)It (s))2 ≤ 2It (s) for each fixed state s, and the last inequality follows from Lemma D.10. Applying Lemma D.11 to (103), we obtain, for any policy π, q term1 ≲ H 2 SA log2 (T ) min{L(π) + RegT (π), HT − L(π) − RegT (π), Q∞ , V1 } + HSA log(T ).

(104)

For term2 , Lemma D.11 similarly yields, for any policy π, q term2 ≲ H 3 S 2 A log2 (T ) min{L(π) + RegT (π), HT − L(π) − RegT (π), Q∞ , V1 } √ + H 3 S 3 A log(T ). (105) For term3 , Lemma D.12 yields v " # u q X u 2 2 2 π 1:T term3 ≲ S 2 A log (T )E[Qtrans (ℓ)] + tHS 2 A log (T )E V πt (s0 ; (ℓt − mt ) ) . t∈Tr

Applying Lemma D.11 to the second term, we obtain, for any policy π, q 1:T term3 ≲ S 2 A log2 (T )E[Qπtrans (ℓ)] q + HS 2 A log2 (T ) min{L(π) + RegT (π), HT − L(π) − RegT (π), Q∞ , V1 } √ + HS 3 A log(T ). (106) 68

Combining (104)–(106) with (102), we obtain q RegT (π) ≲ H 3 S 2 A log2 (T ) min{L(π) + RegT (π), HT − L(π) − RegT (π), Q∞ , V1 } q 7 3 3 1:T (107) + S 2 A log2 (T )E[Qπtrans (ℓ)] + H 2 S 2 A 2 log2 (T ). Below, we derive the first-order bound. By (107), there exists an absolute constant c > 0 such that q q RegT (π) ≤ c H 3 S 2 A log2 (T )L(π) + c H 3 S 2 A log2 (T )RegT (π) q 3 7 3 1:T + c S 2 A log2 (T )E[Qπtrans (ℓ)] + cH 2 S 2 A 2 log2 (T ) q c2 1 ≤ c H 3 S 2 A log2 (T )L(π) + H 3 S 2 A log2 (T ) + RegT (π) 2 2 q 7 3 3 2 π1:T 2 2 2 2 + c S A log (T )E[Qtrans (ℓ)] + cH S A log2 (T ), where the last inequality follows from the AM–GM inequality. Thus, we obtain q q 3 7 3 1:T RegT (π) ≲ H 3 S 2 A log2 (T )L(π) + S 2 A log2 (T )E[Qπtrans (ℓ)] + H 2 S 2 A 2 log2 (T ). (108) Furthermore, we derive the bound in terms of HT − L(π). If RegT (π) < 0, the desired upper bound is trivial. Otherwise, RegT (π) ≥ 0 and (107) gives q q 1:T RegT (π) ≲ H 3 S 2 A log2 (T )(HT − L(π) − RegT (π)) + S 2 A log2 (T )E[Qπtrans (ℓ)] 7

+ H 2 S 2 A 2 log2 (T ) q q 3 7 3 1:T ≤ H 3 S 2 A log2 (T )(HT − L(π)) + S 2 A log2 (T )E[Qπtrans (ℓ)] + H 2 S 2 A 2 log2 (T ). (109) Combining (107)–(109) completes the proof. G.4

Proof for the stochastic regime with adversarial corruption

Theorem G.13 (bandit setting). Under the stochastic regime with adversarial corruption, Algorithm 1 with δ = T12 guarantees that, for any policy π, √ 3 7 3 RegT (π) ≲ U + U C + H 2 S 2 A 2 log2 (T ), 2

log (T ) where U = H S ∆Amin .

Proof. Since RegT (π) ≤ RegT (π̊) for all π, it suffices to bound RegT (π̊). By (101) and Lemmas G.8 and G.9 and δ = O(1/T 2 ), we have ι ≲ log(T ). Hence, there exists an absolute constant c > 0 such that v " # u X u X 7 3 3 2 tE RegT (π̊) ≤ cH 2 S 2 A 2 log (T ) + c log(T ) ζt (s, a) s,a

t∈Tr

}

term1

v " # u XX u 2 3 2 π π̊ t t + c H S A log (T )E [q (s, a) − q (s, a)] +

t∈Tr s,a

}

term2

v  u X u 2 2 2 tH S |Sh ||Sh+1 |A log (T )E

H−1 Xu

 X

[q πt (s, a) − q π̊ (s, a)]+  .

t∈Tr (s,a)∈Sh ×A

h=0

term3

} (110)

For term1 , by the definition of ζt (s, a), we have for any α > 0, v # " u Xu X 2 2 2 t (It (s, a) − πt (a | s)It (s)) (Lt,h(s) − Mt,h(s) ) term1 = c log (T )E s,a

t∈Tr

v # " u Xu X 2 π t t q (s, a)(1 − πt (a | s)) ≤ cH log (T )E s,a

t∈Tr

v # " u X X u X 2 π t ≤ 2cH log (T )E q t (s, a) s

a̸=π ⋆ (s)

≤ α(RegT (π̊) + 2C) +

t∈Tr

X X s

a̸=π ⋆ (s)

c2 H 2 log2 (T ) , 4α∆(s, a)

(111)

where the last line follows from Lemma D.16. For term2 , Lemma D.18 gives term2 ≤ α(RegT (π̊) + 4C) +

c2 H 4 S 2 A log2 (T ) . 4α∆min

(112)

For term3 , Lemma D.17 gives 2

PH−1 q h=0

H 2 S 2 |Sh ||Sh+1 |A log2 (T )

term3 ≤ α(RegT (π̊) + 4C) +

4α∆min

Moreover, by the AM–GM inequality, H−1 Xq

!2 H 2 S 2 |Sh ||Sh+1 |A log2 (T )

h=0

!2 q 1 2 2 2 (|Sh | + |Sh+1 |) H S A log (T ) ≤ 2 h=0 q 2 2 2 4 ≤ H S A log (T ) = H 2 S 4 A log2 (T ). H−1 X

Thus, we obtain term3 ≤ α(RegT (π̊) + 4C) +

c2 H 2 S 4 A log2 (T ) . 4α∆min

(113)

Combining (111)–(113) with (110), we obtain 2 4 3 7 3 H S A log2 (T ) RegT (π̊) ≤ α(3RegT (π̊) + 10C) + O + H 2 S 2 A 2 log2 (T ) . 4α∆min n q o 2 4 log2 (T ) Finally, choosing α = min 61 , UC with U = H S ∆Amin , we get √ RegT (π̊) ≲ U +

U C + H 2 S 2 A 2 log2 (T ).

Therefore, since RegT (π) ≤ RegT (π̊) for all π by the definition of π̊, the desired bound follows.

Record · ID 324899 · SHA-256 fd7bbda36d8c9a6c
Retrieved via Conceptio — every document is proof-bundled with source, license, and retrieval metadata.