Paper deep dive
Fast Rates for Offline Q-Learning with KL Regularization
Yize Hao, Guangxin Jiang, Shuang Qiu
Intelligence
Status: not_run | Model: - | Prompt: - | Confidence: 0%
Entities (0)
Relation Signals (0)
No relation signals yet.
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract:This paper investigates offline Q-learning for finite-horizon Markov decision processes with Kullback-Leibler (KL) regularization. Recent studies have shown that KL regularization can yield fast rates in offline decision-making problems. However, it remains unclear whether Q-learning, which adopts incremental stochastic approximation updates, can achieve such fast rates in the offline setting. We first propose KL-regularized Q-Learning (KLQ), a simple variant of classical Q-learning. By exploiting KL regularization, we prove that KLQ achieves a sample complexity of $\widetilde{O}(1/\epsilon)$ without explicit pessimism. This guarantee, however, has an exponential dependence on the KL regularization parameter and the horizon. To address this limitation, we further propose KL-regularized Pessimistic Q-Learning (KLPQ), which incorporates pessimism into KLQ. We prove that KLPQ retains the same \(\widetilde O(1/\epsilon)\) rate while removing the explicit exponential dependence, thereby further improving the sample complexity. To the best of our knowledge, these results establish the first fast-rate guarantees for offline Q-learning in tabular finite-horizon KL-regularized MDPs.
Tags
Links
- Source: https://arxiv.org/abs/2610.18839v1
- Canonical: https://arxiv.org/abs/2610.18839v1
Trouble viewing inline? Open PDF directly →
Full Text
123,045 characters extracted from source content.
Expand or collapse full text
Fast Rates for Offline Q-Learning with KL Regularization Yize Hao Guangxin Jiang Shuang Qiu† October 13, 2026 Abstract This paper investigates offline Q-learning for finite-horizon Markov decision processes with Kullback-Leibler (KL) regularization. Recent studies have shown that KL regularization can yield fast rates in offline decision-making problems. However, it remains unclear whether Q-learning, which adopts incremental stochastic approximation updates, can achieve such fast rates in the offline setting. We first propose KL-regularized Q-Learning (KLQ), a simple variant of classical Q-learning. By exploiting KL regularization, we prove that KLQ achieves a sample complexity of O~(1/ϵ) O(1/ε) without explicit pessimism. This guarantee, however, has an exponential dependence on the KL regularization parameter and the horizon. To address this limitation, we further propose KL-regularized Pessimistic Q-Learning (KLPQ), which incorporates pessimism into KLQ. We prove that KLPQ retains the same O~(1/ϵ) O(1/ε) rate while removing the explicit exponential dependence, thereby further improving the sample complexity. To the best of our knowledge, these results establish the first fast-rate guarantees for offline Q-learning in tabular finite-horizon KL-regularized MDPs. 00footnotetext: Corresponding Author11footnotetext: Harbin Institute of Technology. Email: 24b910001@stu.hit.edu.cn22footnotetext: City University of Hong Kong. Email: yizehao3-c@my.cityu.edu.hk33footnotetext: Harbin Institute of Technology. Email: gxjiang@hit.edu.cn44footnotetext: City University of Hong Kong. Email: shuanqiu@cityu.edu.hk 1 Introduction Offline reinforcement learning (RL) aims to learn a near-optimal policy from a fixed dataset without further interaction with the environment (Levine et al., 2020). A central challenge in this setting is limited data coverage: since the learner cannot collect additional samples, the learned policy may select actions that are poorly represented in the offline data, leading to inaccurate value estimates and extrapolation error (Fujimoto et al., 2019; Kumar et al., 2020). Two prominent approaches used to stabilize offline learning are pessimism and policy regularization. Pessimistic methods penalize value estimates in poorly covered regions to mitigate estimation errors caused by insufficient data (Rashidinejad et al., 2021; Jin et al., 2021; Shi et al., 2022). Policy regularization instead constrains the learned policy relative to a reference policy, with the Kullback–Leibler (KL) divergence being a widely used choice. When the reference policy coincides with the behavior policy that generates the offline data, KL regularization serves as behavior regularization, keeping the learned policy close to the behavior policy and thereby reducing distribution shift and extrapolation error (Wu et al., 2019). The reference policy, however, may differ from the behavior policy. In this case, KL regularization no longer directly constrains the learned policy toward the behavior policy. Nevertheless, Chen et al. (2026) show that KL regularization with respect to a fixed reference policy can stabilize offline learning in Markov games under unilateral concentrability. The practical importance of regularization is also reflected in reinforcement learning from human feedback and preference-based learning, where KL regularization is widely used to keep the learned policy close to a reference model (Ouyang et al., 2022; Xiong et al., 2023; Rafailov et al., 2023). These developments motivate a deeper understanding of the statistical role of KL regularization in offline learning. Recent theoretical work has revealed that KL regularization can substantially change the statistical behavior of offline learning. In single-step decision problems, fast rates have been established for KL-regularized contextual and multi-armed bandits (Zhao et al., 2025a; Zhao et al., 2026b; Ji et al., 2026a). Related results have also been established under forward-KL regularization (Zhao et al., 2026a). With KL regularization, these works achieve a sample complexity of O~(1/ϵ) O(1/ε), in contrast to the O~(1/ϵ2) O(1/ε^2) sample complexity typically obtained in standard unregularized settings. Fast rates have also been established for single-step zero-sum games (Zhang et al., 2026) and general-sum games (Chen and Zhang, 2026b). More recently, these results have been extended to multi-step sequential decision problems. In particular, Chen et al. (2026) establish a sample complexity of O~(1/ϵ) O(1/ε) for offline two-player zero-sum Markov games with KL regularization. From an algorithmic perspective, the methods of Chen et al. (2026) can be regarded as fitted Q-iteration. Their approach proceeds via backward induction, where Q-functions are estimated stagewise from the end of the horizon to the beginning. In contrast, another important class of algorithms is Q-learning, which adopts incremental stochastic approximation updates to solve the Bellman optimality equation (Watkins and Dayan, 1992). Understanding the statistical efficiency and convergence behavior of Q-learning remains an important topic in the theory of reinforcement learning (Li et al., 2024; Liu et al., 2025). The resulting update scheme differs fundamentally from backward induction, and existing fast-rate analyses based on backward induction do not establish analogous guarantees for Q-learning. In the offline RL setting, Shi et al. (2022) established finite-sample guarantees for pessimistic Q-learning under the standard unregularized objective and single-policy concentrability. Nevertheless, whether offline Q-learning can achieve fast rates for the KL-regularized objective remains unclear. This leads to the following question: Can offline Q-learning achieve fast rates with KL regularization? The above question poses three main challenges. First, although fast rates have been established for KL-regularized offline learning in several settings, the incremental updates of Q-learning pose additional challenges for finite-sample analysis, making it unclear how to exploit KL regularization to achieve similar fast rates. Second, existing finite-sample guarantees for offline Q-learning are established for the unregularized objective and rely on the principle of pessimism. It remains unclear whether pessimism is still necessary with KL regularization, or whether KL regularization alone can enable Q-learning to achieve fast rates. Third, the impact of pessimism on sample complexity under KL regularization remains underexplored for offline Q-learning. In this paper, we address these challenges and therefore answer this question affirmatively by developing two offline Q-learning algorithms for tabular finite-horizon KL-regularized MDPs. For an MDP with S states and A actions, let η>0η>0 denote the KL regularization parameter and let Cη⋆C_η denote the single-policy concentrability coefficient for the corresponding KL-regularized optimal policy. Given K offline trajectories of horizon H, our main contributions are summarized as follows. • We first introduce KL-regularized Q-Learning (KLQ), a simple variant of classical Q-learning without the principle of pessimism. We prove that KLQ achieves a sample complexity of O~(ηeηH(H+1)H8SACη⋆/ϵ) O\! (η e^η H(H+1)H^8SAC _η/ε ) for finding an ϵε-optimal policy. To the best of our knowledge, this is the first O~(1/ϵ) O(1/ε) sample complexity guarantee for Q-learning in an offline finite-horizon tabular setting. This result also demonstrates that pessimism is not necessary for achieving fast rates. • Based on KLQ, we propose KL-regularized Pessimistic Q-Learning (KLPQ), which further incorporates pessimism into KL-regularized Q-Learning. We prove that KLPQ achieves an improved sample complexity of O~(ηH7SACη⋆/ϵ) O (η H^7SAC_η /ε ). This removes KLQ’s explicit exponential dependence on the regularization parameter and horizon while retaining the fast rate. • On the technical side, we exploit the structure induced by KL regularization to establish a fast rate analysis of incremental Q-learning updates through a recursion for the squared Q-estimation error. We further show that pessimism sharpens both this error recursion and the conversion from Q-estimation error to policy suboptimality. 1.1 Related Work Offline RL. A large body of theoretical work studies offline RL under coverage conditions, with pessimism playing an important role in controlling estimation errors caused by insufficient data coverage (Rashidinejad et al., 2021; Xie et al., 2021b; Jin et al., 2021; Shi et al., 2022; Xie et al., 2021a; Yan et al., 2023; Qiao et al., 2026). This principle has been developed for both model-based and model-free methods (Rashidinejad et al., 2021; Xie et al., 2021b; Uehara and Sun, 2021; Shi et al., 2022; Zhang et al., 2024). Beyond the tabular setting, finite-sample guarantees have also been established with function approximation under partial coverage assumptions (Zhan et al., 2022; Xiong et al., 2022; Ye et al., 2023; Uehara et al., 2023). Fast Rates in KL-Regularized Learning. KL regularization can fundamentally change the statistical behavior of learning problems. In the online setting, for single-step problems, fast rates have been established for KL-regularized contextual bandits and RLHF (Zhao et al., 2025a), while logarithmic regret has also been established for KL-regularized multi-armed bandits (Ji et al., 2026b). For multi-step tabular problems, fast rates have been established for maximum entropy exploration (Tiapkin et al., 2023) and sequential RL with demonstration regularization (Tiapkin et al., 2024). In particular, the entropy regularization considered by Tiapkin et al. (2023) is equivalent to KL regularization with a uniform reference policy, up to an additive constant. Zhao et al. (2025b) establish logarithmic regret for KL-regularized episodic RL, while logarithmic regret has also been established for KL-regularized zero-sum Markov games (Nayak et al., 2025). Beyond the tabular setting, Hong et al. (2026) study KL-regularized RL with function approximation under misspecification. In offline learning, for single-step problems, fast rates are known for KL-regularized contextual and multi-armed bandits (Zhao et al., 2026b; Ji et al., 2026a; Zhao et al., 2026a), as well as preference learning and games (Wu et al., 2025; Zhang et al., 2026; Chen and Zhang, 2026b). The role of pessimism has also been studied in this setting. Ji et al. (2026a) establish matching upper and lower bounds across different regularization regimes for offline KL-regularized multi-armed bandits. Their algorithm constructs a pessimistic reward estimate and achieves the optimal sample complexity in both regimes. In contrast, Wu et al. (2025), Zhang et al. (2026), and Chen and Zhang (2026b) obtain fast rates without explicit pessimistic estimates in their respective settings. For multi-step decision problems, Chen et al. (2026) establish a sample complexity of O~(1/ϵ) O(1/ε) for offline Markov games with KL regularization. Their theoretical construction uses backward induction and is therefore different from the incremental Q-learning updates considered in this work. Q-Learning. Q-learning is a classical model-free method for solving the Bellman optimality equation (Watkins and Dayan, 1992; Even-Dar and Mansour, 2003). Under the standard unregularized objective, its non-asymptotic theory has been developed in several settings. For finite-horizon episodic MDPs, regret guarantees have been established for online Q-learning (Jin et al., 2018; Li et al., 2021b), while finite-sample guarantees have also been established for offline Q-learning under single-policy concentrability (Shi et al., 2022). For discounted MDPs, Q-learning has been studied under a generative model (Li et al., 2021a; Li et al., 2024), with Markovian samples (Qu and Wierman, 2020; Li et al., 2020), and in the offline setting under partial coverage (Yan et al., 2023). These results typically exhibit an O~(ϵ−2) O(ε^-2) dependence on accuracy for Q-function estimation or policy suboptimality. With linear function approximation, Liu et al. (2025) establish L2L^2 convergence rates of Q-learning to a bounded set. Finite-sample analyses have also been developed for average-reward Q-learning, under span contraction conditions (Zhang et al., 2021) and, more recently, for weakly communicating MDPs (Jiao et al., 2026). For regularized objectives, Uehara et al. (2023) study offline learning under partial coverage using soft Q-functions, but estimate the Q-functions through minimax optimization. Jeong and Lee (2024); Jeong and Lee (2025) provide finite-time analyses of soft Q-learning in discounted tabular MDPs under full state-action coverage, while Xi et al. (2025) study regularized Q-learning with linear function approximation using an algorithm with two time scales. These works do not address offline Q-learning in finite-horizon MDPs. 1.2 Notation For a positive integer n, we write [n]:=1,…,n[n]:=\1,…,n\. For a finite set X, let Δ() (X) denote the probability simplex over X. For functions f,g:→ℝf,g:X , we write ⟨f,g⟩:=∑x∈f(x)g(x) f,g _X:= _x f(x)g(x), and omit the subscript when the underlying set is clear from context. For p∈Δ()p∈ (X), we denote its support by supp(p):=x∈:p(x)>0supp(p):=\x :p(x)>0\. For a function f:→ℝf:X and p∈Δ()p∈ (X), we use x∼p[f(x)]:=∑x∈p(x)f(x)E_x p[f(x)]:= _x p(x)f(x) when X is finite. We use ℰ1\E\ for the indicator of an event ℰE, and write x∨y:=maxx,yx y:= \x,y\ for scalars. Inequalities between vectors or functions are understood pointwise unless otherwise stated. We use O~(f) O(f) to suppress factors polylogarithmic in f, other relevant problem parameters, and the inverse failure probability. 2 Problem Setup 2.1 Finite-Horizon KL-Regularized MDPs Markov Decision Process. We consider a finite-horizon episodic Markov decision process (MDP) denoted by the tuple ℳ=(,,H,ρ,ℙ,r)M=(S,A,H,ρ,P,r), where S and A are finite state and action sets, H is the episode length, and ρ∈Δ()ρ∈ (S) is the initial state distribution. We write S:=||S:=|S|, A:=||A:=|A|, and Lh:=H−h+1L_h:=H-h+1 with LH+1:=0L_H+1:=0. The transition kernel is ℙ:=ℙhh=1HP:=\P_h\_h=1^H, where ℙh:×→Δ()P_h:S×A→ (S), and the deterministic reward function is r:=rhh=1Hr:=\r_h\_h=1^H, where rh:×→[0,1]r_h:S×A→[0,1]. We write ℙh,s,a:=ℙh(⋅∣s,a)P_h,s,a:=P_h(· s,a). For f:→ℝf:S , the transition operator is (ℙhf)(s,a):=⟨ℙh,s,a,f⟩=∑s′∈ℙh(s′∣s,a)f(s′)(P_hf)(s,a):= _h,s,a,f _S= _s P_h(s s,a)f(s ). A Markov policy is π:=πhh=1Hπ:=\ _h\_h=1^H with πh(⋅∣s)∈Δ() _h(· s)∈ (A). Starting from s1∼ρs_1 ρ, a trajectory is generated according to ah∼πh(⋅∣sh)a_h _h(· s_h) and sh+1∼ℙh(⋅∣sh,ah)s_h+1 _h(· s_h,a_h). We denote the state occupancy by dhπ(s):=Prρ,π,ℙ(sh=s)d_h^π(s):= _ρ,π,P(s_h=s) for h∈[H+1]h∈[H+1], and the state-action occupancy by dhπ(s,a):=dhπ(s)πh(a∣s)d_h^π(s,a):=d_h^π(s) _h(a s) for h∈[H]h∈[H]. Accordingly, d1π(s)=ρ(s)d_1^π(s)=ρ(s) and dh+1π(s′)=∑s,adhπ(s,a)ℙh(s′∣s,a)d_h+1^π(s )= _s,ad_h^π(s,a)P_h(s s,a) for h∈[H]h∈[H]. KL-regularized Value Functions. We now incorporate KL regularization into the MDP defined above. Following the standard framework of regularized MDPs (Geist et al., 2019), fix a reference policy πref:=πhrefh=1Hπ^ref:=\ _h^ref\_h=1^H and a regularization parameter η>0η>0. The coefficient 1/η1/η determines the strength of the KL regularization with respect to the reference policy. For any policy π, we define its KL-regularized value function at step h by Vhπ(s):=π,ℙ[∑t=hH(rt(st,at)−1ηlogπt(at∣st)πtref(at∣st))|sh=s].V_h^π(s):=E_π,P [ . _t=h^H (r_t(s_t,a_t)- 1η _t(a_t s_t) _t^ref(a_t s_t) ) |s_h=s ]. Set VH+1π≡0V_H+1^π≡ 0 and define the corresponding Q-function by Qhπ(s,a):=rh(s,a)+(ℙhVh+1π)(s,a).Q_h^π(s,a):=r_h(s,a)+(P_hV_h+1^π)(s,a). We use the standard convention that KL(p||q)=+∞KL(p||q)=+∞ whenever p is not absolutely continuous with respect to q, and otherwise define KL(p||q):=∑ap(a)logp(a)q(a)KL(p||q):= _ap(a) p(a)q(a), with 0log0:=00 0:=0 and 0log(0/0):=00 (0/0):=0. Under this convention, the corresponding value functions Vhπ(s)V_h^π(s) and Qhπ(s,a)Q_h^π(s,a) may take the value −∞-∞. Throughout the paper, we adopt the convention 0⋅(±∞)=00·(±∞)=0. These functions satisfy the regularized Bellman consistency identity Vhπ(s)=⟨πh(⋅∣s),Qhπ(s,⋅)⟩−1ηKL(πh(⋅∣s)∥πhref(⋅∣s)).V_h^π(s)= _h(· s),Q_h^π(s,·) _A- 1ηKL ( _h(· s) \| _h^ref(· s) ). Regularized Bellman Optimality. For Qh(s,⋅)∈ℝAQ_h(s,·) ^A, define the regularized Bellman operator and Gibbs map by Fh,s(Qh(s,⋅)):=1ηlog⟨πhref(⋅∣s),eηQh(s,⋅)⟩,F_h,s\! (Q_h(s,·) ):= 1η _h^ref(· s),e^η Q_h(s,·) _A, (1) Gh,s(Qh(s,⋅))(a):=πhref(a∣s)eηQh(s,a)∑a′∈πhref(a′∣s)eηQh(s,a′).G_h,s\! (Q_h(s,·) )(a):= _h^ref(a s)e^η Q_h(s,a) _a _h^ref(a s)e^η Q_h(s,a ). (2) The Gibbs variational identity is Fh,s(Qh(s,⋅))=maxπh(⋅∣s)∈Δ()⟨πh(⋅∣s),Qh(s,⋅)⟩−1ηKL(πh(⋅∣s)∥πhref(⋅∣s)),F_h,s\! (Q_h(s,·) )= _ _h(· s)∈ (A) \ _h(· s),Q_h(s,·) _A- 1ηKL ( _h(· s) \| _h^ref(· s) ) \, with unique maximizer Gh,s(Qh(s,⋅))G_h,s(Q_h(s,·)). For every h,sh,s, define the optimal value function by Vh⋆(s):=supπ∈ΠVhπ(s)V_h (s):= _π∈ V_h^π(s), where Π denotes the class of Markov policies, and let VH+1⋆≡0V_H+1 ≡ 0. These results follow from the standard characterization of KL-regularized Bellman optimality (Geist et al., 2019; Zhao et al., 2025b). Proposition 2.1. There exists a KL-regularized optimal policy π⋆π , whose value and Q-functions satisfy, for every (h,s,a)(h,s,a), Qh⋆(s,a) Q_h (s,a) =rh(s,a)+(ℙhVh+1⋆)(s,a),Vh⋆(s)=Fh,s(Qh⋆(s,⋅)), =r_h(s,a)+(P_hV_h+1 )(s,a), V_h (s)=F_h,s(Q_h (s,·)), with the optimal policy given by πh⋆(⋅∣s)=Gh,s(Qh⋆(s,⋅)) _h (· s)=G_h,s(Q_h (s,·)). Moreover, Vhπ(s)≤Vh⋆(s)V_h^π(s)≤ V_h (s) and Qhπ(s,a)≤Qh⋆(s,a)Q_h^π(s,a)≤ Q_h (s,a) for every policy π, and the value ranges satisfy 0≤Vh⋆(s)≤Lh,0≤Qh⋆(s,a)≤Lh.0≤ V_h (s)≤ L_h, 0≤ Q_h (s,a)≤ L_h. (3) 2.2 Offline Learning and Data Coverage Offline Data. Let μ:=μhh=1Hμ:=\ _h\_h=1^H be a behavior policy. The offline dataset Dμ:=τkk=1KD_μ:=\τ^k\_k=1^K consists of K independent trajectories τk=(s1k,a1k,r1k,s2k,…,sHk,aHk,rHk,sH+1k)τ^k=(s_1^k,a_1^k,r_1^k,s_2^k,…,s_H^k,a_H^k,r_H^k,s_H+1^k), where s1k∼ρs_1^k ρ, ahk∼μh(⋅∣shk)a_h^k _h(· s_h^k), sh+1k∼ℙh(⋅∣shk,ahk)s_h+1^k _h(· s_h^k,a_h^k), and rhk=rh(shk,ahk)r_h^k=r_h(s_h^k,a_h^k). The total number of transitions is T=KHT=KH. Since no further interaction with the environment is allowed, a finite-sample guarantee requires the offline data to provide sufficient coverage of the state-action pairs relevant to the target policy. We formalize this requirement through single-policy concentrability. Single-policy Concentrability. Following prior analyses of offline RL under single-policy concentrability (Rashidinejad et al., 2021; Xie et al., 2021b; Shi et al., 2022), we impose the following coverage assumption. It compares the occupancy measure of the KL-regularized optimal policy with that induced by the behavior policy. The coefficient Cη⋆C_η therefore measures how well the behavior policy covers the KL-regularized optimal policy π⋆π , where the subscript η reflects the dependence of π⋆π and its occupancy measure on the regularization strength. Assumption 2.2 (Single-policy concentrability). The behavior policy μ satisfies max(h,s,a)∈[H]×dhπ⋆(s,a)dhμ(s,a)≤Cη⋆ _(h,s,a)∈[H]×S×A d_h^π (s,a)d_h^μ(s,a)≤ C_η for some Cη⋆∈[1,∞)C_η ∈[1,∞), where 0/0:=00/0:=0 and x/0:=+∞x/0:=+∞ for x>0x>0. Remark 2.1. Several recent fast rate analyses consider the setting where πrefπ^ref is also the behavior policy generating the offline data (Zhao et al., 2026b; Ji et al., 2026a; Zhao et al., 2026a). By Proposition 2.1 and the Gibbs map in equation (2), supp(πh⋆(⋅∣s))=supp(πhref(⋅∣s))supp( _h (· s))=supp( _h^ref(· s)) for every (h,s)(h,s). Consequently, when μ=πrefμ=π^ref, the occupancy measure of π⋆π is automatically covered by that of μ, and hence Cη⋆C_η is finite. In contrast, we do not require the behavior policy μ to coincide with the reference policy πrefπ^ref. In this more general setting, Assumption 2.2 requires the occupancy measure of π⋆π to be covered by that of μ. In particular, the behavior policy must cover the action support of the reference policy at states visited by π⋆π . Learning Objective. Our goal is to learn a policy π that maximizes the KL-regularized return Jη(π):=s1∼ρ[V1π(s1)]J_η(π):=E_s_1 ρ[V_1^π(s_1)], and we measure the policy’s performance by SubOpt(π):=Jη(π⋆)−Jη(π),SubOpt(π):=J_η(π )-J_η(π), that is, the suboptimality of policy π under the initial distribution ρ. In addition, we say that a policy π is ϵε-optimal if SubOpt(π)≤ϵSubOpt(π)≤ε. 3 Pessimism-Free KL-Regularized Q-Learning In this section, we propose KL-regularized Q-Learning (KLQ), a pessimism-free algorithm for the KL-regularized objective. We first recall the classical Q-learning update (Watkins and Dayan, 1992). Classical Q-learning can be viewed as a stochastic approximation scheme for solving the Bellman optimality equation. Upon observing a transition (sh,ah,rh,sh+1)(s_h,a_h,r_h,s_h+1) at step h, the corresponding Q-estimate is updated according to Qh(sh,ah)←(1−αn)Qh(sh,ah)+αn(rh+Vh+1(sh+1)),Q_h(s_h,a_h)←(1- _n)Q_h(s_h,a_h)+ _n (r_h+V_h+1(s_h+1) ), where αn _n denotes the learning rate associated with the n-th visit to (sh,ah)(s_h,a_h). In the standard unregularized setting, the value estimate is obtained by the hard maximum Vh(s)=maxa∈Qh(s,a)V_h(s)= _a Q_h(s,a). For our KL-regularized objective, we retain the same stochastic approximation form of the Q-learning update and replace the hard maximum with the regularized Bellman operator Fh,sF_h,s defined in equation (1). Specifically, we set Vh(s)=Fh,s(Qh(s,⋅))V_h(s)=F_h,s(Q_h(s,·)), and the policy associated with the Q estimate is given by Gh,s(Qh(s,⋅))G_h,s(Q_h(s,·)), where Gh,sG_h,s is defined in equation (2). Similar to standard Q-learning, KLQ only updates the visited state-action pair when processing the offline trajectories. For the n-th visit to a state-action pair, we use the standard finite-horizon Q-learning step size αn=H+1H+n _n= H+1H+n from Jin et al. (2018). Let k denote the trajectory index, while n counts how many times the current state-action pair has been visited, including the current visit. Thus, n=Nhk+1(shk,ahk)n=N_h^k+1(s_h^k,a_h^k). After processing all K trajectories, the output policy is given by π^h(⋅∣s)=Gh,s(Q^h(s,⋅)) π_h(· s)=G_h,s ( Q_h(s,·) ) with Q^h=QhK+1 Q_h=Q_h^K+1. Algorithm 1 summarizes the resulting procedure. Algorithm 1 KL-Regularized Q-Learning (KLQ) 1: Offline dataset DμD_μ, reference policy πrefπ^ref, regularization parameter η>0η>0 2: Initialize Qh1(s,a)=0Q_h^1(s,a)=0 and Nh1(s,a)=0N_h^1(s,a)=0 for every (h,s,a)∈[H]×(h,s,a)∈[H]×S×A 3: Set Vh1(s)=Fh,s(Qh1(s,⋅))=0V_h^1(s)=F_h,s(Q_h^1(s,·))=0 for every (h,s)∈[H]×(h,s)∈[H]×S, and set VH+1k≡0V_H+1^k≡ 0 4: for k=1,…,Kk=1,…,K do 5: Read the k-th trajectory τkτ^k from DμD_μ 6: Copy QkQ^k, VkV^k, and NkN^k to Qk+1Q^k+1, Vk+1V^k+1, and Nk+1N^k+1, respectively 7: for h=1,…,Hh=1,…,H do 8: Nhk+1(shk,ahk)=Nhk(shk,ahk)+1N_h^k+1(s_h^k,a_h^k)=N_h^k(s_h^k,a_h^k)+1 9: n=Nhk+1(shk,ahk)n=N_h^k+1(s_h^k,a_h^k) 10: αn=H+1H+n _n= H+1H+n 11: Qhk+1(shk,ahk)=(1−αn)Qhk(shk,ahk)+αn(rhk+Vh+1k(sh+1k))Q_h^k+1(s_h^k,a_h^k)=(1- _n)Q_h^k(s_h^k,a_h^k)+ _n(r_h^k+V_h+1^k(s_h+1^k)) 12: Vhk+1(shk)=Fh,shk(Qhk+1(shk,⋅))V_h^k+1(s_h^k)=F_h,s_h^k(Q_h^k+1(s_h^k,·)) 13: end for 14: end for 15: Q^h=QhK+1 Q_h=Q_h^K+1 and π^h(⋅∣s)=Gh,s(Q^h(s,⋅)) π_h(· s)=G_h,s( Q_h(s,·)) Compared with the pessimistic Q-learning algorithm of Shi et al. (2022), KLQ does not use an explicit pessimistic bonus or a monotone max update. While the algorithm of Shi et al. (2022) adjusts the Q-learning target by a pessimistic penalty and updates the value estimate monotonically, the Q update of KLQ is the same as in classical Q-learning, with the value function and policy determined by the KL-regularized Bellman equations. We provide the finite-sample guarantee for KLQ in the following theorem. Theorem 3.1. Suppose Assumption 2.2 holds. For any δ∈(0,1)δ∈(0,1), define ι:=logSATδ := SATδ. Then, with probability at least 1−δ1-δ, the policy π π returned by Algorithm 1 satisfies SubOpt(π^)≤cηeηH(H+1)H7SACη⋆Kι4(1+logK),SubOpt( π)≤ c η e^η H(H+1)H^7SAC_η K ^4(1+ K), where c>0c>0 is a sufficiently large universal constant. As a consequence, KLQ is guaranteed to find an ϵε-optimal policy with sample complexity O~(ηeηH(H+1)H8SACη⋆/ϵ) O\! (η e^η H(H+1)H^8SAC_η /ε ). Remark 3.1. Notably, the bound in Theorem 3.1 contains the exponential factor eηH(H+1)e^η H(H+1), which can become large as the horizon increases for fixed η>0η>0. Similar exponential dependence appears in recent analyses of KL-regularized offline learning without pessimism. In single-step problems, the bound can depend exponentially on the KL-regularization parameter (Wu et al., 2025; Chen and Zhang, 2026a), while in multi-step Markov games the corresponding factors may accumulate over the horizon (Chen et al., 2026). In our analysis, the likelihood-ratio argument compares Gh,s(Qhk(s,⋅))G_h,s(Q_h^k(s,·)) with πh⋆(⋅∣s) _h (· s) using the Gibbs map defined in equation (2). These comparisons contribute to both stagewise error propagation and the conversion from Q-estimation error to policy suboptimality, as explained in Section 5.1. 4 KL-Regularized Pessimistic Q-Learning Although KLQ achieves a fast rate, Theorem 3.1 contains an exponential factor in η and H. This motivates us to further propose KL-regularized Pessimistic Q-Learning (KLPQ) to improve this dependence. KLPQ retains the regularized value and policy updates of KLQ in Algorithm 1, while modifying the Q-estimation procedure through a pessimistic bonus and a monotone update. More specifically, KLPQ introduces the pessimistic bonus bh,n:=cbLh+1ιHnwith ι:=logSATδ and n≥1,b_h,n:=c_bL_h+1 Hn ~ := SATδ~and~n≥ 1, (4) where cb>0c_b>0 is a fixed universal constant. In KLPQ, we maintain an auxiliary Q estimate Q~k Q^k in addition to QkQ^k. At the n-th visit to (shk,ahk)(s_h^k,a_h^k), we first update Q~hk+1(shk,ahk) Q_h^k+1(s_h^k,a_h^k) using the pessimistic Q-learning target: Q~hk+1(shk,ahk)=(1−αn)Q~hk(shk,ahk)+αn(rhk+Vh+1k(sh+1k)−bh,n). Q_h^k+1(s_h^k,a_h^k)=(1- _n) Q_h^k(s_h^k,a_h^k)+ _n (r_h^k+V_h+1^k(s_h+1^k)-b_h,n ). Algorithm 2 KL-Regularized Pessimistic Q-Learning (KLPQ) 1: Offline dataset DμD_μ, reference policy πrefπ^ref, regularization parameter η>0η>0, failure probability δ∈(0,1)δ∈(0,1) 2: Set ι=logSATδ = SATδ and bh,n=cbLh+1ιHnb_h,n=c_bL_h+1 Hn for a fixed sufficiently large universal constant cbc_b 3: Initialize Q~h1(s,a)=0 Q_h^1(s,a)=0, Qh1(s,a)=0Q_h^1(s,a)=0, and Nh1(s,a)=0N_h^1(s,a)=0 for every (h,s,a)∈[H]×(h,s,a)∈[H]×S×A 4: Set Vh1(s)=Fh,s(Qh1(s,⋅))=0V_h^1(s)=F_h,s(Q_h^1(s,·))=0 for every (h,s)∈[H]×(h,s)∈[H]×S, and set VH+1k≡0V_H+1^k≡ 0 5: for k=1,…,Kk=1,…,K do 6: Read the k-th trajectory τkτ^k from DμD_μ 7: Copy Q~k Q^k, QkQ^k, VkV^k, and NkN^k to Q~k+1 Q^k+1, Qk+1Q^k+1, Vk+1V^k+1, and Nk+1N^k+1, respectively 8: for h=1,…,Hh=1,…,H do 9: Nhk+1(shk,ahk)=Nhk(shk,ahk)+1N_h^k+1(s_h^k,a_h^k)=N_h^k(s_h^k,a_h^k)+1 10: n=Nhk+1(shk,ahk)n=N_h^k+1(s_h^k,a_h^k) 11: αn=H+1H+n _n= H+1H+n 12: Q~hk+1(shk,ahk)=(1−αn)Q~hk(shk,ahk)+αn(rhk+Vh+1k(sh+1k)−bh,n) Q_h^k+1(s_h^k,a_h^k)=(1- _n) Q_h^k(s_h^k,a_h^k)+ _n(r_h^k+V_h+1^k(s_h+1^k)-b_h,n) 13: Qhk+1(shk,ahk)=maxQhk(shk,ahk),Q~hk+1(shk,ahk)Q_h^k+1(s_h^k,a_h^k)= \Q_h^k(s_h^k,a_h^k), Q_h^k+1(s_h^k,a_h^k)\ 14: Vhk+1(shk)=Fh,shk(Qhk+1(shk,⋅))V_h^k+1(s_h^k)=F_h,s_h^k(Q_h^k+1(s_h^k,·)) 15: end for 16: end for 17: Q^h=QhK+1 Q_h=Q_h^K+1 and π^h(⋅∣s)=Gh,s(Q^h(s,⋅)) π_h(· s)=G_h,s( Q_h(s,·)) Inspired by Shi et al. (2022), we use the monotone max update Qhk+1(shk,ahk)=maxQhk(shk,ahk),Q~hk+1(shk,ahk),Q_h^k+1(s_h^k,a_h^k)= \Q_h^k(s_h^k,a_h^k), Q_h^k+1(s_h^k,a_h^k) \, which ensures that the Q estimate does not decrease after each update. The two Q estimates serve different roles. The auxiliary iterate Q~k Q^k follows the Q-learning update with the pessimistic bonus, while QkQ^k records the monotone estimate used to compute the regularized value function. In the basic LCB-Q algorithm of Shi et al. (2022), monotonicity is enforced directly at the value level by taking the maximum of the previous value estimate and maxaQh(s,a) _aQ_h(s,a). In our regularized setting, the value estimate is instead given by Fh,s(Qh(s,⋅))F_h,s(Q_h(s,·)), where Fh,sF_h,s is defined in equation (1). Accordingly, we apply the max update to the Q estimate and then compute the value through Fh,sF_h,s. Since Fh,sF_h,s is monotone in each coordinate, the value estimates are also nondecreasing. This monotone construction supports the pessimism guarantee and enables direct control of the final iterate error. For each k∈[K+1]k∈[K+1], let πkπ^k denote the policy induced by QkQ^k, i.e., πhk(⋅∣s):=Gh,s(Qhk(s,⋅)) _h^k(· s):=G_h,s(Q_h^k(s,·)). In particular, π^=πK+1 π=π^K+1. Algorithm 2 summarizes the resulting procedure. We provide the finite-sample guarantee for KLPQ in the following theorem. Theorem 4.1. Suppose Assumption 2.2 holds. For any δ∈(0,1)δ∈(0,1), the policy π π returned by Algorithm 2 satisfies, with probability at least 1−δ1-δ, SubOpt(π^)≤cηH6SACη⋆Kι3(1+logK),SubOpt( π)≤ c η H^6SAC_η K ^3(1+ K), where c>0c>0 is a universal constant. As a consequence, KLPQ is guaranteed to find an ϵε-optimal policy with sample complexity O~(ηH7SACη⋆/ϵ) O\! (η H^7SAC_η /ε ). Compared with Theorem 3.1, Theorem 4.1 removes the explicit factor eηH(H+1)e^η H(H+1) and improves the polynomial dependence on H by one factor. This improvement holds for any fixed η>0η>0, without changing the KL-regularized objective or the concentrability coefficient Cη⋆C_η . The effect of varying η on the learning objective and data coverage is discussed later in this section. Remark 4.1. A similar role of pessimism has also been observed in KL-regularized offline bandits, where Ji et al. (2026a) construct a pessimistic reward estimate and obtain polynomial rather than exponential dependence on η. Their setting is single-step, so pessimism is imposed directly on the reward estimate before forming the Gibbs policy. KLPQ, by contrast, maintains pessimism throughout the multi-step Q-learning updates. Remark 4.2. Explicit exponential dependence can also be avoided without pessimism when additional structure is available. For example, in single-step zero-sum games, Zhang et al. (2026) exploit equilibrium stability and the skew-symmetry of the game operator to localize the analysis to unilateral estimation errors. Their argument relies on a problem-specific structure. In the multi-step Q-learning problem considered here, we instead use pessimism to remove the exponential factor. Comparison with Unregularized Offline Q-Learning. Our work is closely related to the offline pessimistic Q-learning analysis of Shi et al. (2022), which also considers finite-horizon tabular MDPs under single-policy concentrability. However, their work studies the standard unregularized objective. Their LCB-Q-Advantage algorithm achieves a sample complexity of O~(H4SC⋆/ϵ2+H5SC⋆/ϵ) O(H^4SC /ε^2+H^5SC /ε). Its leading ϵ−2ε^-2 term matches the minimax lower bound Ω~(H4SC⋆/ϵ2) (H^4SC /ε^2) up to logarithmic factors (Xie et al., 2021b). We note that our guarantee concerns the KL-regularized objective and its corresponding optimal policy. Thus, its dependence on the problem parameters is not directly comparable with the bound of Shi et al. (2022). In particular, the KL-regularized optimal policy is generally stochastic, so the corresponding coverage requirement can involve multiple actions at each state, leading to the additional factor A in our current bound. The main distinction is the dependence on the target accuracy. For the KL-regularized objective, we bound policy suboptimality by the squared Q-estimation error. Thus, an O~(1/K) O(1/K) bound on the squared estimation error yields an O~(1/K) O(1/K) policy-suboptimality rate. Accordingly, KLPQ achieves O~(ηH7SACη⋆/ϵ) O(η H^7SAC_η /ε) for fixed η, rather than the ϵ−2ε^-2 dependence in the unregularized setting. This difference does not contradict the minimax lower bound of Xie et al. (2021b), which applies to the standard unregularized objective. Effect of Regularization Strength. An important point in interpreting our results is that the learning objective itself depends on the regularization strength. Although Theorems 3.1 and 4.1 do not impose additional restrictions on η>0η>0 beyond Assumption 2.2, choosing η affects both the learning objective and the sample complexity guarantees. For example, the exponential factor in Theorem 3.1 can make the fast-rate guarantee less informative as the horizon increases. A natural way to control this factor is to choose η=Θ(H−2)η= (H^-2). However, this also strengthens the KL regularization and changes the learning objective itself. In particular, as η becomes sufficiently small, the regularized optimal policy approaches the reference policy. In this regime, the learning problem can become trivial, since the reference policy itself may already achieve the desired accuracy without using any offline data. Thus, the choice of η should reflect the tradeoff between staying close to the reference policy and improving reward performance through offline learning. 5 Theoretical Analysis In this section, we provide proof sketches for Theorems 3.1 and 4.1. We first analyze KLQ and then show how pessimism changes the analysis for KLPQ. For simplicity, throughout this section, we use O~(⋅) O(·) to suppress polynomial dependencies on H, S, A, and Cη⋆C_η , as well as logarithmic factors in the problem parameters, while keeping the dependence on K and η explicit. The full parameter dependencies are provided in the main theorems and their detailed proofs in Appendices C and D. 5.1 Analysis for KLQ For each k and h, define ehk(s):=a∼πh⋆(⋅∣s)[(Qhk(s,a)−Qh⋆(s,a))2]e_h^k(s):=E_a _h (· s)[(Q_h^k(s,a)-Q_h (s,a))^2], with eH+1k≡0e_H+1^k≡ 0. Let γh:=e2ηLh _h:=e^2η L_h, γH+1:=1 _H+1:=1, and Γa:b:=∏j=abγj _a:b:= _j=a^b _j, with Γa:b:=1 _a:b:=1 when a>ba>b. Proof Sketch of Theorem 3.1. By Lemma C.2, the policy suboptimality satisfies SubOpt(π^)≤η2∑h=1HΓ1:h(s,a)∼dhπ⋆[(QhK+1(s,a)−Qh⋆(s,a))2].SubOpt( π)≤ η2 _h=1^H [rgb]0,0,1 _1:hE_(s,a) d_h^π [(Q_h^K+1(s,a)-Q_h (s,a))^2 ]. (5) Thus, it suffices to control the squared error of the final Q iterate. To this end, we first relate the error at stage h to that at stage h+1h+1 and then apply a backward recursion. Define ℰh:=∑k=1Ks∼dhπ⋆[ehk(s)]E_h:= _k=1^KE_s d_h^π [e_h^k(s)], with ℰH+1:=0E_H+1:=0. By Lemma C.4, with high probability, ℰh≤(1+5H)γh+1ℰh+1+O~(γh+1(1+logK)).E_h≤ (1+ 5H ) [rgb]0,0,1 _h+1E_h+1+ O\! ( [rgb]0,0,1 _h+1(1+ K) ). (6) In the recursion (6), the first term corresponds to the error propagated from stage h+1h+1, while the second term is the accumulated statistical error. As the statistical error grows only polylogarithmically with K, backward iteration yields ℰh≤Γh+1:HO~(1).E_h≤ [rgb]0,0,1 _h+1:H\, O(1). (7) The bound in (7) controls the cumulative squared Q-estimation error ℰhE_h, whereas bound (5) requires controlling the final-iterate error. Since the Q-estimates of KLQ are not monotone, the cumulative error bound does not directly yield a bound for the final iterate. To address this issue, we apply Lemma C.5 to relate the final-iterate error to the cumulative error at the next stage. Specifically, we obtain s∼dhπ⋆[ehK+1(s)]≤γh+1KO~(1+ℰh+1)≤Γh+1:HKO~(1)E_s d_h^π [e_h^K+1(s)]≤ [rgb]0,0,1 _h+1K\, O(1+E_h+1)≤ [rgb]0,0,1 _h+1:HK\, O(1). Substituting this into (5) and using Γ1:hΓh+1:H=eηH(H+1) _1:h _h+1:H=e^η H(H+1), we obtain SubOpt(π^)≤ηeηH(H+1)O~(K−1),SubOpt( π)≤ [rgb]0,0,1η e^η H(H+1)\, O(K^-1), which proves Theorem 3.1. The exponential factor arises from both stagewise error propagation and the conversion to policy suboptimality. 5.2 Analysis for KLPQ Proof Sketch of Theorem 4.1. For KLPQ, let QhkQ_h^k and VhkV_h^k be its iterates, and define ehke_h^k and ℰhE_h as in Section 5.1. By the construction of pessimistic Q-estimates and the monotone update in Algorithm 2, Lemma D.2 ensures, with high probability, Qhk(s,a)≤Qhπk(s,a)≤Qh⋆(s,a)Q_h^k(s,a)≤ Q_h^π^k(s,a)≤ Q_h (s,a). The pointwise pessimism property plays a crucial role in removing the exponential factors in the KLQ analysis. For KLQ, the bound (Vhk(s)−Vh⋆(s))2≤γhehk(s)(V_h^k(s)-V_h (s))^2≤ _he_h^k(s) in inequality (14) introduces the factor γh+1 _h+1 into the squared-error recursion (6). In contrast, for KLPQ, the pointwise pessimism property and the convexity of the regularized Bellman operator yield (Vh⋆(s)−Vhk(s))2≤ehk(s)(V_h (s)-V_h^k(s))^2≤ e_h^k(s) as shown in inequality (40), avoiding this additional factor in the error recursion. For KLQ, as detailed in our proof, the likelihood-ratio argument is used both to bound the KL divergence between π π and π⋆π and to compare their occupancy measures, resulting in the factor Γ1:h _1:h in bound (5). In contrast, for KLPQ, this property and the Gibbs formula allow us to control policy suboptimality directly under dhπ⋆d_h^π , without requiring such an occupancy comparison. Specifically, by Lemma D.3, we obtain SubOpt(π^)≤η∑h=1Hs∼dhπ⋆[ehK+1(s)].SubOpt( π)≤ [rgb]0,0,1η _h=1^HE_s d_h^π [e_h^K+1(s)]. Applying Lemma D.4 and following the analysis for KLQ in Lemma C.4, we obtain, with high probability, ℰh≤(1+5H)ℰh+1+O~(1+logK).E_h≤ (1+ 5H )E_h+1+ O(1+ K). Iterating this recursion backward and using the polylogarithmic dependence of the statistical error on K, we obtain ℰh≤O~(1)E_h≤ O(1). Finally, by the pointwise pessimism property and the monotone update in Algorithm 2, we have 0≤Qh⋆−QhK+1≤Qh⋆−Qhk0≤ Q_h -Q_h^K+1≤ Q_h -Q_h^k for every k∈[K]k∈[K], which further yields s∼dhπ⋆[ehK+1(s)]≤1K∑k=1Ks∼dhπ⋆[ehk(s)]=ℰhK≤O~(K−1)E_s d_h^π [e_h^K+1(s)]≤ 1K _k=1^KE_s d_h^π [e_h^k(s)]= E_hK≤ O(K^-1). Combining the above bounds, we obtain SubOpt(π^)≤ηO~(K−1).SubOpt( π)≤ [rgb]0,0,1η\, O(K^-1). Compared with the final-iterate argument in Lemma C.5, this direct averaging argument also saves one factor of H, yielding the sharper horizon dependence in Theorem 4.1. 6 Conclusion In this paper, we study offline Q-learning for finite-horizon KL-regularized MDPs. We first propose KL-regularized Q-Learning (KLQ) and establish an O~(1/ϵ) O(1/ε) sample complexity without explicit pessimism. We then develop KL-regularized Pessimistic Q-Learning (KLPQ), which achieves the same rate while removing the explicit exponential dependence on the regularization parameter and horizon. These results establish fast-rate guarantees for offline Q-learning with KL regularization and demonstrate the benefit of pessimism in improving sample complexity. Appendix Appendix A Proof of Proposition 2.1 Proof. Define V¯H+1≡0 V_H+1≡ 0 and recursively set Q¯h:=rh+ℙhV¯h+1 Q_h:=r_h+P_h V_h+1, V¯h(s):=Fh,s(Q¯h(s,⋅)) V_h(s):=F_h,s( Q_h(s,·)), and π¯h(⋅∣s):=Gh,s(Q¯h(s,⋅)) π_h(· s):=G_h,s( Q_h(s,·)). We prove by backward induction that Vhπ≤V¯hV_h^π≤ V_h for every policy π and Vhπ¯=V¯hV_h π= V_h. Both claims are immediate at H+1H+1. If Vh+1π≤V¯h+1V_h+1^π≤ V_h+1, then Vhπ(s) V_h^π(s) =⟨πh(⋅∣s),rh(s,⋅)+(ℙhVh+1π)(s,⋅)⟩−1ηKL(πh(⋅∣s)∥πhref(⋅∣s)) = _h(· s),r_h(s,·)+(P_hV_h+1^π)(s,·) _A- 1ηKL\! ( _h(· s) \| _h^ref(· s) ) ≤⟨πh(⋅∣s),Q¯h(s,⋅)⟩−1ηKL(πh(⋅∣s)∥πhref(⋅∣s)) ≤ _h(· s), Q_h(s,·) _A- 1ηKL\! ( _h(· s) \| _h^ref(· s) ) ≤Fh,s(Q¯h(s,⋅))=V¯h(s), ≤ F_h,s( Q_h(s,·))= V_h(s), where the last inequality is the Gibbs variational identity. If Vh+1π¯=V¯h+1V_h+1 π= V_h+1, then Qhπ¯=Q¯hQ_h π= Q_h, and because π¯h π_h is the maximizer in the Gibbs variational identity, Vhπ¯(s)=⟨π¯h(⋅∣s),Q¯h(s,⋅)⟩−1ηKL(π¯h(⋅∣s)∥πhref(⋅∣s))=V¯h(s).V_h π(s)= π_h(· s), Q_h(s,·) _A- 1ηKL\! ( π_h(· s) \| _h^ref(· s) )= V_h(s). Thus V¯h=Vh⋆ V_h=V_h , Q¯h=Qh⋆ Q_h=Q_h , and π¯=π⋆ π=π . The same induction also gives Qhπ≤Qh⋆Q_h^π≤ Q_h for every policy π. For the range, suppose 0≤Vh+1⋆≤Lh+10≤ V_h+1 ≤ L_h+1. Then 0≤Qh⋆(s,a)=rh(s,a)+(ℙhVh+1⋆)(s,a)≤1+Lh+1=Lh.0≤ Q_h (s,a)=r_h(s,a)+(P_hV_h+1 )(s,a)≤ 1+L_h+1=L_h. Since Fh,s(q)F_h,s(q) lies between the minimum and maximum coordinates of q, 0≤Vh⋆(s)=Fh,s(Qh⋆(s,⋅))≤Lh.0≤ V_h (s)=F_h,s(Q_h (s,·))≤ L_h. Backward induction from VH+1⋆=0V_H+1 =0 completes the proof. ∎ Appendix B Supporting Lemmas We first introduce the notation used throughout the statistical analysis. Let Nhk(s,a)N_h^k(s,a) denote the number of visits to (h,s,a)(h,s,a) before episode k, and let kh,n(s,a)k_h,n(s,a) denote the episode index of its n-th visit. For the learning rate αn=H+1H+n _n= H+1H+n used in Algorithm 1, for integers N≥0N≥ 0 and n≥1n≥ 1, define α0N:=∏j=1N(1−αj)=0,N>0,1,N=0,αnN:=αn∏j=n+1N(1−αj),N>n,αn,N=n,0,N<n. _0^N:= cases _j=1^N(1- _j)=0,&N>0,\\ 1,&N=0, cases _n^N:= cases _n _j=n+1^N(1- _j),&N>n,\\ _n,&N=n,\\ 0,&N<n. cases These coefficients and their basic identities are standard in finite-sample analyses of Q-learning; see Jin et al. (2018, Lemma 4.1) and Li et al. (2021b, Lemma 1). Let <k:=σ(τ1,…,τk−1)D_<k:=σ(τ^1,…,τ^k-1). Let ℙ^hk P_h^k be the one-hot row vector satisfying ℙ^hkf=f(sh+1k) P_h^kf=f(s_h+1^k), and regard ℙ^hk P_h^k and ℙh,s,aP_h,s,a as row vectors over S. Under Assumption 2.2, 0≤dhπ⋆(s,a)dhμ(s,a)≤Cη⋆,0≤ d_h^π (s,a)d_h^μ(s,a)≤ C_η , with the convention 0/0=00/0=0, as in Assumption 2.2. Throughout the appendix, we use the convention that empty sums are zero. We record the standard results below. Lemma B.1. For every N≥1N≥ 1 and a∈[1/2,1]a∈[1/2,1], 1Na≤∑n=1NαnNna≤2Na,∑n=1NαnN=1,max1≤n≤NαnN≤2HN, 1N^a≤ _n=1^N _n^Nn^a≤ 2N^a, _n=1^N _n^N=1, _1≤ n≤ N _n^N≤ 2HN, ∑n=1N(αnN)2≤2HN,∑M=n∞αnM=1+1H. _n=1^N( _n^N)^2≤ 2HN, _M=n^∞ _n^M=1+ 1H. We also need the following standard consequence of Freedman’s martingale inequality (Freedman, 1975, Theorem 1.6). Lemma B.2. Let X1,…,XmX_1,…,X_m be martingale differences with respect to a filtration ℱii=0m\F_i\_i=0^m, let |Xi|≤R|X_i|≤ R, and set Wm:=∑i=1m[Xi2∣ℱi−1]W_m:= _i=1^mE[X_i^2 _i-1]. If Wm≤σ2W_m≤σ^2 almost surely for a deterministic σ2σ^2, then, for every u>0u>0, with probability at least 1−2e−u1-2e^-u, |∑i=1mXi|≤cσ2u+cRu. | _i=1^mX_i |≤ c σ^2u+cRu. Lemma B.3. Suppose that, for every k∈[K]k∈[K] and h∈[H]h∈[H], Vh+1kV_h+1^k is <kD_<k-measurable and satisfies 0≤Vh+1k(s)≤Lh+10≤ V_h+1^k(s)≤ L_h+1 for every s∈s . For any δ∈(0,1)δ∈(0,1), let ι:=logSATδ := SATδ. With probability at least 1−δ1-δ, simultaneously for every h∈[H]h∈[H], (s,a)∈×(s,a) ×A, and 1≤N≤NhK+1(s,a)1≤ N≤ N_h^K+1(s,a), |∑n=1NαnN(ℙ^hkh,n(s,a)−ℙh,s,a)Vh+1kh,n(s,a)|≤cLh+1ιHN, | _n=1^N _n^N( P_h^k_h,n(s,a)-P_h,s,a)V_h+1^k_h,n(s,a) |≤ cL_h+1 HN, where c>0c>0 is a universal constant. Proof. If Lh+1=0L_h+1=0, the claim is immediate. Hence suppose Lh+1>0L_h+1>0. Then H≥2H≥ 2, so SAT≥2SAT≥ 2 and ι≥log2 ≥ 2. Fix (h,s,a,N)(h,s,a,N) with 1≤N≤K1≤ N≤ K and define N¯hk(s,a):=Nhk(s,a)+(shk,ahk)=(s,a),ℱk,h−:=σ(<k,s1k,a1k,…,shk,ahk), N_h^k(s,a):=N_h^k(s,a)+1\(s_h^k,a_h^k)=(s,a)\, _k,h^-:=σ(D_<k,s_1^k,a_1^k,…,s_h^k,a_h^k), ℱk,h+:=ℱk,h−∨σ(sh+1k),Xk:=αN¯hk(s,a)N(shk,ahk)=(s,a)(ℙ^hk−ℙh,s,a)Vh+1k. _k,h^+:=F_k,h^- σ(s_h+1^k), X_k:= _ N_h^k(s,a)^N1\(s_h^k,a_h^k)=(s,a)\( P_h^k-P_h,s,a)V_h+1^k. Conditional on ℱk,h−F_k,h^-, every factor in XkX_k except sh+1ks_h+1^k is fixed, and sh+1k∼ℙh(⋅∣shk,ahk)s_h+1^k _h(· s_h^k,a_h^k). Hence [Xk∣ℱk,h−]=0E[X_k _k,h^-]=0. Moreover, ℱk,h−⊆ℱk,h+⊆ℱk+1,h−F_k,h^- _k,h^+ _k+1,h^- for k<Kk<K. Define 0:=ℱ1,h−G_0:=F_1,h^-, k:=ℱk+1,h−G_k:=F_k+1,h^- for 1≤k<K1≤ k<K, and K:=ℱK,h+G_K:=F_K,h^+. Then kk=0K\G_k\_k=0^K is a filtration, XkX_k is kG_k-measurable, and [Xk∣k−1]=[Xk∣ℱk,h−]=0E[X_k _k-1]=E[X_k _k,h^-]=0 for every k∈[K]k∈[K]. At the n-th visit to (s,a)(s,a), N¯hk(s,a)=n N_h^k(s,a)=n. Since αnN=0 _n^N=0 for n>Nn>N, using 0≤Vh+1k≤Lh+10≤ V_h+1^k≤ L_h+1 and Lemma B.1, we have |Xk|≤2HLh+1N|X_k|≤ 2HL_h+1N. Furthermore, ∑k=1K[Xk2∣k−1]=∑k=1K[Xk2∣ℱk,h−] _k=1^KE[X_k^2 _k-1]= _k=1^KE[X_k^2 _k,h^-] ≤Lh+12∑k=1K(αN¯hk(s,a)N)2(shk,ahk)=(s,a) ≤ L_h+1^2 _k=1^K ( _ N_h^k(s,a)^N )^21\(s_h^k,a_h^k)=(s,a)\ ≤Lh+12∑n=1N(αnN)2≤2HLh+12N. ≤ L_h+1^2 _n=1^N( _n^N)^2≤ 2HL_h+1^2N. Hence, for N≥HN≥ H, applying Lemma B.2 with u=2ιu=2 yields, with probability at least 1−2e−2ι1-2e^-2 , |∑k=1KXk| | _k=1^KX_k | ≤cLh+1HιN+cLh+1HιN≤cLh+1ιHN, ≤ cL_h+1 H N+cL_h+1 H N≤ cL_h+1 HN, where the last inequality uses ι≥log2 ≥ 2 and H/N≤H/NH/N≤ H/N, after absorbing numerical factors into the universal constant. Whenever N≤NhK+1(s,a)N≤ N_h^K+1(s,a), by the definition of the visit indices, ∑k=1KXk=∑n=1NαnN(ℙ^hkh,n(s,a)−ℙh,s,a)Vh+1kh,n(s,a). _k=1^KX_k= _n=1^N _n^N( P_h^k_h,n(s,a)-P_h,s,a)V_h+1^k_h,n(s,a). Thus the desired bound holds for N≥HN≥ H. When N<HN<H and N≤NhK+1(s,a)N≤ N_h^K+1(s,a), the same quantity is deterministically bounded by |∑n=1NαnN(ℙ^hkh,n(s,a)−ℙh,s,a)Vh+1kh,n(s,a)|≤Lh+1∑n=1NαnN=Lh+1≤cLh+1ιHN, | _n=1^N _n^N( P_h^k_h,n(s,a)-P_h,s,a)V_h+1^k_h,n(s,a) |≤ L_h+1 _n=1^N _n^N=L_h+1≤ cL_h+1 HN, where we used the weight normalization in Lemma B.1, ι≥log2 ≥ 2, and N<HN<H, after enlarging c if necessary. A union bound over at most HSAK=SATHSAK=SAT choices of (h,s,a,N)(h,s,a,N) has failure probability at most 2SATe−2ι≤δ2SATe^-2 ≤δ, proving the lemma. ∎ Lemma B.4. Suppose SAT>1SAT>1. For any δ∈(0,1)δ∈(0,1), let ι:=logSATδ := SATδ. With probability at least 1−δ1-δ, simultaneously for every h∈[H]h∈[H], (s,a)∈×(s,a) ×A, and m∈[K]m∈[K], dhμ(s,a)Nhm+1(s,a)∨1≤8ιm, d_h^μ(s,a)N_h^m+1(s,a) 1≤ 8 m, (8) and whenever mdhμ(s,a)≥8ιmd_h^μ(s,a)≥ 8 , Nhm+1(s,a)≥mdhμ(s,a)2≥1.N_h^m+1(s,a)≥ md_h^μ(s,a)2≥ 1. (9) Under Assumption 2.2, on the same event, simultaneously for every h∈[H]h∈[H], ∑k=1K∑s,adhπ⋆(s,a)Nhk(s,a)=0≤1+8SACη⋆ι, _k=1^K _s,ad_h^π (s,a)1\N_h^k(s,a)=0\≤ 1+8SAC_η , (10) ∑k=1K∑s,adhπ⋆(s,a)Nhk(s,a)≥1Nhk(s,a)∨1≤8SACη⋆ι(1+logK), _k=1^K _s,ad_h^π (s,a) 1\N_h^k(s,a)≥ 1\N_h^k(s,a) 1≤ 8SAC_η (1+ K), (11) ∑s,adhπ⋆(s,a)NhK+1(s,a)=0≤8SACη⋆ιK, _s,ad_h^π (s,a)1\N_h^K+1(s,a)=0\≤ 8SAC_η K, (12) and ∑s,adhπ⋆(s,a)NhK+1(s,a)≥1NhK+1(s,a)∨1≤8SACη⋆ιK. _s,ad_h^π (s,a) 1\N_h^K+1(s,a)≥ 1\N_h^K+1(s,a) 1≤ 8SAC_η K. (13) Proof. Fix (h,s,a,m)(h,s,a,m). The count Nhm+1(s,a)N_h^m+1(s,a) is binomial with parameters m and dhμ(s,a)d_h^μ(s,a). If mdhμ(s,a)<8ιmd_h^μ(s,a)<8 , then dhμ(s,a)Nhm+1(s,a)∨1≤dhμ(s,a)<8ιm. d_h^μ(s,a)N_h^m+1(s,a) 1≤ d_h^μ(s,a)< 8 m. Otherwise, the multiplicative Chernoff bound gives Pr(Nhm+1(s,a)<mdhμ(s,a)2)≤e−mdhμ(s,a)/8≤e−ι. \! (N_h^m+1(s,a)< md_h^μ(s,a)2 )≤ e^-md_h^μ(s,a)/8≤ e^- . On the complementary event, Nhm+1(s,a)≥mdhμ(s,a)/2≥1N_h^m+1(s,a)≥ md_h^μ(s,a)/2≥ 1, and hence dhμ(s,a)Nhm+1(s,a)∨1≤2m≤8ιm. d_h^μ(s,a)N_h^m+1(s,a) 1≤ 2m≤ 8 m. A union bound over at most HSAK=SATHSAK=SAT choices proves the first two claims of Lemma B.4 simultaneously. To prove (10), observe that (9) with m=k−1m=k-1 implies, for k≥2k≥ 2, Nhk(s,a)=0N_h^k(s,a)=0 implies (k−1)dhμ(s,a)<8ι(k-1)d_h^μ(s,a)<8 . Thus a state-action pair with positive behavior occupancy can have zero count for at most 1+8ι/dhμ(s,a)1+8 /d_h^μ(s,a) episodes. Using Assumption 2.2, ∑k=1K∑s,adhπ⋆(s,a)Nhk(s,a)=0≤∑(s,a):dhμ(s,a)>0dhπ⋆(s,a)(1+8ιdhμ(s,a))≤1+8SACη⋆ι, _k=1^K _s,ad_h^π (s,a)1\N_h^k(s,a)=0\≤ _(s,a):\,d_h^μ(s,a)>0d_h^π (s,a) (1+ 8 d_h^μ(s,a) )≤ 1+8SAC_η , which proves the third claim of Lemma B.4. In the sum on the left-hand side of (11), the k=1k=1 contribution is zero. For k≥2k≥ 2, (8) with m=k−1m=k-1 gives ∑s,adhπ⋆(s,a)Nhk(s,a)≥1Nhk(s,a)∨1 _s,ad_h^π (s,a) 1\N_h^k(s,a)≥ 1\N_h^k(s,a) 1 =∑s,adhπ⋆(s,a)dhμ(s,a)dhμ(s,a)Nhk(s,a)≥1Nhk(s,a)∨1≤8SACη⋆ιk−1. = _s,a d_h^π (s,a)d_h^μ(s,a) d_h^μ(s,a)1\N_h^k(s,a)≥ 1\N_h^k(s,a) 1≤ 8SAC_η k-1. Summing over k and using ∑j=1K−11/j≤1+logK _j=1^K-11/j≤ 1+ K proves the fourth claim of Lemma B.4. Finally, (8) with m=Km=K gives dhμ(s,a)/(NhK+1(s,a)∨1)≤8ι/Kd_h^μ(s,a)/(N_h^K+1(s,a) 1)≤ 8 /K. Hence ∑s,adhπ⋆(s,a)NhK+1(s,a)=0 _s,ad_h^π (s,a)1\N_h^K+1(s,a)=0\ ≤8ιK∑s,adhπ⋆(s,a)dhμ(s,a)≤8SACη⋆ιK, ≤ 8 K _s,a d_h^π (s,a)d_h^μ(s,a)≤ 8SAC_η K, ∑s,adhπ⋆(s,a)NhK+1(s,a)≥1NhK+1(s,a)∨1 _s,ad_h^π (s,a) 1\N_h^K+1(s,a)≥ 1\N_h^K+1(s,a) 1 ≤8ιK∑s,adhπ⋆(s,a)dhμ(s,a)≤8SACη⋆ιK. ≤ 8 K _s,a d_h^π (s,a)d_h^μ(s,a)≤ 8SAC_η K. This proves the final two claims of Lemma B.4. ∎ The following concentration bound is an immediate consequence of Lemma B.6 of Shi et al. (2022), applied with Cd=1C_d=1, Cw=BhC_w=B_h, and Wh+1k(s,a)=Uhk(s,a)W_h+1^k(s,a)=U_h^k(s,a)1, where 1 denotes the all-ones state vector, together with (Uhk(s,a))2≤BhUhk(s,a)(U_h^k(s,a))^2≤ B_hU_h^k(s,a). The logarithmic factors are absorbed into ι . Lemma B.5. Suppose Assumption 2.2 holds. Fix nonnegative <kD_<k-measurable functions Uhk:×→[0,Bh]U_h^k:S×A→[0,B_h]. For any δ∈(0,1)δ∈(0,1), let ι:=logSATδ := SATδ. With probability at least 1−δ1-δ, simultaneously for every h∈[H]h∈[H], |∑k=1Kdhπ⋆(shk,ahk)dhμ(shk,ahk)Uhk(shk,ahk)−∑k=1K∑s,adhπ⋆(s,a)Uhk(s,a)| | _k=1^K d_h^π (s_h^k,a_h^k)d_h^μ(s_h^k,a_h^k)U_h^k(s_h^k,a_h^k)- _k=1^K _s,ad_h^π (s,a)U_h^k(s,a) | ≤cCη⋆Bhι∑k=1K∑s,adhπ⋆(s,a)Uhk(s,a)+cCη⋆Bhι. ≤ c C_η B_h _k=1^K _s,ad_h^π (s,a)U_h^k(s,a)+cC_η B_h . Appendix C Proofs for Algorithm 1 Throughout, constant factors in logarithmic confidence terms are absorbed into universal constants. For notational convenience, we define Δhk(s,a):=Qhk(s,a)−Qh⋆(s,a) _h^k(s,a):=Q_h^k(s,a)-Q_h (s,a). C.1 Lemmas for Theorem 3.1 Lemma C.1. For every k∈[K+1]k∈[K+1], h∈[H]h∈[H], and (s,a)∈×(s,a) ×A, 0≤Qhk(s,a)≤Lh,0≤Vhk(s)≤Lh.0≤ Q_h^k(s,a)≤ L_h, 0≤ V_h^k(s)≤ L_h. Proof. The claim holds at initialization. Suppose it holds before episode k. At a stage-h update, 0≤rhk+Vh+1k(sh+1k)≤1+Lh+1=Lh.0≤ r_h^k+V_h+1^k(s_h+1^k)≤ 1+L_h+1=L_h. Thus the updated Q-value is a convex combination of two values in [0,Lh][0,L_h], while all other Q-values are unchanged. Since Fh,s(q)F_h,s(q) lies between minaq(a) _aq(a) and maxaq(a) _aq(a), the updated value also lies in [0,Lh][0,L_h]. Induction over episodes proves the claim. ∎ Lemma C.2. For every k∈[K+1]k∈[K+1], h∈[H]h∈[H], and s∈s , (Vhk(s)−Vh⋆(s))2≤γhehk(s).(V_h^k(s)-V_h (s))^2≤ _he_h^k(s). (14) Moreover, the output policy in Algorithm 1 satisfies SubOpt(π^)≤η2∑h=1HΓ1:h(s,a)∼dhπ⋆[(QhK+1(s,a)−Qh⋆(s,a))2].SubOpt( π)≤ η2 _h=1^H _1:hE_(s,a) d_h^π [(Q_h^K+1(s,a)-Q_h (s,a))^2 ]. (15) Proof. Fix k∈[K+1]k∈[K+1], h∈[H]h∈[H], and s∈s . By Lemma C.1 and Proposition 2.1, for every a∈a , Qhk(s,a),Qh⋆(s,a)∈[0,Lh],−Lh≤Δhk(s,a)≤Lh.Q_h^k(s,a),Q_h (s,a)∈[0,L_h], -L_h≤ _h^k(s,a)≤ L_h. For t∈[0,1]t∈[0,1], set Qh,tk(s,⋅):=Qh⋆(s,⋅)+tΔhk(s,⋅)Q_h,t^k(s,·):=Q_h (s,·)+t _h^k(s,·). Using the Gibbs formula and πh⋆(⋅∣s)=Gh,s(Qh⋆(s,⋅)) _h (· s)=G_h,s(Q_h (s,·)), for every action in the support of πhref(⋅∣s) _h^ref(· s), Gh,s(Qh,tk(s,⋅))(a) G_h,s(Q_h,t^k(s,·))(a) =πh⋆(a∣s)eηtΔhk(s,a)∑b∈πh⋆(b∣s)eηtΔhk(s,b) = _h (a s)e^η t _h^k(s,a) _b _h (b s)e^η t _h^k(s,b) ≤πh⋆(a∣s)e2ηtLh≤γhπh⋆(a∣s). ≤ _h (a s)e^2η tL_h≤ _h _h (a s). (16) The same inequality is trivial outside the support, where both probabilities are zero. Since ∇Fh,s=Gh,s∇ F_h,s=G_h,s, the fundamental theorem of calculus gives (Vhk(s)−Vh⋆(s))2 (V_h^k(s)-V_h (s))^2 =(∫01⟨Gh,s(Qh,tk(s,⋅)),Δhk(s,⋅)⟩t)2 = ( _0^1 G_h,s(Q_h,t^k(s,·)), _h^k(s,·) _A\,dt )^2 ≤∫01∑a∈Gh,s(Qh,tk(s,⋅))(a)(Δhk(s,a))2t ≤ _0^1 _a G_h,s(Q_h,t^k(s,·))(a)( _h^k(s,a))^2\,dt ≤γh∑a∈πh⋆(a∣s)(Δhk(s,a))2=γhehk(s), ≤ _h _a _h (a s)( _h^k(s,a))^2= _he_h^k(s), where the first inequality follows from Jensen’s inequality, applied first to the integral and then to the action distribution, and the second follows from (16). This proves the first claim of Lemma C.2. We next bound the KL divergence between the corresponding Gibbs policies. Define ϕ(t):=log∑b∈πhref(b∣s)eηQh,1−tk(s,b),t∈[0,1].φ(t):= _b _h^ref(b s)e^η Q_h,1-t^k(s,b), t∈[0,1]. The Gibbs formulas imply KL(Gh,s(Qhk(s,⋅))∥πh⋆(⋅∣s))=ϕ(1)−ϕ(0)−ϕ′(0),KL\! (G_h,s(Q_h^k(s,·)) \| _h (· s) )=φ(1)-φ(0)-φ (0), and differentiating ϕ(t)φ(t) twice yields ϕ′(t)=η2Vara∼Gh,s(Qh,1−tk(s,⋅))(Δhk(s,a)).φ (t)=η^2Var_a G_h,s(Q_h,1-t^k(s,·))( _h^k(s,a)). Therefore, Taylor’s theorem with integral remainder, together with Var(X)≤[X2]Var(X) [X^2] and (16), yields KL(Gh,s(Qhk(s,⋅))∥πh⋆(⋅∣s)) \! (G_h,s(Q_h^k(s,·)) \| _h (· s) ) =η2∫01(1−t)Vara∼Gh,s(Qh,1−tk(s,⋅))(Δhk(s,a))t =η^2 _0^1(1-t)Var_a G_h,s(Q_h,1-t^k(s,·))( _h^k(s,a))\,dt ≤η2γh∫01(1−t)t∑a∈πh⋆(a∣s)(Δhk(s,a))2=η2γh2ehk(s). ≤η^2 _h _0^1(1-t)\,dt _a _h (a s)( _h^k(s,a))^2= η^2 _h2e_h^k(s). (17) We now turn to the output policy. Taking k=K+1k=K+1 and t=1t=1 in (16) gives π^h(a∣s)≤γhπh⋆(a∣s) π_h(a s)≤ _h _h (a s). Since d1π^=d1π⋆=ρd_1 π=d_1^π =ρ, induction over h gives dh+1π^(s′) d_h+1 π(s ) =∑s,adhπ^(s)π^h(a∣s)ℙh(s′∣s,a) = _s,ad_h π(s) π_h(a s)P_h(s s,a) ≤Γ1:h−1γh∑s,adhπ⋆(s)πh⋆(a∣s)ℙh(s′∣s,a)=Γ1:hdh+1π⋆(s′). ≤ _1:h-1 _h _s,ad_h^π (s) _h (a s)P_h(s s,a)= _1:hd_h+1^π (s ). (18) Thus dhπ^(s)≤Γ1:h−1dhπ⋆(s)d_h π(s)≤ _1:h-1d_h^π (s) for every h and s. It remains to convert the pointwise KL bound into policy suboptimality. For any policy π with finite regularized value, the Gibbs formula for π⋆π gives logπh⋆(a∣s)πhref(a∣s)=η(Qh⋆(s,a)−Vh⋆(s)) _h (a s) _h^ref(a s)=η(Q_h (s,a)-V_h (s)) on the common support. Combining this identity with Bellman consistency yields Vh⋆(s)−Vhπ(s)=1ηKL(πh(⋅∣s)∥πh⋆(⋅∣s))+∑aπh(a∣s)(ℙh(Vh+1⋆−Vh+1π))(s,a).V_h (s)-V_h^π(s)= 1ηKL\! ( _h(· s) \| _h (· s) )+ _a _h(a s)(P_h(V_h+1 -V_h+1^π))(s,a). Taking expectation with respect to s∼dhπs d_h^π and summing over h, the next-stage value terms telescope, yielding Jη(π⋆)−Jη(π)=1η∑h=1Hs∼dhπ[KL(πh(⋅∣s)∥πh⋆(⋅∣s))].J_η(π )-J_η(π)= 1η _h=1^HE_s d_h^π [KL\! ( _h(· s) \| _h (· s) ) ]. Taking π=π^π= π, using (17) and (18), and then expanding ehK+1e_h^K+1 gives SubOpt(π^) ( π) ≤η2∑h=1Hγh∑sdhπ^(s)ehK+1(s) ≤ η2 _h=1^H _h _sd_h π(s)e_h^K+1(s) ≤η2∑h=1HΓ1:h∑sdhπ⋆(s)ehK+1(s) ≤ η2 _h=1^H _1:h _sd_h^π (s)e_h^K+1(s) =η2∑h=1HΓ1:h(s,a)∼dhπ⋆[(QhK+1(s,a)−Qh⋆(s,a))2], = η2 _h=1^H _1:hE_(s,a) d_h^π [(Q_h^K+1(s,a)-Q_h (s,a))^2 ], which proves the second claim of Lemma C.2. ∎ We next combine Lemma B.3 with the KL value-error bound in Lemma C.2 to derive a pointwise recursion for the squared Q-estimation error. This recursion will be used to control both the cumulative squared error and the error of the final iterate. Lemma C.3. For any δ∈(0,1)δ∈(0,1), let ι:=logSATδ := SATδ. With probability at least 1−δ1-δ, simultaneously for every k∈[K+1]k∈[K+1], h∈[H]h∈[H], and (s,a)∈×(s,a) ×A, (Δhk(s,a))2≤ ( _h^k(s,a))^2≤ Lh2Nhk(s,a)=0+c0H2Lh+12ι2Nhk(s,a)≥1Nhk(s,a)∨1 L_h^21\N_h^k(s,a)=0\+c_0H^2L_h+1^2 ^2 1\N_h^k(s,a)≥ 1\N_h^k(s,a) 1 (19) +(1+1H)γh+1∑n=1Nhk(s,a)αnNhk(s,a)(ℙheh+1kh,n(s,a))(s,a), + (1+ 1H ) _h+1 _n=1^N_h^k(s,a) _n^N_h^k(s,a)(P_he_h+1^k_h,n(s,a))(s,a), where c0>0c_0>0 is a universal constant. Proof. By Lemma C.1, Vh+1kV_h+1^k satisfies 0≤Vh+1k≤Lh+10≤ V_h+1^k≤ L_h+1, and by the update order of Algorithm 1, Vh+1kV_h+1^k is <kD_<k-measurable. Hence Lemma B.3 applies. Work on its event of probability at least 1−δ1-δ. Fix (k,h,s,a)(k,h,s,a), write N:=Nhk(s,a)N:=N_h^k(s,a), and suppress the dependence of kh,nk_h,n on (s,a)(s,a). If N=0N=0, then Qhk(s,a)=0Q_h^k(s,a)=0 and (Δhk(s,a))2≤Lh2( _h^k(s,a))^2≤ L_h^2 by (3). Suppose N≥1N≥ 1. Unrolling the Q-learning update and subtracting the optimal Bellman equation with the same coefficients αnN _n^N gives Δhk(s,a)=∑n=1NαnN(ℙ^hkh,n−ℙh,s,a)Vh+1kh,n+∑n=1NαnNℙh,s,a(Vh+1kh,n−Vh+1⋆), _h^k(s,a)= _n=1^N _n^N( P_h^k_h,n-P_h,s,a)V_h+1^k_h,n+ _n=1^N _n^NP_h,s,a(V_h+1^k_h,n-V_h+1 ), since α0N=0 _0^N=0. Applying (x+y)2≤(H+1)x2+(1+1/H)y2(x+y)^2≤(H+1)x^2+(1+1/H)y^2 and Lemma B.3 yields (Δhk(s,a))2 ( _h^k(s,a))^2 ≤c0H2Lh+12ι2N+(1+1H)(∑n=1NαnNℙh,s,a(Vh+1kh,n−Vh+1⋆))2 ≤ c_0H^2L_h+1^2 ^2N+ (1+ 1H ) ( _n=1^N _n^NP_h,s,a(V_h+1^k_h,n-V_h+1 ) )^2 ≤c0H2Lh+12ι2N+(1+1H)∑n=1NαnNℙh,s,a[(Vh+1kh,n−Vh+1⋆)2] ≤ c_0H^2L_h+1^2 ^2N+ (1+ 1H ) _n=1^N _n^NP_h,s,a\! [(V_h+1^k_h,n-V_h+1 )^2 ] ≤c0H2Lh+12ι2N+(1+1H)γh+1∑n=1NαnN(ℙheh+1kh,n)(s,a). ≤ c_0H^2L_h+1^2 ^2N+ (1+ 1H ) _h+1 _n=1^N _n^N(P_he_h+1^k_h,n)(s,a). The second inequality follows from Jensen’s inequality, first with respect to the weights αnN\ _n^N\ and then with respect to ℙh(⋅∣s,a)P_h(· s,a), the last follows from (14) at stage h+1h+1. Together with the zero-count case, this proves Lemma C.3. ∎ Lemma C.4. Suppose Assumption 2.2 holds and SAT>1SAT>1. For any δ∈(0,1)δ∈(0,1), let ι:=logSATδ := SATδ. Then, with probability at least 1−δ1-δ, simultaneously for every h∈[H]h∈[H], ∑k=1K∑sdhπ⋆(s)ehk(s)≤ _k=1^K _sd_h^π (s)e_h^k(s)≤ (1+5H)γh+1∑k=1K∑sdh+1π⋆(s)eh+1k(s) (1+ 5H ) _h+1 _k=1^K _sd_h+1^π (s)e_h+1^k(s) (20) +c0SACη⋆γh+1H2Lh2ι3(1+logK). +c_0SAC_η _h+1H^2L_h^2 ^3(1+ K). Consequently, ∑k=1K(s,a)∼dhπ⋆[(Qhk(s,a)−Qh⋆(s,a))2]≤c1SACη⋆Γh+1:H2Lh3ι3(1+logK), _k=1^KE_(s,a) d_h^π [(Q_h^k(s,a)-Q_h (s,a))^2 ]≤ c_1SAC_η _h+1:HH^2L_h^3 ^3(1+ K), (21) where c0,c1>0c_0,c_1>0 are universal constants. Proof. Invoke Lemmas C.3 and B.4 with failure probability δ/4δ/4 each, and invoke Lemma B.5 twice with failure probability δ/4δ/4, first with Uhk(s,a):=∑n=1Nhk(s,a)αnNhk(s,a)(ℙheh+1kh,n(s,a))(s,a),U_h^k(s,a):= _n=1^N_h^k(s,a) _n^N_h^k(s,a)(P_he_h+1^k_h,n(s,a))(s,a), (22) and then with Uhk(s,a):=(ℙheh+1k)(s,a).U_h^k(s,a):=(P_he_h+1^k)(s,a). (23) In both applications take Bh=Lh+12B_h=L_h+1^2. By Lemma C.1 and Proposition 2.1, 0≤eh+1k(s)≤Lh+120≤ e_h+1^k(s)≤ L_h+1^2. Moreover, by the update order in Algorithm 1, QkQ^k, and hence eke^k, are <kD_<k-measurable. Since kh,n(s,a)<k_h,n(s,a)<k for every 1≤n≤Nhk(s,a)1≤ n≤ N_h^k(s,a), the historical test function in (22) is also <kD_<k-measurable. Thus both choices satisfy the hypotheses of Lemma B.5. By a union bound, all four events hold simultaneously with probability at least 1−δ1-δ. Summing (19) over k∈[K]k∈[K] and averaging with respect to dhπ⋆d_h^π gives ∑k=1K∑sdhπ⋆(s)ehk(s) _k=1^K _sd_h^π (s)e_h^k(s) ≤Lh2∑k=1K∑s,adhπ⋆(s,a)Nhk(s,a)=0 ≤ L_h^2 _k=1^K _s,ad_h^π (s,a)1\N_h^k(s,a)=0\ +c0H2Lh+12ι2∑k=1K∑s,adhπ⋆(s,a)Nhk(s,a)≥1Nhk(s,a)∨1 +c_0H^2L_h+1^2 ^2 _k=1^K _s,ad_h^π (s,a) 1\N_h^k(s,a)≥ 1\N_h^k(s,a) 1 +(1+1H)γh+1∑k=1K∑s,adhπ⋆(s,a)∑n=1Nhk(s,a)αnNhk(s,a)(ℙheh+1kh,n(s,a))(s,a)⏟(I). + (1+ 1H ) _h+1 _k=1^K _s,ad_h^π (s,a) _n=1^N_h^k(s,a) _n^N_h^k(s,a)(P_he_h+1^k_h,n(s,a))(s,a)_(I). (24) By (10) and (11), we have Lh2∑k=1K∑s,adhπ⋆(s,a)Nhk(s,a)=0+c0H2Lh+12ι2∑k=1K∑s,adhπ⋆(s,a)Nhk(s,a)≥1Nhk(s,a)∨1 L_h^2 _k=1^K _s,ad_h^π (s,a)1\N_h^k(s,a)=0\+c_0H^2L_h+1^2 ^2 _k=1^K _s,ad_h^π (s,a) 1\N_h^k(s,a)≥ 1\N_h^k(s,a) 1 ≤cSACη⋆H2Lh2ι3(1+logK). ≤ cSAC_η H^2L_h^2 ^3(1+ K). (25) It remains to bound (I)(I). Applying Lemma B.5 with the test function in (22) gives (I) (I) ≤∑k=1Kdhπ⋆(shk,ahk)dhμ(shk,ahk)∑n=1Nhk(shk,ahk)αnNhk(shk,ahk)(ℙheh+1kh,n(shk,ahk))(shk,ahk)⏟(I)+cCη⋆Lh+12ι(I)+cCη⋆Lh+12ι ≤ _k=1^K d_h^π (s_h^k,a_h^k)d_h^μ(s_h^k,a_h^k)\! _n=1^N_h^k(s_h^k,a_h^k)\! _n^N_h^k(s_h^k,a_h^k)(P_he_h+1^k_h,n(s_h^k,a_h^k))(s_h^k,a_h^k)_(I)+c C_η L_h+1^2 \ \!(I)\!+\!cC_η L_h+1^2 ≤(i)(1+18H)(I)+cCη⋆HLh+12ι. (i)≤ (1+ 18H )(I)+cC_η HL_h+1^2 . (26) Here (i) uses cxy≤x16H+4c2Hyc xy≤ x16H+4c^2Hy with x=(I)x=(I) and y=Cη⋆Lh+12ιy=C_η L_h+1^2 . After moving x/(16H)x/(16H) to the left, we use (1−1/(16H))−1≤1+1/(8H)(1-1/(16H))^-1≤ 1+1/(8H) and absorb numerical factors into the universal constant. We next reindex (I)(I). For each state-action pair (s,a)(s,a), the m-th visit occurs in episode kh,m(s,a)k_h,m(s,a) and satisfies Nhkh,m(s,a)(s,a)=m−1N_h^k_h,m(s,a)(s,a)=m-1. Hence (I) (I) =∑s,adhπ⋆(s,a)dhμ(s,a)∑m=1NhK+1(s,a)∑n=1m−1αnm−1(ℙheh+1kh,n(s,a))(s,a) = _s,a d_h^π (s,a)d_h^μ(s,a) _m=1^N_h^K+1(s,a) _n=1^m-1 _n^m-1(P_he_h+1^k_h,n(s,a))(s,a) =∑s,adhπ⋆(s,a)dhμ(s,a)∑n=1NhK+1(s,a)−1(∑m=n+1NhK+1(s,a)αnm−1)(ℙheh+1kh,n(s,a))(s,a) = _s,a d_h^π (s,a)d_h^μ(s,a) _n=1^N_h^K+1(s,a)-1 ( _m=n+1^N_h^K+1(s,a) _n^m-1 )(P_he_h+1^k_h,n(s,a))(s,a) ≤(1+1H)∑s,adhπ⋆(s,a)dhμ(s,a)∑n=1NhK+1(s,a)(ℙheh+1kh,n(s,a))(s,a) ≤ (1+ 1H ) _s,a d_h^π (s,a)d_h^μ(s,a) _n=1^N_h^K+1(s,a)(P_he_h+1^k_h,n(s,a))(s,a) =(1+1H)∑k=1Kdhπ⋆(shk,ahk)dhμ(shk,ahk)(ℙheh+1k)(shk,ahk)⏟(I). = (1+ 1H ) _k=1^K d_h^π (s_h^k,a_h^k)d_h^μ(s_h^k,a_h^k)(P_he_h+1^k)(s_h^k,a_h^k)_(I). (27) The inequality in (27) uses ∑m=n+1NhK+1(s,a)αnm−1≤∑M=n∞αnM=1+1H, _m=n+1^N_h^K+1(s,a) _n^m-1≤ _M=n^∞ _n^M=1+ 1H, and adds the nonnegative term corresponding to n=NhK+1(s,a)n=N_h^K+1(s,a). It remains to control (I)(I). Applying Lemma B.5 with (23) and the occupancy recursion under π⋆π gives (I) (I) ≤∑k=1K∑s,adhπ⋆(s,a)(ℙheh+1k)(s,a)+cCη⋆Lh+12ι∑k=1K∑s,adhπ⋆(s,a)(ℙheh+1k)(s,a)+cCη⋆Lh+12ι ≤\! _k=1^K\! _s,ad_h^π \!(s,a)(P_he_h+1^k)(s,a)\!+\!c\! C_η L_h+1^2 \! _k=1^K\! _s,ad_h^π \!(s,a)(P_he_h+1^k)(s,a)\!+\!cC_η L_h+1^2 =∑k=1K∑sdh+1π⋆(s)eh+1k(s)+cCη⋆Lh+12ι∑k=1K∑sdh+1π⋆(s)eh+1k(s)+cCη⋆Lh+12ι = _k=1^K _sd_h+1^π (s)e_h+1^k(s)+c C_η L_h+1^2 _k=1^K _sd_h+1^π (s)e_h+1^k(s)\!+\!cC_η L_h+1^2 ≤(ii)(1+116H)∑k=1K∑sdh+1π⋆(s)eh+1k(s)+cCη⋆HLh+12ι. (i)≤ (1+ 116H ) _k=1^K _sd_h+1^π (s)e_h+1^k(s)+cC_η HL_h+1^2 . (28) Here (i) uses cxy≤x16H+4c2Hy,c xy≤ x16H+4c^2Hy, with x=∑k=1K∑sdh+1π⋆(s)eh+1k(s),y=Cη⋆Lh+12ι.x= _k=1^K _sd_h+1^π (s)e_h+1^k(s), y=C_η L_h+1^2 . Combining (26), (27), and (28) gives (I) (I) ≤(1+18H)(1+1H)(1+116H)∑k=1K∑sdh+1π⋆(s)eh+1k(s)+cCη⋆HLh+12ι ≤ (1+ 18H ) (1+ 1H ) (1+ 116H ) _k=1^K _sd_h+1^π (s)e_h+1^k(s)+cC_η HL_h+1^2 ≤(1+2H)∑k=1K∑sdh+1π⋆(s)eh+1k(s)+cCη⋆HLh+12ι. ≤ (1+ 2H ) _k=1^K _sd_h+1^π (s)e_h+1^k(s)+cC_η HL_h+1^2 . (29) Combining (24), (25), and (29) yields ∑k=1K∑sdhπ⋆(s)ehk(s) _k=1^K _sd_h^π (s)e_h^k(s) ≤cSACη⋆H2Lh2ι3(1+logK)+ ≤ cSAC_η H^2L_h^2 ^3(1+ K)+ (1+1H)γh+1[(1+2H)∑k=1K∑sdh+1π⋆(s)eh+1k(s)+cCη⋆HLh+12ι] (1+ 1H ) _h+1 [ (1+ 2H ) _k=1^K _sd_h+1^π (s)e_h+1^k(s)+cC_η HL_h+1^2 ] ≤(1+5H)γh+1∑k=1K∑sdh+1π⋆(s)eh+1k(s) ≤ (1+ 5H ) _h+1 _k=1^K _sd_h+1^π (s)e_h+1^k(s) +c0SACη⋆γh+1H2Lh2ι3(1+logK). +c_0SAC_η _h+1H^2L_h^2 ^3(1+ K). Here we used (1+1H)(1+2H)=1+3H+2H2≤1+5H, (1+ 1H ) (1+ 2H )=1+ 3H+ 2H^2≤ 1+ 5H, together with γh+1≥1 _h+1≥ 1, Lh+1≤LhL_h+1≤ L_h, SA≥1SA≥ 1, H≥1H≥ 1, ι≥log2 ≥ 2, and 1+logK≥11+ K≥ 1, absorbing lower-order terms into the universal constant. This proves the first claim of Lemma C.4. Iterating (20) backward, with the stage-H+1H+1 term equal to zero, gives ∑k=1K∑sdhπ⋆(s)ehk(s) _k=1^K _sd_h^π (s)e_h^k(s) ≤c0SACη⋆H2ι3(1+logK)∑t=hH(1+5H)t−h(∏j=h+1t+1γj)Lt2 ≤ c_0SAC_η H^2 ^3(1+ K) _t=h^H (1+ 5H )^t-h ( _j=h+1^t+1 _j )L_t^2 ≤cSACη⋆Γh+1:H2ι3(1+logK)∑t=hHLt2 ≤ cSAC_η _h+1:HH^2 ^3(1+ K) _t=h^HL_t^2 ≤c1SACη⋆Γh+1:H2Lh3ι3(1+logK), ≤ c_1SAC_η _h+1:HH^2L_h^3 ^3(1+ K), where we used (1+5H)t−h≤(1+5H)H≤e5,∏j=h+1t+1γj≤∏j=h+1Hγj=Γh+1:H, (1+ 5H )^t-h≤ (1+ 5H )^H≤ e^5, _j=h+1^t+1 _j≤ _j=h+1^H _j= _h+1:H, and ∑t=hHLt2=∑ℓ=1Lhℓ2≤Lh3. _t=h^HL_t^2= _ =1^L_h ^2≤ L_h^3. By the definition of ehke_h^k, this proves the second claim of Lemma C.4. ∎ Lemma C.5. Suppose Assumption 2.2 holds. For any δ∈(0,1)δ∈(0,1), let ι:=logSATδ := SATδ. Then, with probability at least 1−δ1-δ, simultaneously for every h∈[H]h∈[H], (s,a)∼dhπ⋆[(QhK+1(s,a)−Qh⋆(s,a))2]≤c0SACη⋆γh+1H2Lh2ι3K _(s,a) d_h^π [(Q_h^K+1(s,a)-Q_h (s,a))^2 ]≤ c_0SAC_η _h+1H^2L_h^2 ^3K (30) +c0Hιγh+1K∑k=1Ks∼dh+1π⋆[eh+1k(s)], + c_0H _h+1K _k=1^KE_s d_h+1^π [e_h+1^k(s) ], where c0>0c_0>0 is a universal constant, and the sum on the right is zero when h=Hh=H. Proof. If SAT=1SAT=1, the single Q-update is exact, so the left-hand side is zero. Hence suppose SAT>1SAT>1. Invoke Lemmas C.3, B.4, and B.5 with failure probability δ/3δ/3 each, for Lemma B.5, take Uhk(s,a)=(ℙheh+1k)(s,a)U_h^k(s,a)=(P_he_h+1^k)(s,a) and Bh=Lh+12B_h=L_h+1^2. The range bounds ensure 0≤Uhk(s,a)≤Lh+120≤ U_h^k(s,a)≤ L_h+1^2, and UhkU_h^k is <kD_<k-measurable. By a union bound, all three events hold simultaneously with probability at least 1−δ1-δ. Fix h∈[H]h∈[H]. For every state-action pair with dhπ⋆(s,a)>0d_h^π (s,a)>0 and NhK+1(s,a)≥1N_h^K+1(s,a)≥ 1, Assumption 2.2 gives dhμ(s,a)>0d_h^μ(s,a)>0, and Lemma B.1 together with (8) at m=Km=K and log(3SAT/δ)≤3ι (3SAT/δ)≤ 3 gives maxnαnNhK+1(s,a)≤2HNhK+1(s,a)≤48HιKdhμ(s,a). _n _n^N_h^K+1(s,a)≤ 2HN_h^K+1(s,a)≤ 48H Kd_h^μ(s,a). (31) Averaging (19) at k=K+1k=K+1 with respect to dhπ⋆d_h^π and using (12)–(13), we obtain (s,a)∼dhπ⋆[(QhK+1(s,a)−Qh⋆(s,a))2] _(s,a) d_h^π [(Q_h^K+1(s,a)-Q_h (s,a))^2 ] ≤cSACη⋆H2Lh2ι3K+(1+1H)γh+1∑s,adhπ⋆(s,a)∑n=1NhK+1(s,a)αnNhK+1(s,a)(ℙheh+1kh,n(s,a))(s,a) ≤ cSAC_η H^2L_h^2 ^3K+ (1+ 1H ) _h+1 _s,ad_h^π (s,a) _n=1^N_h^K+1(s,a) _n^N_h^K+1(s,a)(P_he_h+1^k_h,n(s,a))(s,a) ≤(i)cSACη⋆H2Lh2ι3K+48HιK(1+1H)γh+1∑k=1Kdhπ⋆(shk,ahk)dhμ(shk,ahk)(ℙheh+1k)(shk,ahk)⏟(I). (i)≤ cSAC_η H^2L_h^2 ^3K+ 48H K (1+ 1H ) _h+1 _k=1^K d_h^π (s_h^k,a_h^k)d_h^μ(s_h^k,a_h^k)(P_he_h+1^k)(s_h^k,a_h^k)_(I). (32) Here (i) follows from (31) after reindexing the pairs ((s,a),n)((s,a),n) by their visit episodes kh,n(s,a)k_h,n(s,a), the factor dhπ⋆(s,a)/dhμ(s,a)d_h^π (s,a)/d_h^μ(s,a) then yields (I)(I). We next control (I)(I). Applying Lemma B.5 with Uhk(s,a)=(ℙheh+1k)(s,a)U_h^k(s,a)=(P_he_h+1^k)(s,a) and Bh=Lh+12B_h=L_h+1^2, and then using the occupancy recursion under π⋆π , (I) (I) ≤∑k=1K∑s,adhπ⋆(s,a)(ℙheh+1k)(s,a)+cCη⋆Lh+12ι∑k=1K∑s,adhπ⋆(s,a)(ℙheh+1k)(s,a)+cCη⋆Lh+12ι ≤ _k=1^K _s,ad_h^π \!(s,a)(P_he_h+1^k)(s,a)\!+\!c C_η L_h+1^2 \! _k=1^K _s,ad_h^π (s,a)(P_he_h+1^k)(s,a)\!+\!cC_η L_h+1^2 (33) =∑k=1K∑sdh+1π⋆(s)eh+1k(s)+cCη⋆Lh+12ι∑k=1K∑sdh+1π⋆(s)eh+1k(s)+cCη⋆Lh+12ι = _k=1^K _sd_h+1^π (s)e_h+1^k(s)+c C_η L_h+1^2 _k=1^K _sd_h+1^π (s)e_h+1^k(s)+cC_η L_h+1^2 ≤(ii)c∑k=1K∑sdh+1π⋆(s)eh+1k(s)+cCη⋆Lh+12ι. (i)≤c _k=1^K _sd_h+1^π (s)e_h+1^k(s)+cC_η L_h+1^2 . (34) Here (i) uses xy≤(x+y)/2 xy≤(x+y)/2 with x=∑k=1K∑sdh+1π⋆(s)eh+1k(s),y=Cη⋆Lh+12ι,x= _k=1^K _sd_h+1^π (s)e_h+1^k(s), y=C_η L_h+1^2 , after adjusting the universal constant c. Combining (32) and (34) gives (s,a)∼dhπ⋆[(QhK+1(s,a)−Qh⋆(s,a))2] _(s,a) d_h^π [(Q_h^K+1(s,a)-Q_h (s,a))^2 ] ≤cSACη⋆H2Lh2ι3K+cHιγh+1K∑k=1K∑sdh+1π⋆(s)eh+1k(s)+cCη⋆γh+1HLh+12ι2K ≤ cSAC_η H^2L_h^2 ^3K+ cH _h+1K _k=1^K _sd_h+1^π (s)e_h+1^k(s)+ cC_η _h+1HL_h+1^2 ^2K ≤c0SACη⋆γh+1H2Lh2ι3K+c0Hιγh+1K∑k=1Ks∼dh+1π⋆[eh+1k(s)]. ≤ c_0SAC_η _h+1H^2L_h^2 ^3K+ c_0H _h+1K _k=1^KE_s d_h+1^π [e_h+1^k(s) ]. Here we used Lh+1≤LhL_h+1≤ L_h, SA≥1SA≥ 1, ι≥log2 ≥ 2, γh+1≥1 _h+1≥ 1, and the definition of eh+1ke_h+1^k. This proves Lemma C.5. When h=Hh=H, the stage-H+1H+1 terms are zero. ∎ C.2 Proof of Theorem 3.1 Proof. If SAT=1SAT=1, the output is the unique policy, so SubOpt(π^)=0SubOpt( π)=0. Hence suppose SAT>1SAT>1. Apply Lemmas C.5 and C.4 with failure probability δ/2δ/2 each. With probability at least 1−δ1-δ, for every h∈[H]h∈[H], (s,a)∼dhπ⋆[(QhK+1(s,a)−Qh⋆(s,a))2] _(s,a) d_h^π \! [(Q_h^K+1(s,a)\!-\!Q_h (s,a))^2 ] ≤cSACη⋆γh+1H2Lh2ι3K+cHιγh+1K∑k=1K∑sdh+1π⋆(s)eh+1k(s) ≤\! cSAC_η _h+1H^2L_h^2 ^3K\!+\! cH _h+1K\! _k=1^K\! _s\!d_h+1^π (s)e_h+1^k(s) ≤cSACη⋆KΓh+1:H3Lh3ι4(1+logK), ≤ c SAC_η K _h+1:HH^3L_h^3 ^4(1+ K), where the second inequality uses (21) at stage h+1h+1, when h=Hh=H, eH+1k≡0e_H+1^k≡ 0. Substituting this estimate into (15) gives SubOpt(π^) ( π) ≤cηSACη⋆H3ι4(1+logK)K∑h=1HΓ1:hΓh+1:HLh3 ≤ c η SAC_η H^3 ^4(1+ K)K _h=1^H _1:h _h+1:HL_h^3 =cηeηH(H+1)SACη⋆H3ι4(1+logK)K∑h=1HLh3 =c η e^η H(H+1)SAC_η H^3 ^4(1+ K)K _h=1^HL_h^3 ≤cηeηH(H+1)H7SACη⋆Kι4(1+logK). ≤ c η e^η H(H+1)H^7SAC_η K ^4(1+ K). Here Γ1:hΓh+1:H=Γ1:H=eηH(H+1) _1:h _h+1:H= _1:H=e^η H(H+1) and ∑h=1HLh3=(H(H+1)/2)2≤H4 _h=1^HL_h^3=(H(H+1)/2)^2≤ H^4. This proves Theorem 3.1. ∎ Appendix D Proofs for Algorithm 2 Throughout this appendix, fix the confidence level δ∈(0,1)δ∈(0,1) used in Algorithm 2 and let ι:=logSATδ := SATδ. All iterate-dependent quantities refer to this fixed run of KLPQ. We use the shorthand Δhk(s,a):=Qhk(s,a)−Qh⋆(s,a) _h^k(s,a):=Q_h^k(s,a)-Q_h (s,a), where QhkQ_h^k now denotes the KLPQ iterates, and retain the definition of ehke_h^k from Section 5.1. We also retain <kD_<k and ℙ^hk P_h^k from Appendix B. Constant-factor changes in concentration thresholds are absorbed into universal constants, throughout, the algorithm is run with the original confidence level. D.1 Lemmas for Theorem 4.1 Lemma D.1. For every k∈[K+1]k∈[K+1], h∈[H]h∈[H], and (s,a)∈×(s,a) ×A, Q~hk(s,a)≤Lh,0≤Qhk(s,a)≤Lh,0≤Vhk(s)≤Lh. Q_h^k(s,a)≤ L_h, 0≤ Q_h^k(s,a)≤ L_h, 0≤ V_h^k(s)≤ L_h. (35) Moreover, Qhk+1≥QhkQ_h^k+1≥ Q_h^k and Vhk+1≥VhkV_h^k+1≥ V_h^k coordinatewise for every k∈[K]k∈[K] and h∈[H]h∈[H], and Qhk(s,a)=max1≤j≤kQ~hj(s,a),Vhk(s)=Fh,s(Qhk(s,⋅)).Q_h^k(s,a)= _1≤ j≤ k Q_h^j(s,a), V_h^k(s)=F_h,s(Q_h^k(s,·)). Proof. We prove the stated properties by induction over episodes. For the base case k=1k=1, all claims follow directly from the initialization, and Vh1(s)=Fh,s(Qh1(s,⋅))V_h^1(s)=F_h,s(Q_h^1(s,·)) for every (h,s)∈[H]×(h,s)∈[H]×S. For the induction hypothesis, suppose that the range bounds in (35), the invariant Vhk(s)=Fh,s(Qhk(s,⋅))V_h^k(s)=F_h,s(Q_h^k(s,·)), and the identity Qhk(s,a)=max1≤j≤kQ~hj(s,a)Q_h^k(s,a)= _1≤ j≤ k Q_h^j(s,a) hold at the beginning of episode k. For the induction step from k to k+1k+1, the algorithm carries QhkQ_h^k, VhkV_h^k, and Q~hk Q_h^k forward except at the visited coordinates. At a stage-h update, rhk+Vh+1k(sh+1k)−bh,n≤1+Lh+1=Lhr_h^k+V_h+1^k(s_h+1^k)-b_h,n≤ 1+L_h+1=L_h. Hence the update of Q~h Q_h remains at most LhL_h. The max update in Line 13 therefore ensures that Qhk+1Q_h^k+1 remains in [0,Lh][0,L_h], preserves coordinatewise monotonicity, and yields Qhk+1(s,a)=max1≤j≤k+1Q~hj(s,a)Q_h^k+1(s,a)= _1≤ j≤ k+1 Q_h^j(s,a). Since Fh,sF_h,s is coordinatewise nondecreasing and lies between the minimum and maximum coordinates of its argument, the recomputed value also lies in [0,Lh][0,L_h] and satisfies Vhk+1≥VhkV_h^k+1≥ V_h^k coordinatewise. The invariant Vhk+1(s)=Fh,s(Qhk+1(s,⋅))V_h^k+1(s)=F_h,s(Q_h^k+1(s,·)) is preserved because the algorithm carries QhkQ_h^k and VhkV_h^k forward together and recomputes the value at every updated state. This completes the induction over k. ∎ We now introduce a concentration event for later use. Notably, QkQ^k and VkV^k before episode k depend only on τ1,…,τk−1τ^1,…,τ^k-1, so QhkQ_h^k, VhkV_h^k, and ehke_h^k are <kD_<k-measurable. The deterministic bounds (35) and (3) give 0≤ehk(s)≤Lh2,0≤(ℙheh+1k)(s,a)≤Lh+12, 0≤ e_h^k(s)≤ L_h^2, 0≤(P_he_h+1^k)(s,a)≤ L_h+1^2, 0≤∑n=1Nhk(s,a)αnNhk(s,a)(ℙheh+1kh,n(s,a))(s,a)≤Lh+12. 0≤ _n=1^N_h^k(s,a) _n^N_h^k(s,a)(P_he_h+1^k_h,n(s,a))(s,a)≤ L_h+1^2. Moreover, for every k,h,s,ak,h,s,a, ∑n=1Nhk(s,a)αnNhk(s,a)(ℙheh+1kh,n(s,a))(s,a) _n=1^N_h^k(s,a) _n^N_h^k(s,a)(P_he_h+1^k_h,n(s,a))(s,a) is <kD_<k-measurable because kh,n(s,a)<k_h,n(s,a)<k for every 1≤n≤Nhk(s,a)1≤ n≤ N_h^k(s,a). By Lemma D.1, 0≤Vh+1k≤Lh+10≤ V_h+1^k≤ L_h+1. Moreover, Vh+1kV_h+1^k is <kD_<k-measurable, since the iterate before episode k depends only on τ1,…,τk−1τ^1,…,τ^k-1. Therefore, Lemma B.3 also holds for KLPQ. Apply it with failure probability δ/4δ/4 and denote the resulting event by ℰ1E_1. Choose the fixed universal constant cbc_b so that cb≥4maxc,1c_b≥ 4 \c,1\, where c is the universal constant in Lemma B.3. For N≥1N≥ 1, Lemma B.1 with exponent 1/21/2 gives cbLh+1ιHN≤∑n=1NαnNbh,n≤2cbLh+1ιHN.c_bL_h+1 HN≤ _n=1^N _n^Nb_h,n≤ 2c_bL_h+1 HN. (36) Moreover, on ℰ1E_1, for 1≤N≤NhK+1(s,a)1≤ N≤ N_h^K+1(s,a), |∑n=1NαnN(ℙ^hkh,n(s,a)−ℙh,s,a)Vh+1kh,n(s,a)|≤4cLh+1ιHN≤cbLh+1ιHN≤∑n=1NαnNbh,n. | _n=1^N _n^N( P_h^k_h,n(s,a)-P_h,s,a)V_h+1^k_h,n(s,a) |≤ 4cL_h+1 HN≤ c_bL_h+1 HN≤ _n=1^N _n^Nb_h,n. (37) The first inequality is immediate when Lh+1=0L_h+1=0. Otherwise, H≥2H≥ 2, so ι≥log2 ≥ 2 and log(4SAT/δ)=ι+log4≤4ι (4SAT/δ)= + 4≤ 4 . The second follows from cb≥4c_b≥ 4c, and the last is the lower bound in (36). For N=0N=0, both weighted sums are zero. Lemma D.2. On the event ℰ1E_1, if cbc_b is fixed as above, Q~hj(s,a)≤Qhk(s,a)≤Qhπk(s,a)≤Qh⋆(s,a),Vhk(s)≤Vhπk(s)≤Vh⋆(s) Q_h^j(s,a)≤ Q_h^k(s,a)≤ Q_h^π^k(s,a)≤ Q_h (s,a), V_h^k(s)≤ V_h^π^k(s)≤ V_h (s) (38) simultaneously for every k∈[K+1]k∈[K+1], j∈[k]j∈[k], h∈[H]h∈[H], and (s,a)∈×(s,a) ×A. Proof. We work on the event ℰ1E_1 defined above. Fix k∈[K+1]k∈[K+1] and proceed by backward induction on h. For the base case h=H+1h=H+1, VH+1πk=VH+1k=VH+1⋆=0V_H+1^π^k=V_H+1^k=V_H+1 =0. For the induction hypothesis, suppose that the desired value ordering holds at h+1h+1, namely, Vh+1k≤Vh+1πk≤Vh+1⋆V_h+1^k≤ V_h+1^π^k≤ V_h+1 . For the induction step from h+1h+1 to h, the induction hypothesis, monotonicity, and nonnegativity give Vh+1πk≥Vh+1k≥Vh+1i≥0V_h+1^π^k≥ V_h+1^k≥ V_h+1^i≥ 0 for every i≤ki≤ k, and therefore Qhπk(s,a)≥0Q_h^π^k(s,a)≥ 0. Fix j≤kj≤ k and (s,a)(s,a), write N:=Nhj(s,a)N:=N_h^j(s,a), and suppress the dependence of kh,nk_h,n on (s,a)(s,a). Unrolling Line 12 gives Q~hj(s,a)=α0NQ~h1(s,a)+∑n=1NαnN(rh(s,a)+ℙ^hkh,nVh+1kh,n−bh,n). Q_h^j(s,a)= _0^N Q_h^1(s,a)+ _n=1^N _n^N (r_h(s,a)+ P_h^k_h,nV_h+1^k_h,n-b_h,n ). (39) Writing the Bellman equation for Qhπk(s,a)Q_h^π^k(s,a) with the same weights and subtracting (39) yields Qhπk(s,a)−Q~hj(s,a)= Q_h^π^k(s,a)- Q_h^j(s,a)= α0NQhπk(s,a)+∑n=1NαnNℙh,s,a(Vh+1πk−Vh+1kh,n) _0^NQ_h^π^k(s,a)+ _n=1^N _n^NP_h,s,a(V_h+1^π^k-V_h+1^k_h,n) +∑n=1NαnNbh,n−∑n=1NαnN(ℙ^hkh,n−ℙh,s,a)Vh+1kh,n + _n=1^N _n^Nb_h,n- _n=1^N _n^N( P_h^k_h,n-P_h,s,a)V_h+1^k_h,n ≥ ≥ α0NQhπk(s,a)+∑n=1NαnNℙh,s,a(Vh+1πk−Vh+1kh,n)≥0. _0^NQ_h^π^k(s,a)+ _n=1^N _n^NP_h,s,a(V_h+1^π^k-V_h+1^k_h,n)≥ 0. The first inequality follows from (37), the second uses Qhπk≥0Q_h^π^k≥ 0 and Vh+1πk≥Vh+1kh,nV_h+1^π^k≥ V_h+1^k_h,n for every historical visit kh,n<j≤k_h,n<j≤ k. This also covers N=0N=0, since every sum ∑n=1N(⋯) _n=1^N(·s) above is then zero. Thus Q~hj(s,a)≤Qhπk(s,a) Q_h^j(s,a)≤ Q_h^π^k(s,a) for every j≤kj≤ k, and hence Qhk(s,a)=max1≤j≤kQ~hj(s,a)≤Qhπk(s,a)≤Qh⋆(s,a),Q_h^k(s,a)= _1≤ j≤ k Q_h^j(s,a)≤ Q_h^π^k(s,a)≤ Q_h (s,a), where the last inequality follows from Proposition 2.1. Since πhk(⋅∣s)=Gh,s(Qhk(s,⋅)) _h^k(· s)=G_h,s(Q_h^k(s,·)), Vhk(s) V_h^k(s) =⟨πhk(⋅∣s),Qhk(s,⋅)⟩−1ηKL(πhk(⋅∣s)∥πhref(⋅∣s)) = _h^k(· s),Q_h^k(s,·) _A- 1ηKL\! ( _h^k(· s) \| _h^ref(· s) ) ≤⟨πhk(⋅∣s),Qhπk(s,⋅)⟩−1ηKL(πhk(⋅∣s)∥πhref(⋅∣s)) ≤ _h^k(· s),Q_h^π^k(s,·) _A- 1ηKL\! ( _h^k(· s) \| _h^ref(· s) ) =Vhπk(s)≤Vh⋆(s). =V_h^π^k(s)≤ V_h (s). This proves the induction step at stage h and hence establishes the inequalities in (38) by backward induction. Since all arguments beyond the deterministic range and monotonicity properties use only ℰ1E_1, this completes the proof. ∎ Lemma D.3. On ℰ1E_1, for every k∈[K+1]k∈[K+1], h∈[H]h∈[H], and s∈s , (Vh⋆(s)−Vhk(s))2≤ehk(s).(V_h (s)-V_h^k(s))^2≤ e_h^k(s). (40) Moreover, the output policy in Algorithm 2 satisfies SubOpt(π^)≤η∑h=1H(s,a)∼dhπ⋆[(Qh⋆(s,a)−QhK+1(s,a))2].SubOpt( π)≤η _h=1^HE_(s,a) d_h^π [(Q_h (s,a)-Q_h^K+1(s,a))^2 ]. (41) Proof. Work on ℰ1E_1. For the value error, convexity of Fh,sF_h,s at Qh⋆(s,⋅)Q_h (s,·) and the ordering Qhk≤Qh⋆Q_h^k≤ Q_h give 0≤Vh⋆(s)−Vhk(s)≤⟨πh⋆(⋅∣s),Qh⋆(s,⋅)−Qhk(s,⋅)⟩.0≤ V_h (s)-V_h^k(s)≤ _h (· s),Q_h (s,·)-Q_h^k(s,·) _A. Squaring and applying Jensen’s inequality yields (Vh⋆(s)−Vhk(s))2≤∑aπh⋆(a∣s)[Qh⋆(s,a)−Qhk(s,a)]2=ehk(s),(V_h (s)-V_h^k(s))^2≤ _a _h (a s)[Q_h (s,a)-Q_h^k(s,a)]^2=e_h^k(s), which proves the first claim. It remains to prove the output-policy bound. Let π^=πK+1 π=π^K+1. By (38), 0≤Qhπ^(s,a)−QhK+1(s,a)≤Qh⋆(s,a)−QhK+1(s,a).0≤ Q_h π(s,a)-Q_h^K+1(s,a)≤ Q_h (s,a)-Q_h^K+1(s,a). By Bellman consistency, Vh⋆(s)=⟨πh⋆(⋅∣s),Qh⋆(s,⋅)⟩−1ηKL(πh⋆(⋅∣s)∥πhref(⋅∣s)), V_h (s)= _h (· s),Q_h (s,·) _A- 1ηKL\! ( _h (· s) \| _h^ref(· s) ), Vhπ^(s)=⟨π^h(⋅∣s),Qhπ^(s,⋅)⟩−1ηKL(π^h(⋅∣s)∥πhref(⋅∣s)). V_h π(s)= π_h(· s),Q_h π(s,·) _A- 1ηKL\! ( π_h(· s) \| _h^ref(· s) ). Subtracting the two identities and adding and subtracting ⟨πh⋆(⋅∣s),Qhπ^(s,⋅)⟩ _h (· s),Q_h π(s,·) _A yields Vh⋆(s)−Vhπ^(s)= V_h (s)-V_h π(s)= ⟨πh⋆(⋅∣s)−π^h(⋅∣s),Qhπ^(s,⋅)⟩+⟨πh⋆(⋅∣s),Qh⋆(s,⋅)−Qhπ^(s,⋅)⟩ _h (· s)- π_h(· s),Q_h π(s,·) _A+ _h (· s),Q_h (s,·)-Q_h π(s,·) _A −1ηKL(πh⋆(⋅∣s)∥πhref(⋅∣s))+1ηKL(π^h(⋅∣s)∥πhref(⋅∣s)) - 1ηKL\! ( _h (· s) \| _h^ref(· s) )+ 1ηKL\! ( π_h(· s) \| _h^ref(· s) ) = = ⟨πh⋆(⋅∣s)−π^h(⋅∣s),Qhπ^(s,⋅)⟩+⟨πh⋆(⋅∣s),ℙh(Vh+1⋆−Vh+1π^)(s,⋅)⟩ _h (· s)- π_h(· s),Q_h π(s,·) _A+ _h (· s),P_h(V_h+1 -V_h+1 π)(s,·) _A −1ηKL(πh⋆(⋅∣s)∥πhref(⋅∣s))+1ηKL(π^h(⋅∣s)∥πhref(⋅∣s)). - 1ηKL\! ( _h (· s) \| _h^ref(· s) )+ 1ηKL\! ( π_h(· s) \| _h^ref(· s) ). Taking expectation of this identity with respect to s∼dhπ⋆s d_h^π and summing over h, using VH+1⋆=VH+1π^=0V_H+1 =V_H+1 π=0, gives SubOpt(π^)=∑h=1Hs∼dhπ⋆[ ( π)= _h=1^HE_s d_h^π [ ⟨πh⋆(⋅∣s)−π^h(⋅∣s),Qhπ^(s,⋅)⟩ _h (· s)- π_h(· s),Q_h π(s,·) _A −1ηKL(πh⋆(⋅∣s)∥πhref(⋅∣s))+1ηKL(π^h(⋅∣s)∥πhref(⋅∣s))]. - 1ηKL\! ( _h (· s) \| _h^ref(· s) )+ 1ηKL\! ( π_h(· s) \| _h^ref(· s) ) ]. The Gibbs formula for π^h π_h gives logπ^h(a∣s)πhref(a∣s)=ηQhK+1(s,a)−log∑bπhref(b∣s)eηQhK+1(s,b). π_h(a s) _h^ref(a s)=η Q_h^K+1(s,a)- _b _h^ref(b s)e^η Q_h^K+1(s,b). Hence, we have 1ηKL(πh⋆(⋅∣s)∥π^h(⋅∣s))= 1ηKL\! ( _h (· s) \| π_h(· s) )= 1ηKL(πh⋆(⋅∣s)∥πhref(⋅∣s))−⟨πh⋆(⋅∣s),QhK+1(s,⋅)⟩ 1ηKL\! ( _h (· s) \| _h^ref(· s) )- _h (· s),Q_h^K+1(s,·) _A +1ηlog∑bπhref(b∣s)eηQhK+1(s,b) + 1η _b _h^ref(b s)e^η Q_h^K+1(s,b) =(i) (i)= 1ηKL(πh⋆(⋅∣s)∥πhref(⋅∣s))−1ηKL(π^h(⋅∣s)∥πhref(⋅∣s)) 1ηKL\! ( _h (· s) \| _h^ref(· s) )- 1ηKL\! ( π_h(· s) \| _h^ref(· s) ) −⟨πh⋆(⋅∣s)−π^h(⋅∣s),QhK+1(s,⋅)⟩, - _h (· s)- π_h(· s),Q_h^K+1(s,·) _A, where (i) uses the Gibbs variational identity. Substituting this identity into the preceding expression for SubOpt(π^)SubOpt( π) gives SubOpt(π^) ( π) =∑h=1Hs∼dhπ⋆[⟨πh⋆(⋅∣s)−π^h(⋅∣s),Qhπ^(s,⋅)−QhK+1(s,⋅)⟩ = _h=1^HE_s d_h^π [ _h (· s)- π_h(· s),Q_h π(s,·)-Q_h^K+1(s,·) _A −1ηKL(πh⋆(⋅∣s)∥π^h(⋅∣s))] 119.50157pt- 1ηKL\! ( _h (· s) \| π_h(· s) ) ] ≤∑h=1Hs∼dhπ⋆[⟨πh⋆(⋅∣s)−π^h(⋅∣s),Qhπ^(s,⋅)−QhK+1(s,⋅)⟩], ≤ _h=1^HE_s d_h^π [ _h (· s)- π_h(· s),Q_h π(s,·)-Q_h^K+1(s,·) _A ], where the inequality uses the nonnegativity of KL divergence. For every action with πh⋆(a∣s)>0 _h (a s)>0, the two Gibbs formulas give πh⋆(a∣s)−π^h(a∣s) _h (a s)- π_h(a s) =πh⋆(a∣s)(1−e−η[Qh⋆(s,a)−QhK+1(s,a)]∑bπh⋆(b∣s)e−η[Qh⋆(s,b)−QhK+1(s,b)]) = _h (a s) (1- e^-η[Q_h (s,a)-Q_h^K+1(s,a)] _b _h (b s)e^-η[Q_h (s,b)-Q_h^K+1(s,b)] ) ≤(i)πh⋆(a∣s)(1−e−η[Qh⋆(s,a)−QhK+1(s,a)]) (i)≤ _h (a s) (1-e^-η[Q_h (s,a)-Q_h^K+1(s,a)] ) ≤(ii)ηπh⋆(a∣s)[Qh⋆(s,a)−QhK+1(s,a)]. (i)≤η _h (a s)[Q_h (s,a)-Q_h^K+1(s,a)]. (42) Here (i) uses QhK+1≤Qh⋆Q_h^K+1≤ Q_h , which implies ∑bπh⋆(b∣s)e−η[Qh⋆(s,b)−QhK+1(s,b)]≤1 _b _h (b s)e^-η[Q_h (s,b)-Q_h^K+1(s,b)]≤ 1, and (i) uses 1−e−v≤v1-e^-v≤ v for v≥0v≥ 0. For actions outside the common support, both probabilities are zero, so (42) holds for every action. Since Qhπ^(s,a)−QhK+1(s,a)≥0Q_h π(s,a)-Q_h^K+1(s,a)≥ 0, applying (42) yields SubOpt(π^) ( π) ≤η∑h=1Hs∼dhπ⋆∑aπh⋆(a∣s)[Qh⋆(s,a)−QhK+1(s,a)][Qhπ^(s,a)−QhK+1(s,a)] ≤η _h=1^HE_s d_h^π _a _h (a s)[Q_h (s,a)-Q_h^K+1(s,a)][Q_h π(s,a)-Q_h^K+1(s,a)] ≤η∑h=1Hs∼dhπ⋆∑aπh⋆(a∣s)[Qh⋆(s,a)−QhK+1(s,a)]2 ≤η _h=1^HE_s d_h^π _a _h (a s)[Q_h (s,a)-Q_h^K+1(s,a)]^2 =η∑h=1H(s,a)∼dhπ⋆[(Qh⋆(s,a)−QhK+1(s,a))2], =η _h=1^HE_(s,a) d_h^π [(Q_h (s,a)-Q_h^K+1(s,a))^2 ], where the second inequality uses Qhπ^(s,a)−QhK+1(s,a)≤Qh⋆(s,a)−QhK+1(s,a)Q_h π(s,a)-Q_h^K+1(s,a)≤ Q_h (s,a)-Q_h^K+1(s,a) from (38), and the last equality follows from dhπ⋆(s,a)=dhπ⋆(s)πh⋆(a∣s)d_h^π (s,a)=d_h^π (s) _h (a s). This proves the second claim. ∎ Lemma D.4. On ℰ1E_1, simultaneously for every k∈[K+1]k∈[K+1], h∈[H]h∈[H], and (s,a)∈×(s,a) ×A, writing N:=Nhk(s,a)N:=N_h^k(s,a), (Δhk(s,a))2≤ ( _h^k(s,a))^2≤ Lh2N=0+cH2Lh+12ι2N≥1N∨1 L_h^21\N=0\+cH^2L_h+1^2 ^2 1\N≥ 1\N 1 +(1+1H)∑n=1NαnN(ℙheh+1kh,n(s,a))(s,a), + (1+ 1H ) _n=1^N _n^N(P_he_h+1^k_h,n(s,a))(s,a), where c>0c>0 is a universal constant. Proof. Fix k,h,s,ak,h,s,a, let N:=Nhk(s,a)N:=N_h^k(s,a), and suppress the dependence of kh,nk_h,n on (s,a)(s,a). If N=0N=0, then Qhk(s,a)=0Q_h^k(s,a)=0 and (Δhk(s,a))2≤Lh2( _h^k(s,a))^2≤ L_h^2 by (3). Suppose N≥1N≥ 1. Subtracting (39) with j=kj=k from the optimal Bellman equation gives Qh⋆(s,a)−Q~hk(s,a)= Q_h (s,a)- Q_h^k(s,a)= ∑n=1NαnNℙh,s,a(Vh+1⋆−Vh+1kh,n)+∑n=1NαnNbh,n _n=1^N _n^NP_h,s,a(V_h+1 -V_h+1^k_h,n)+ _n=1^N _n^Nb_h,n −∑n=1NαnN(ℙ^hkh,n−ℙh,s,a)Vh+1kh,n, - _n=1^N _n^N( P_h^k_h,n-P_h,s,a)V_h+1^k_h,n, since α0N=0 _0^N=0. By (38) and (37), 0≤Qh⋆(s,a)−Qhk(s,a) 0≤ Q_h (s,a)-Q_h^k(s,a) ≤Qh⋆(s,a)−Q~hk(s,a) ≤ Q_h (s,a)- Q_h^k(s,a) ≤∑n=1NαnNℙh,s,a(Vh+1⋆−Vh+1kh,n)+2∑n=1NαnNbh,n. ≤ _n=1^N _n^NP_h,s,a(V_h+1 -V_h+1^k_h,n)+2 _n=1^N _n^Nb_h,n. Consequently, (Δhk(s,a))2 ( _h^k(s,a))^2 ≤(1+1H)(∑n=1NαnNℙh,s,a(Vh+1⋆−Vh+1kh,n))2+4(H+1)(∑n=1NαnNbh,n)2 ≤ (1+ 1H ) ( _n=1^N _n^NP_h,s,a(V_h+1 -V_h+1^k_h,n) )^2+4(H+1) ( _n=1^N _n^Nb_h,n )^2 ≤(1+1H)∑n=1NαnNℙh,s,a[(Vh+1⋆−Vh+1kh,n)2]+32cb2H2Lh+12ι2N ≤ (1+ 1H ) _n=1^N _n^NP_h,s,a\! [(V_h+1 -V_h+1^k_h,n)^2 ]+ 32c_b^2H^2L_h+1^2 ^2N ≤(1+1H)∑n=1NαnN(ℙheh+1kh,n)(s,a)+cH2Lh+12ι2N. ≤ (1+ 1H ) _n=1^N _n^N(P_he_h+1^k_h,n)(s,a)+ cH^2L_h+1^2 ^2N. The first inequality uses (x+y)2≤(1+1/H)x2+(H+1)y2(x+y)^2≤(1+1/H)x^2+(H+1)y^2. The second follows from Jensen’s inequality, first with respect to the weights αnN\ _n^N\ and then with respect to ℙh(⋅∣s,a)P_h(· s,a), together with the upper bound in (36). The last inequality follows from (40), after enlarging the universal constant c to dominate 32cb232c_b^2. Together with the zero-count case, this proves the lemma. ∎ We now introduce a common event for the proof of Theorem 4.1: If SAT>1SAT>1, apply Lemma B.4 with failure probability δ/4δ/4 and denote its event by ℰ2E_2, if SAT=1SAT=1, let ℰ2E_2 be the sure event. Apply Lemma B.5 twice with failure probability δ/4δ/4, using Uhk(s,a)=∑n=1Nhk(s,a)αnNhk(s,a)(ℙheh+1kh,n(s,a))(s,a)andUhk(s,a)=(ℙheh+1k)(s,a),U_h^k(s,a)= _n=1^N_h^k(s,a) _n^N_h^k(s,a)(P_he_h+1^k_h,n(s,a))(s,a) U_h^k(s,a)=(P_he_h+1^k)(s,a), respectively, with ehke_h^k defined as in Section 5.1 for Algorithm 2. The deterministic bounds and predictability above ensure that both choices of Uhk(s,a)U_h^k(s,a) with Bh=Lh+12B_h=L_h+1^2 satisfy the conditions of Lemma B.5. Denote the two events by ℰ3E_3 and ℰ4E_4, and set ℰ:=ℰ1∩ℰ2∩ℰ3∩ℰ4,Pr(ℰ)≥1−δ.E:=E_1 _2 _3 _4, (E)≥ 1-δ. All four events are defined for the same iterates generated using the original bonus in (4). D.2 Proof of Theorem 4.1 Proof. If SAT=1SAT=1, the output is the unique policy, so SubOpt(π^)=0SubOpt( π)=0. Hence suppose SAT>1SAT>1. Work on the common event ℰE defined above, which has probability at least 1−δ1-δ. Starting from Lemma D.4, we repeat the argument used in the proof of Lemma C.4. The count-control step, the two applications of Lemma B.5, and the reindexing argument are unchanged, up to universal constants, because the required boundedness and predictability conditions are verified in Appendix D.1. The only difference is that the propagated error term in Lemma D.4 has no factor γh+1 _h+1. Therefore, the same calculation yields, for every h∈[H]h∈[H], ∑k=1K∑sdhπ⋆(s)ehk(s)≤(1+5H)∑k=1K∑sdh+1π⋆(s)eh+1k(s)+c0SACη⋆H2Lh2ι3(1+logK). _k=1^K _sd_h^π (s)e_h^k(s)≤ (1+ 5H ) _k=1^K _sd_h+1^π (s)e_h+1^k(s)+c_0SAC_η H^2L_h^2 ^3(1+ K). Applying the same backward iteration argument as in the proof of Lemma C.4, now without the products of γj _j, and using eH+1k≡0e_H+1^k≡ 0 together with (1+5H)H≤e5,∑t=hHLt2≤Lh3, (1+ 5H )^H≤ e^5, _t=h^HL_t^2≤ L_h^3, gives ∑k=1K(s,a)∼dhπ⋆[(Qhk(s,a)−Qh⋆(s,a))2]≤c1SACη⋆H2Lh3ι3(1+logK), _k=1^KE_(s,a) d_h^π [(Q_h^k(s,a)-Q_h (s,a))^2 ]≤ c_1SAC_η H^2L_h^3 ^3(1+ K), which gives the desired accumulated squared Q-estimation error bound. By Line 13, Qhk+1≥QhkQ_h^k+1≥ Q_h^k coordinatewise, while the ordering (38) gives Qhk≤Qh⋆Q_h^k≤ Q_h . Therefore, for every k∈[K]k∈[K] and (s,a)∈×(s,a) ×A, 0≤Qh⋆(s,a)−QhK+1(s,a)≤Qh⋆(s,a)−Qhk(s,a).0≤ Q_h (s,a)-Q_h^K+1(s,a)≤ Q_h (s,a)-Q_h^k(s,a). Squaring, averaging first with respect to dhπ⋆d_h^π , and then averaging over k∈[K]k∈[K] gives (s,a)∼dhπ⋆[(QhK+1(s,a)−Qh⋆(s,a))2] _(s,a) d_h^π [(Q_h^K+1(s,a)-Q_h (s,a))^2 ] ≤1K∑k=1K(s,a)∼dhπ⋆[(Qhk(s,a)−Qh⋆(s,a))2] ≤ 1K _k=1^KE_(s,a) d_h^π [(Q_h^k(s,a)-Q_h (s,a))^2 ] ≤c1SACη⋆KH2Lh3ι3(1+logK). ≤ c_1 SAC_η KH^2L_h^3 ^3(1+ K). Substituting this into (41) gives SubOpt(π^) ( π) ≤cηSACη⋆H2ι3(1+logK)K∑h=1HLh3 ≤ c η SAC_η H^2 ^3(1+ K)K _h=1^HL_h^3 ≤cηH6SACη⋆Kι3(1+logK). ≤ c η H^6SAC_η K ^3(1+ K). The second inequality uses ∑h=1HLh3≤H4 _h=1^HL_h^3≤ H^4. This proves Theorem 4.1. ∎ References Chen et al. (2026) C. Chen, Y. Zhang, X. Liu, Z. Xie, S. D. Liu, and N. Jiang Offline two-player zero-sum markov games with KL regularization. In Forty-third International Conference on Machine Learning, Cited by: §1.1, §1, §1, Remark 3.1. Chen and Zhang (2026a) C. Chen and Y. Zhang Fast rates in α-potential games via regularized mirror descent. arXiv preprint arXiv:2605.00268. Cited by: Remark 3.1. Chen and Zhang (2026b) C. Chen and Y. Zhang Pessimism-free offline learning in general-sum games via kl regularization. arXiv preprint arXiv:2605.00264. Cited by: §1.1, §1. Even-Dar and Mansour (2003) E. Even-Dar and Y. Mansour Learning rates for q-learning. Journal of machine learning Research 5 (Dec), p. 1–25. Cited by: §1.1. Freedman (1975) D. A. Freedman On tail probabilities for martingales. the Annals of Probability, p. 100–118. Cited by: Appendix B. Fujimoto et al. (2019) S. Fujimoto, D. Meger, and D. Precup Off-policy deep reinforcement learning without exploration. In International conference on machine learning, p. 2052–2062. Cited by: §1. Geist et al. (2019) M. Geist, B. Scherrer, and O. Pietquin A theory of regularized markov decision processes. In International conference on machine learning, p. 2160–2169. Cited by: §2.1, §2.1. Hong et al. (2026) H. Hong, Z. Wang, Q. Gu, and H. Wang Online kl-regularized reinforcement learning with function approximation under misspecification. arXiv preprint arXiv:2606.06053. Cited by: §1.1. Jeong and Lee (2024) N. Jeong and D. Lee Finite-time error analysis of soft q-learning: switching system approach. In 2024 IEEE 63rd Conference on Decision and Control (CDC), p. 3897–3904. Cited by: §1.1. Jeong and Lee (2025) N. Jeong and D. Lee Unified finite-time error analysis of soft q-learning. Neurocomputing 626, p. 129582. Cited by: §1.1. Ji et al. (2026a) K. Ji, Q. Di, H. Zhao, Q. Zhao, and Q. Gu On the optimal sample complexity of offline multi-armed bandits with kl regularization. arXiv preprint arXiv:2605.02141. Cited by: §1.1, §1, Remark 2.1, Remark 4.1. Ji et al. (2026b) K. Ji, Q. Zhao, H. Zhao, Q. Di, and Q. Gu Near-optimal regret for kl-regularized multi-armed bandits. arXiv preprint arXiv:2603.02155. Cited by: §1.1. Jiao et al. (2026) Y. Jiao, J. Woo, G. Li, G. Joshi, and Y. Chi Sample complexity of average-reward q-learning: from single-agent to federated reinforcement learning. arXiv preprint arXiv:2601.13642. Cited by: §1.1. Jin et al. (2018) C. Jin, Z. Allen-Zhu, S. Bubeck, and M. Jordan Is q-learning provably efficient?. Advances in neural information processing systems 31. Cited by: Appendix B, §1.1, §3. Jin et al. (2021) Y. Jin, Z. Yang, and Z. Wang Is pessimism provably efficient for offline rl?. In International conference on machine learning, p. 5084–5096. Cited by: §1.1, §1. Kumar et al. (2020) A. Kumar, A. Zhou, G. Tucker, and S. Levine Conservative q-learning for offline reinforcement learning. Advances in neural information processing systems 33, p. 1179–1191. Cited by: §1. Levine et al. (2020) S. Levine, A. Kumar, G. Tucker, and J. Fu Offline reinforcement learning: tutorial, review, and perspectives on open problems. arXiv preprint arXiv:2005.01643. Cited by: §1. Li et al. (2021a) G. Li, C. Cai, Y. Chen, Y. Gu, Y. Wei, and Y. Chi Tightening the dependence on horizon in the sample complexity of q-learning. In International Conference on Machine Learning, p. 6296–6306. Cited by: §1.1. Li et al. (2024) G. Li, C. Cai, Y. Chen, Y. Wei, and Y. Chi Is q-learning minimax optimal? a tight sample complexity analysis. Operations Research 72 (1), p. 222–236. Cited by: §1.1, §1. Li et al. (2021b) G. Li, L. Shi, Y. Chen, Y. Gu, and Y. Chi Breaking the sample complexity barrier to regret-optimal model-free reinforcement learning. Advances in Neural Information Processing Systems 34, p. 17762–17776. Cited by: Appendix B, §1.1. Li et al. (2020) G. Li, Y. Wei, Y. Chi, Y. Gu, and Y. Chen Sample complexity of asynchronous q-learning: sharper analysis and variance reduction. Advances in neural information processing systems 33, p. 7031–7043. Cited by: §1.1. Liu et al. (2025) X. Liu, Z. Xie, and S. Zhang Linear Q-learning does not diverge in L2L^2: convergence rates to a bounded set. In Forty-second International Conference on Machine Learning, Cited by: §1.1, §1. Nayak et al. (2025) A. Nayak, T. Yang, O. Yagan, G. Joshi, and Y. Chi Achieving logarithmic regret in kl-regularized zero-sum markov games. arXiv preprint arXiv:2510.13060. Cited by: §1.1. Ouyang et al. (2022) L. Ouyang, J. Wu, X. Jiang, D. Almeida, C. Wainwright, P. Mishkin, C. Zhang, S. Agarwal, K. Slama, A. Ray, et al. Training language models to follow instructions with human feedback. Advances in neural information processing systems 35, p. 27730–27744. Cited by: §1. Qiao et al. (2026) Z. Qiao, J. Lyu, B. Lyu, Y. Shu, S. Gao, and S. Qiu Model-based offline rl via robust value-aware model learning with implicitly differentiable adaptive weighting. arXiv preprint arXiv:2603.08118. Cited by: §1.1. Qu and Wierman (2020) G. Qu and A. Wierman Finite-time analysis of asynchronous stochastic approximation and Q-learning. In Conference on learning theory, p. 3185–3205. Cited by: §1.1. Rafailov et al. (2023) R. Rafailov, A. Sharma, E. Mitchell, C. D. Manning, S. Ermon, and C. Finn Direct preference optimization: your language model is secretly a reward model. Advances in neural information processing systems 36, p. 53728–53741. Cited by: §1. Rashidinejad et al. (2021) P. Rashidinejad, B. Zhu, C. Ma, J. Jiao, and S. Russell Bridging offline reinforcement learning and imitation learning: a tale of pessimism. Advances in Neural Information Processing Systems 34, p. 11702–11716. Cited by: §1.1, §1, §2.2. Shi et al. (2022) L. Shi, G. Li, Y. Wei, Y. Chen, and Y. Chi Pessimistic q-learning for offline reinforcement learning: towards optimal sample complexity. In International conference on machine learning, p. 19967–20025. Cited by: Appendix B, §1.1, §1.1, §1, §1, §2.2, §3, §4, §4, §4. Tiapkin et al. (2023) D. Tiapkin, D. Belomestny, D. Calandriello, E. Moulines, R. Munos, A. Naumov, P. Perrault, Y. Tang, M. Valko, and P. Menard Fast rates for maximum entropy exploration. In International Conference on Machine Learning, p. 34161–34221. Cited by: §1.1. Tiapkin et al. (2024) D. Tiapkin, D. Belomestny, D. Calandriello, E. Moulines, A. Naumov, P. Perrault, M. Valko, and P. Menard Demonstration-regularized RL. In The Twelfth International Conference on Learning Representations, Cited by: §1.1. Uehara et al. (2023) M. Uehara, N. Kallus, J. D. Lee, and W. Sun Offline minimax soft-q-learning under realizability and partial coverage. Advances in Neural Information Processing Systems 36, p. 12797–12809. Cited by: §1.1, §1.1. Uehara and Sun (2021) M. Uehara and W. Sun Pessimistic model-based offline reinforcement learning under partial coverage. arXiv preprint arXiv:2107.06226. Cited by: §1.1. Watkins and Dayan (1992) C. J. Watkins and P. Dayan Q-learning. Machine learning 8 (3), p. 279–292. Cited by: §1.1, §1, §3. Wu et al. (2025) D. Wu, C. Shi, J. Yang, and C. Shen Greedy sampling is provably efficient for RLHF. In The Thirty-ninth Annual Conference on Neural Information Processing Systems, Cited by: §1.1, Remark 3.1. Wu et al. (2019) Y. Wu, G. Tucker, and O. Nachum Behavior regularized offline reinforcement learning. arXiv preprint arXiv:1911.11361. Cited by: §1. Xi et al. (2025) J. Xi, A. Garcia, and P. Momčilović Regularized q-learning with linear function approximation. IEEE Transactions on Automatic Control 71 (1), p. 504–511. Cited by: §1.1. Xie et al. (2021a) T. Xie, C. Cheng, N. Jiang, P. Mineiro, and A. Agarwal Bellman-consistent pessimism for offline reinforcement learning. Advances in neural information processing systems 34, p. 6683–6694. Cited by: §1.1. Xie et al. (2021b) T. Xie, N. Jiang, H. Wang, C. Xiong, and Y. Bai Policy finetuning: bridging sample-efficient offline and online reinforcement learning. Advances in neural information processing systems 34, p. 27395–27407. Cited by: §1.1, §2.2, §4. Xiong et al. (2023) W. Xiong, H. Dong, C. Ye, Z. Wang, H. Zhong, H. Ji, N. Jiang, and T. Zhang Iterative preference learning from human feedback: bridging theory and practice for rlhf under kl-constraint. arXiv preprint arXiv:2312.11456. Cited by: §1. Xiong et al. (2022) W. Xiong, H. Zhong, C. Shi, C. Shen, L. Wang, and T. Zhang Nearly minimax optimal offline reinforcement learning with linear function approximation: single-agent mdp and markov game. arXiv preprint arXiv:2205.15512. Cited by: §1.1. Yan et al. (2023) Y. Yan, G. Li, Y. Chen, and J. Fan The efficacy of pessimism in asynchronous q-learning. IEEE Transactions on Information Theory 69 (11), p. 7185–7219. Cited by: §1.1, §1.1. Ye et al. (2023) C. Ye, R. Yang, Q. Gu, and T. Zhang Corruption-robust offline reinforcement learning with general function approximation. Advances in Neural Information Processing Systems 36, p. 36208–36221. Cited by: §1.1. Zhan et al. (2022) W. Zhan, B. Huang, A. Huang, N. Jiang, and J. Lee Offline reinforcement learning with realizability and single-policy concentrability. In Conference on Learning Theory, p. 2730–2775. Cited by: §1.1. Zhang et al. (2024) D. Zhang, B. Lyu, S. Qiu, M. Kolar, and T. Zhang Pessimism meets risk: risk-sensitive offline reinforcement learning. In Proceedings of the 41st International Conference on Machine Learning, p. 59459–59489. Cited by: §1.1. Zhang et al. (2021) S. Zhang, Z. Zhang, and S. T. Maguluri Finite sample analysis of average-reward td learning and Q-learning. Advances in Neural Information Processing Systems 34, p. 1230–1242. Cited by: §1.1. Zhang et al. (2026) Y. Zhang, C. Chen, and N. Jiang Beyond pessimism: offline learning in kl-regularized games. arXiv preprint arXiv:2604.06738. Cited by: §1.1, §1, Remark 4.2. Zhao et al. (2025a) H. Zhao, C. Ye, Q. Gu, and T. Zhang Sharp analysis for KL-regularized contextual bandits and RLHF. In The Thirty-ninth Annual Conference on Neural Information Processing Systems, Cited by: §1.1, §1. Zhao et al. (2025b) H. Zhao, C. Ye, W. Xiong, Q. Gu, and T. Zhang Logarithmic regret for online kl-regularized reinforcement learning. arXiv preprint arXiv:2502.07460. Cited by: §1.1, §2.1. Zhao et al. (2026a) Q. Zhao, K. Ji, H. Zhao, and Q. Gu Fast rates for offline contextual bandits with forward-kl regularization under single-policy concentrability. arXiv preprint arXiv:2605.09214. Cited by: §1.1, §1, Remark 2.1. Zhao et al. (2026b) Q. Zhao, K. Ji, H. Zhao, T. Zhang, and Q. Gu Towards a sharp analysis of offline policy learning for f-divergence-regularized contextual bandits. In The Fourteenth International Conference on Learning Representations, Cited by: §1.1, §1, Remark 2.1.