Optimal Single-Policy Sample Complexity and Transient Coverage for Average-Reward Offline RL
Authors: Matthew Zurek
Guy Zamir
Yudong Chen
Venue: NeurIPS 2025 poster ()
Keywords: RL theory
offline RL
average-reward RL
sample complexity
minimax lower bounds
Primary area: reinforcement_learning

Abstract: We study offline reinforcement learning in average-reward MDPs, which presents increased challenges from the perspectives of distribution shift and non-uniform coverage, and has been relatively underexamined from a theoretical perspective. While previous work obtains performance guarantees under single-policy data coverage assumptions, such guarantees utilize additional complexity measures which are uniform over all policies, such as the uniform mixing time. We develop sharp guarantees depending only on the target policy, specifically the bias span and a novel policy hitting radius, yielding the first fully single-policy sample complexity bound for average-reward offline RL. We are also the first to handle general weakly communicating MDPs, contrasting restrictive structural assumptions made in prior work. To achieve this, we introduce an algorithm based on pessimistic discounted value iteration enhanced by a novel quantile clipping technique, which enables the use of a sharper empirical-span-based penalty function. Our algorithm also does not require any prior parameter knowledge for its implementation. Remarkably, we show via hard examples that learning under our conditions requires coverage assumptions beyond the stationary distribution of the target policy, distinguishing single-policy complexity measures from previously examined cases. We also develop lower bounds nearly matching our main result.

Optimal Single-Policy Sample Complexity and Transient Coverage for Average-Reward Offline RL
Matthew Zurek
Guy Zamir
Department of Computer Sciences University of Sasconsin-MMadion matthew. zurek@xisc.edu
Department of Computer Sciences
University of @zamirQwisc.ddu
Yudong Chen
Department Computer Sciences University of Wisconsin- Maddison yudongchen@cs wisc. edu
Abstract
We study offline reinforcement learning in average-reward MDPs, which presents increased challenges from the perspectives of distribution shift and non-uniform coverage, and has been relatively underexamined from theoretical perspective. While previous work obtains performance guarantees under single-policy data coverage assumptions, such guarantees utilize additional complexity measures which are uniform over all policies, such the uniform mixing time. We develop sharp guarantees depending only on the target policy, specifically the bias span and novel policy hitting radius, yielding the first fully single-policy sample complexity bound for average-reward offline RL. We are also the first to handle general weakly communicating MDPs, contrasting restrictive structural assumptions made in prior work. To achieve this, we introduce an algorithm based on pessimistic discounted value iteration enhanced by novel quantile clipping technique, which enables the use of sharper empirical-span based penalty function. Our algorithm also does not require any prior parameter knowledge for its implementation. Remarkably, we show via hard examples that learning under our conditions requires coverage assumptions beyond the stationary distribution of the target policy, distinguishing single-policy complexity measures from previously examined cases. We also develop lower bounds nearly matching our main result.
Introduction
Reinforcement learning (RL) has achieved impressive results for many control problems where it is possible to collect large amounts experience through online interaction with the environment. However, many real-world application areas where we would like to apply RL methods, such as robotics, education, or healthcare, there may not exist simulators and data collection can be expensive dangerous. Offline RL is subfield of RL which seeks address these issues by learning from historical data without online interaction, and hence achieving the maximum possible statistical efficiency is the paramount concern. The lack of online experience collection poses many related challenges to offline RL methods. One issue, often termed distribution shift, is that improving policy's 's performance will inherently change the distribution of states and actions it experiences, potentially moving it away from the distribution of the historical dataset. Another closely related issue, sometimes referred to non- con-uiiform coverage, is that our dataset may generally be unevenly
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

concentrated so that it is impossible to estimate the performance of all policies to uniform accuracy, and instead we must balance exploitation with varying degrees of confidence.
Recent research has made significant progress on the theoretical limits of offline RL by addressing these issues. However, many of these advances have been confined to the finite horizon setting, or the discounted infinite horizon setting, which can also behave like finite horizon due to the irrelevance of distant future rewards. In this paper we focus on the challenging average-reward setting where the goal is to maximize the long-term average of rewards, which has been underexplored from a theoretical perspective. We briefly argue that the two aforementioned difficulties are amplified in the average-rewarr setting, and have not been satisfactorily addressed by previous work. First, since the average-rewarr objective captures performance in the long- long-horizon limit, we must contend with distribution shifts that occur after arbitrarily long time scales. Secondly, the issue of non- uniform coverage is magnified because while the (effective) horizon can serve as an extrinsic upper bound on the complexity of a particular policy, in the average-reward setting different policies can have arbitrarily different intrinsic complexities (as measured by parameters such as the span of the policy's 'ss relative value function). Existing work has developed algorithms which succeed under single-policy data coverage assumptiios/connentabbili also using parameters that upper bound the complexity of all policies. Such large uniform-policy complexity measures can lead to vacuous bounds and overall fail to fully address both of the above issues. Additionally, algorithms from prior work fail to obtain optimal statistical efficiency and require foreknowledge of unlearnable parameters (such as coverage coefficients or environmental complexity parameters) for their implementation.
coefficients, but has only done so when
1.1 Our contributions
We address all of these challenges, developing an algorithm for (single-policy coverage) offline average-reward RL which is the first to handle the weakly communicating setting where not all policies have constant gains, as well as the first to obtain a convergence rate dependent on the bias span of only the target policy (as opposed to uniform complexity measures). Informally, our main theorem provides a
guarantee on the suboptimality of the output policy ß. of the form
10 - S
50(v
Issun
(1)
m
where ||/" Issan is the bias-span of the target policy nt and S is the number of states. This holds whenever the sample size n(ss a) per state-action pair (s, a) satisfies n(ss, n (s)) 2 mp" (s) - Ö (P, for all states Here 10" is the stationary distribution of the target policy, is the "effective dataset size," and Thit PP, x²) is a novel policy hitting radius that measures the time for x** to reach a particular state in the support of its stationary distribution, and thus also a single-policy complexity measure.
Interestingly, this condition requires data even for state-action pairs (s, (s)) for which s is transient (u" (s) 0) under the target policy, and we show via hard example that this requirement is nearly unimprovable. In particular, this implies two surprising findings: i) with fully "single-policy" sample complexity, learning a near-optimal policy is impossible under coverage conditions with respect to only the stationary distribution of the target policy, even with arbitrarily large amounts of data; ii) on the other hand, only a bounded amount of data from the transient state-action pairs of the target policy is sufficient to achieve vanishing suboptimality. We also show another lower bound which implies the optimality of the guarantee (1) in terms of its dependence on m, making our result the first among offline average-reward RL approaches to achieve an optimal rate for large m.
Our algorithm is based upon pessimistic discounted value iteration procedure, involving very large and prioo-knowledge-ffi free choice of discount factor. Most notably we develop a quantile clipping technique which enables the use of a sharper empirical-spane siitcal-saaa-bbssee based penalty function.
1.2 Related work
First we discuss prior work on average-reward offline RL. To the best of our knowledge the only works with explicit results for this setting are Ozdaglar et al. [2024] and Gabbianelli et al. [2023]. Ozdaglar et al. [2024] assume that the MDP is unichain, and obtain guarantees with a constrained linear

---

programming (LP) algorithm in terms of the uniform mixing time Tunif (defined in Section 2), for both general function approximation and tabular settings. We also discuss quantitative comparisons to the tabular results from Ozdaglar et al. [2024] after presenting our main theorem. Gabbianelli et al. [2023] assume that all policies in the MDP have constant (state-independent) gain, which is more general than unichain MDPs but does not hold in weakly communicating MDPs. Gabbianelli et al. [2023] consider the linear MDP setting, develop an algorithm based on primal-dual methods for solving LPs, and obtain guarantees in terms of a uniform bound on the span of all policies Huiif- The algorithms in both of these works require knowledge of certain concentrability coefficients.
Next we briefly discuss related work for offline RL outside of the average-reward setting. Our algo- rithm is essentially a careful refinement of the pessimistic value iteration approach of Li et al. [2023] for the discounted tabular setting, which in turn is a refinement of Rashidinejad et al. [2022]. Many works (e.g.. Liu et al. [2020], Jin et al. [2021], Xie et al. [2021], Uehara and Sun [2021]. Rashidinejad et al. [2022]) have demonstrated the ability for pessimistic approaches to address the distribution shift/non-unifore coverage challenges of offline RI. and achieve near-optimal performance under single-policy concentrability assumptions.
Finally we discuss prior work on average-reward RL under uniform coverage assumptions. Many papers on average-reward RL considering the tabular generative model setting [Kearns and Singh, 1998] actually only require a dataset with an equal number of samples from all state-action pairs (e.g.. Wang et al. [2022, 2023], Zurek and Chen [2024, 2025a.b]), and hence we believe such papers could be easily extended to the uniform coverage setting. obtaining a guarantee dependent on the smallest number of samples for any state-action pair. While such works might be considered offline RL, we reserve this term for guarantees involving only single-policy coverage assumptions. Achieving instance-dependee guarantees in terms of the bias span of an optimal policy (e.g., Zhang and Xie [2023], Wang et al. [2022], Zurek and Chen [2025b]) and removing the need for prior knowledge of complexity parameters (e.g.. Jin et al. [2024], Neu and Okolo [2024], Tuynman et al. [2024], Zurek and Chen (2025a]) have been the objectives of extensive research in the uniform coverage setting.
2 Background and problem setup
2.1 Background
A Markov decision process (MDP) is tuple AS where S and A respectively denote the finite state and action spaces, P S x A + A(S) is the transition kernel (with (S) denoting the probability simplex S), and [0, 1 1saA is the reward function. We let S = [8| and A |A|-- We generally omit the explicit reference to S and A when defining MDPs. A (Markovian//staionaary policy is mapping π.: S + (AA). We call a policy deterministic if for all s E S. T(s) only places probability mass on one action, and in this case we also treat as mapping S - A. Let II denote the set of all stationary deterministic policies. An initial state so E S and policy π induce a distribution over trajectories (su. Ao. S1, .I....) where A, ~ (Si), S ~ P(- St. At), and we let ET, denote the expectation with respect to this distribution. We often treat P as an (S x A)- matrix where Pan.s' = P(8' 18, ss,)), and let Psa denote the sa-th row of this matrix (treated as "row vector". so X = E. Psa (sa(s') (s') for X R.S). For X RS and & S,a a E A, define the next-state value variance V.... [X] = =EVES P(s') s,a) - (ESES P(s' s, as))
A discounted MDP is a tuple (S,A, 7,r,7) where 7 E 10.1) is the discount factor. For a policy t, the discounted value function V. E [0, - e is defined V.7 (s) = E 1E 72 R2) where R² r(S,, A.), and the gain p² E [0, 1js, is (s) C-lim; D [R.] limy T R&] where C-lim is the Cesaro limit. We define the optimal gain p² = sup p², and we say a policy π gain-optimal if pT = p² A gain-optimal policy always exists [Puterman, 1994]. The bias function of a policy n, hTT E R is he (s) = C- E7 1' (R. - p² (S.))).
T-
M 12S + RS denotes the action maximization operator where (Q) = max.5.A Q(s a) and M denotes the policy matrix where (Q) = EnsA ((s)(a)((ss a), for any Q E S E S, and policy We often drop the parenthesis and write MQ = M()) For any Q E SSA the discounted (action-value) Bellman operator T SRS - 5xA is T(Q) == r + (PM()). and the policy-evaluation Bellman operator 7 is T (Q) : 7PM Q. for any policy
3

---

Let N = 21, denote the set of natural numbers. Define 0, 1 as the all-zero and all-one vectors, respectively. For X E R let || max,es X() min (() denote the span semi- norm. We use Ō(.), (c)). (-)) notation to ignore constants as well as logarithmic factors in S, 1- 8 and Maot. where 8 and Nitot are the failure probability and the total dataset size, to be defined below. Let Cs E R$ denote the vector which is all zero except for a in entry E S. For two vectors v, E IR. v 2 r' denotes the elementwise inequality v()) 2 (i) for all i.
1 1
Under the transition kernel P, policy π induces a Markov chain over state S, whose transition matrix is denoted by Px. The policy π is said to be unichain if it induces a unichain Markov chain, meaning that the chain consists of a single (irreducible) recurrent class plus a possibly empty set of transient states. An MDP is unichain if all deterministic policies in the MDP are unichain. An MDP communicating (aka strongly connected) if for any pair of states s, s' E S. s' is accessible from meaning there exists some policy and some k E N such that (S) = 8') > 0. An MDP is weakly communicating if consists of a set of states S. such that, for any s' E Se, is accessible from 8, plus set of states S, = S \ Se which are transient under all policies. All unichain and communicating MDPs are weakly communicating.
A unichain policy has constant (state-independent) p", and thus in unichain MDPs, all policies have constant gains. In weakly communicating MDPs, the optimal gain p² is constant, but sub-optimal policies may have non-constant p". For any unichain policy オ. we write its (unique) stationary distribution as μ²" E R (which we treat as "row vector"). For any unichain policy x, we define its mixing time T(T) = inf(t 2 0 ||e_ Pt μ² S } Define the uniform mixing time as Tunif = sup*en TTT). Also define the uniform span bound Humit = suP || For any s S, let 7/s- = in 2 : St = s} be the first hitting time of state s. Define the diameter
D = sees min E [, and we sometimes write Dp to emphasize the dependence on P.
2.2 Offline RL. setting
We assume sample size function n S A N is fixed priori, and for each E S, E A, we assume that have n(s, a) samples S1 s.0t--.; spp(sa) sampled independently from the next-state transition distribution P(- 18, a). We define the dataset D ((s, a, Siaa)) aaS, A.ISisn(s.a) and let Noot ExES,aeA n(s, a) denote the total dataset size. We assume the reward function r is known.
We introduce a new quantity which plays key role in both our main theorem and our lower bounds. For any transition kernel matrix and policy æ, we define the policy hitting radius
Thit (P, x) == inf sup ET [.-]. E* soES
(2)
where again 7) is the first hitting time of state s. In words, Thit (P, T) measures the largest expected amount of time required to hit the "center" state s*, for the optimal choice of s* (which will always be a recurrent state). As shown in Lemma 10, Thir(P, R) is always finite if Pz is unichain. We also always have that ||4* Ilspan 4Tise (P, π) for any ı (Lemma B3).). There is generally no relationship between Thi (P, T) and T ( see the discussion in Appendix B.5.
3
Main results
3.1 Algorithm
First we describe the algorithm used to obtain our main result. We employ a discounted reduction approach, i.c., approximating the average-reward MDP by discounted MDP with an appropriate choice of discount factor. The main component of our approach, Algorithm 1, is a pessimistic value iteration subroutine which can be understood solving a discounted MDP.
Now we define the pessimistic Bellman operator Ppp
S + S used in Algorithm 1. Tpe is a function of y as well as the dataset D, utilizing the empirical transition matrix P where P(s' 8, 8,a) n[s.a] ((s.a)) T(S ='). If n((s a) 0 for some 8, then for concreteness we

---

Algorithm I Pessimistic Value Iteration With Quantile Clipping
input: Dataset D, reward function r, discount factor 7 E (0, 1), failure probability å (0,
1: Form empirical transition matrix P used in Tpe from D
2: Let Qo 0 and K
log(
> initialization and number of iterations
3: for = 1...., do
4: Let Q: Te (Q111)
5: end for
6: Let Q = Qx and for each s E S, let (() a
7:
return ?
define P(s' s, = 1/S, although any default probability distribution over S would be fine, since our construction of The does not depend on rows Pss. such that n(s, a) = 0.'
For any Q SxA and any E ESSaa E A, we define
Fno (e) == r(s, a) + max PaoTBcc.a) (Pa. MQ) - b(8, a, MQ), min(MM))))) (3)
Here MQ E S takes the maximum over actions of the Q-function Q (and thus should be understood the corresponding value function). The term b(s, a, MQ) is certain Bernstein-style penalty, which chosen below to ensure that T (Q) lower-bounds the true (unknown) Bellman operator T(Q) for any Q. The expression (a MQ) denotes the inner product of the probability distribution P.a. with the vector To(,,a) (Psn, MQ) E RRS, which is "quantile-clppped" version of MQ to be defined momentarily. For B E [0, 1]. the quantile clipping operator Tg IR$ x R$ + R
defined as follows: for any V E R.S. S, and probability distribution μ E IR let
Ta(u, () = min V(),, sup { ((d)): :8 ES,
E
m(s') 2 3 }}
(4)
In words, all entries of V larger than the (largest) 1 - 3 quantile with respect to are clipped down to this quantile. To extend the definition 3 1, we set [H, () min Vss),, that is all entries will be clipped to the minimum entry of V. Finally we define the penalty term
b(x, a, V) = max {
((s.a) aV P... (P v)] 3.,(8, Tsto.a) (P... V span
5
+
(5)
noat
where a = log GS (GS"AAm Anrar (1-7)0 and ((s,a)= max(m(s.a)-I.f) Note that ((s, a) = Ö (
(when-
ever n( a) > 0).
The pessimistic Bellman operator Tpe has several nice properties that are crucial to our analysis.
Lemma 3.1. 7pe satisfies the following:
1. Monotonicity: If 2 Q' then F (Q)).
Tpe
2. Constant shift: For any E IR, (Q + cl) = F (Q) 77l..
3. 7-contractivity: Tpe is y-contraction and has a unique fixed point Qú E 10,, 10-1)
See Lemma B.1 for a more complete statement. In summary, like previous pessimistic value iteration approaches [Li et al., 2023, Rashidinejad al., 2022], our pessimistic Bellman operator shares key properties with usual Bellman operators enabling us to find an approximate fixed point in Ō 2 value iteration steps, and then we will choose policy ß to be greedy with respect to this fixed point.
Now we discuss the motivation for quantile clipping, and the differences from prior work. In particular we highlight the constant shift property enjoyed by Tpe. This is highly desirable for the average-reward
If m(s a) = 0 then 3(s, a) = a > 1 and Tpc,, (P.., MQ) = (min. (MQ)()))) causing the max in (3) equal (MQ)
5

---

setting, and more generally any weakly communicating MDPs, since in such MDPs the optimal value function behaves Vi p and p" is multiple of The constant shift property essentially guarantees that we only penalize the variability in the relative value differences between states, not the overall horizon-dependent scale I- of the cumulative rewards. The - -aan second term in penalty function definition (5) of 6 is essential for this constant-shif property, since the span semi- norm is invariant to translation by multiples of 1. Previous pernstein-stylee penalty functions [Li al., 2023] a larger term like ((s, a) T- n(s,a) I-y' which breaks the constant shift property and can dominate the first (variance-based) term in (5) when used with large horizons. Naively using ((s. span in the second term of (5) actually fails to ensure the monotonicity and contractivity properties of pe- for reasons that we elaborate upon in Section 4, Fortunately, the introduction of quantile clipping remedies these issues, and only introduces small additional bias: since only entries representing at most 3(x,a) O ((e.a) of the probability mass with respect to Psa have their
values clipped, we have (ssTa( introducing quantile clipping within the two terms of the penalty function b in (5) only reduces the penalty value, relative to instead using V Vp,.. [V] and Vllsppn (See Lemma 1.14.)
(ss.a) (Pea, V) PsaV < PeoTe(s.a) V) + B(ss a) ||V'llpann and
3.2
Main theorem
Now we present our main theorem on the performance of Algorithm We will apply Algorithm with very large discount factor such that the effective horizon is 1 1-y Niot-
Theorem 3.2. There exist absolute constants C1, C2 such that the following holds: Fix 8 O. Let y = =
and a 8 log (65* Amict) ). Let n² be deterministic gain-optimal policy which is (1-7)6
Piot
unichain with stationary distribution p² Suppose there exists some m E IN such that
n(s, (+)) 2 mp" (s) + a (C2Thin (P, x x²))²
and ö, we have Then letting be the policy returned by Algorithm I with inputs D, r, 7 Renet with probability at least 1 56 that
CiS(IhT pp
Ipan + 1)a
m
We prove Theorem 3.2 in Appendix B. Theorem 3.2 demonstrates that the "effective dataset size" m increases, the suboptimality of decreases at rate of Ö( S| /apun/mm,, which matches our lower bound Theorem 3.4. Our coverage assumption is qualitatively different than previous works on average-reward RL, since even for states s which are transient under x (and thus have μ² (s) = 0), still require Ö(Thie (P,, ?)) samples from the state-action pair (s, nT" (s)). Note that up log factor this transient state coverage assumption independent of m, meaning that vanishing suboptimality is possible with only an essentially bounded amount of data from transient states. (In the absence of this additional term we could treat Neot / as a "concentrability coefficient" similar to prior work, but we believe results As shown in Theorem 3.3, this transient data requirement is necessary to obtain || Ilapan -bsed guarantee, and our dependence on The (P, x²) is nearly optimal. Theorem 3.2 requires x" to be unichain, which is mild assumption, since policies are unichain, there always exists a unichain gain-optimal policy [Bertsekas, 2018].
stated more clearly in terms of the effective dataset size m.)
in weakly communicating MDPs where not all
No prior parameter knowledge, such of || Ilspan or the value of m (or equivalently a coverage coefficient) is needed for Algorithm to be implemented and enjoy the above guarantee. In particular y is set so that the effective horizon is noot Actually our theorem would hold for arbitrarily larger choices of the effective horizon, and the guarantee would not degrade except for logarithmic dependence on the effective horizon, but this would be suboptimal from a computational perspective, since Õ(1/(1 - 7)) iterations are required for convergence in Algorithm 1. Also see Theorem B.20 for version of Theorem 3.2 allowing x² to be gain-suboptimal.
al. [2024] obtain a suboptimality bound like Ö( Sf where C 2 1 is a certain coverage coefficient roughly equivalent to Pro/mm. With this substitution their bound becomes Ö( / T S/mm, which interestingly degrades with the
In the unichain tabular setting, Ozdaglar

---

coverage coefficient C even as the effective dataset size m is held constant, while our bound has no such issue. We also have || apan I (Tunit), and qualitatively ||/" [|span is much sharper since it depends only on x¹ rather than all policies.
3.3 Lower bounds
In this subsection we present two lower bounds implying the vear-optimality of our Theorem 3.2. Below, for an MDP (Po. r), Po big and μi denote the gain, bias and stationary distribution of policy T, respectively; Pg and Dg denote the optimal gain and the diameter of the MDP, respectively; and Po,n denotes the distribution of the dataset DD under this MDP when the sample size function is n.
First, we present the surprising fact that, to obtain convergence rates dependent on certain single- policy complexity measures including ||A* spsn and Tie (P, π²), coverage assumptions with respect to only the stationary distribution of the target policy are insufficient to learn a near-optimal policy, even with an arbitrarily large amount of data.
Theorem 3.3. For any T 2 4 and any m E N, there exist a finite index set O, transition matrices Po for each 0 E θ and reward function v, such that for all ó E (0, } there exists a function n : S x A - N satisfying the following:
1. For each A E θ the MDP (Po,r) is unichain and communicating, with A s O ([ actions and diameter T.
2. For each 0 E O the MDP (Po,r) has a unique deterministic gain-optimal policy To such that This ( m²) S T and n(s, (T)ss) 2 mp T (s) + +T log (t) for all s E S.
3. For any algorithm of that maps the dataset 'D to a stationary policy, we have max Po.m (pá Pg (D) 1/2) 2 8. OEG
Note that the "effective dataset size" parameter m can be taken arbitrarily large, meaning that learning better than a 3 -suboptimal policy is impossible even with arbitrarily large amounts of data from the stationary distribution of the target policy. This does not contradict the error bounds from prior work which make
distiorrrry-tttibuttooonn based coverage assumptions and involve uniform complexity mea- sures Tunif, Hunif [Ozdaglar et al., 2024, Gabbianelli et al., 2023], since the parameters Tunif, Hunif scale with m in our hard instances in such a way as to render such bounds vacuous. In contrast,
the parameters | || Ipan; That m)), and Dg remain bounded, implying that a convergence rate involving any of these parameters is impossible without data coverage beyond the stationary distri- bution, revealing qualitatively different behavior of such parameters. While oftentimes results for average-reward setups can be predicted/derived by taking appropriate large-y limits of results for discounted settings, taking the limit + 1 of usual discounted occupancy coverage assumptions (e.g.. C* in Rashidinejad et al. [2022, Theorem 6]) only leads to requirements on covering the stationary distribution.
The setup in Theorem 3.3 even provides the learner with ([Thi (Pe, samples from state-action pairs which are transient under the target policy (11 = (s) = 0), and this is still insufficient for learning near-optimal policies. This implies that the transient state dataset coverage requirement of Theorem 3.2 is nearly unimprovable. up to an additional factor of (T r))) A complete proof of Theorem 3.3 is provided in Appendix C and a sketch is provided in Section 4, but we briefly summarize the key idea: even with an arbitrarily large (but finite) amount of data from the recurrent class of the target policy, we may inevitably learn a policy with small probability of leaving these well-covered states. Without any data we cannot learn how to recover from such a transition and navigate back to rewardie regions quickly enough. This unfavorable but rare transition has negligible impact for tinite horizon/discounted RL objectives (if the starting state is within the -ewariree region). In unichain MDPs all policies are guaranteed to eventually return to the recurrent class of the optimal policy eventually (because all recurrent classes must overlap, otherwise it would be possible construct multichain policy), but the fact that some policies take long time to do so means that the uniform mixing time Tunit is very large, even if the optimal policy can recover quickly. Despite being unichain, such MDPs are qualitatively close to being non-unichain (but weakly communicating.
Next, we present lower bound which demonstrates that dependence on in Theorem 3.2 is tight.
7

---

Theorem 3,4. There exist absolute constants C1, C2, > 0 such that for any T 2 c1. S 22 0. and m 2 max(T'S kS), one can construct finite index set Q transition matrices Po for each 0 E O reward function and function n : S x A - N such that the following hold:
1. For each 0 E ④ the MDP (Po,r) is unichain and communicating, with S states and diameter T.
2. For each 0 O the MDP (Pe,r) has unique stationary gain-optimal policy zh such that Thit Tb) S T and n(s, (T)) 2 mpp zo (s) + k for all s E S.
3. For any algorithm sf that maps the dataset D to a stationary policy, have
max Fo.n 8EB
PD
Po
(D)
ca
TS
(6)
64
Since generally Thin 2 |1A** span 4 (see Lemma B.13), Theorem 3.2 implies lower bound in
R0 |ssan and (Pa, mī) are on the same order in the instances of Theorem 3.4). We add the parameter Is to demonstrate that coverage requirement in the form of Theorem 3.2 does not affect the dependence on m in (6) for sufficiently large m. In particular after setting
terms of ||/" /1
A @(T²) to match Theorem 3.2, its dependence on ||/= Il S, and matches (6) and thus is
unimprovable up to Ō() factors as long as m 2 S). Theorem 3.4 proven in Appendix D.
Proof sketches
4.1
Main theorem
First we discuss the proof of Theorem 3.2, including the motivation for quantile clipping. The key idea of pessimistic value iteration is to choose T,e so that Tpe (ee(epe) S T(Qpp)) and then letting स be greedy with respect to Qpe (meaning T(ppe) T (Qpe)) we have
@.o T Poo (pie) S T(@;)) pe = TT (8tt))
so by standard monotonicity arguments we have Qi SQ² The challenge is then choose Tpe as "close" to T as possible, so that Q7. is close as possible to Q* (while ensuring Tpe ( I T(Pp))) in order to maximize Q*. Using a to hide Ō(-) terms, an empirical Bernstein-lic like bound [Maurer and Pontil, 2009] for the quantity D. M@per and upper-bounding sum by max, yields
'e
7 pc
Pau V. pe 2 Peo DA max
20
pe
span
=: Poa V.- - -b(s,a, Vpc) Vs, a. (7)
a
a) n((sa) a)
This sharp span- based form of penalty function i is crucial for the constant shift property described
in Lemma 3.1, since both Vp [t] and I-Ilsgan are invariant to shifts by multiples of 1. As discussed there this property is essential for the average-reward setting, and the Bernstein-style penalty used in Li et al. [2023] replaces the second term from the max in (7) with - 2 II pe Il and hence does not enjoy this property. However, we cannot simply use an operator like T(Q) a) = r(s, a) + P Vr= --((s, a, V because the span term within would lead to non conoooottyyycty of T and disrupt many other essential properties (like 7-contractivity). To see the non-monotonicity. suppose some s' has P(s' s,a) < n(s.a). Then, for V E R$ where V(s') is the largest entry, ignoring non conddifferentiabbiiyy edge cases, we have
d d (PavV- [IVllpm dv(s') (PaV- V(s') min V(s") n(s.a)
n(s,a) (
(s')
P s,
a 0.
n n(s, a)
8

---

However, if we replace V with the quantile-clippe quantity Ta /a/n( (P.,o V), then increasing Vis') (when the largest entry of V) will only increase Ta/n(s,a) (Pa.a. a. V) P(s' 8, a) has at least (s, a) probability mass. Hence, by fixing the overpenalization caused by II-Ilspan quantile clipping is essential to define our empirical-span--aseeeee basedd pessimistic Bellman operator.
Now we discuss a few other aspects of the proof of Theorem 3.2. Obtaining the Bernstein-style
inequality (7) is nontrivial due to statistical dependence between P and pe- We remedy this with an MDP techniques [Agarwal al., 2020], which requires additional covering steps due to the presence of quantile clipping. (See Lemmas B.6 and B.5.)
argument based on
It is somewhat surprising that Theorem 3.2 is able to obtain bias-span-based guarantee without requiring any prior bias-span knowledge, since prior work in related uniform coverage settings has shown this is impossible when the effective horizon is large/on the same order the size of the dataset [Zurek and Chen, 2024]. This is closely related to the issue that the bias span ||t Ip of a policy π is not estimable to multiplicative error with a sample complexity polynomial in only S, A, and | |span [Zurek and Chen, 2025b, Tuynman al., 2024]. However, our proof suggests that ||h" estimable if we allow a dependence on the policy hitting radius Thi (P. T), which we believe is an independently interesting finding. (See Lemma 181 This fact plays key role in bounding the suboptimality in terms of [/]] span
4.2 Transient lower bound
Next we briefly describe the idea behind the hard instances within Theorem 3.3, which implies that transient coverage is required for offline RL with single-policy complexity parameters. Consider the MDP P in Figure 1, which is parameterized by m, which we imagine as arbitrarily large, and T, which we imagine measuring the complexity of P. There are two states with actions each, an absorbing stay action and leave action which has a small chance of leading to the other state. State has reward 1 for both actions and state 2 has reward O for both actions, clearly the optimal policy x² is to take leave in state 2 and take stay in state 1, and the associated stationary distribution has all its mass on state 1. Also, assuming m > T. Thit (4, x*) T, since this is the expected amount of time to hit state starting from state 2. Therefore to satisfy the coverage
assumption ns,s, x² (s)) 2 my"" (s) + Thi (P, x²), would suffice to provide m samples for both state 1 actions, and T samples for both state actions.
a leave, R ===10
stay, R 0
a leave, R R=
stay, R
1
2
stay, R =1
0 leave, R =0
a = stay, R =
leave, R = 0
P
P
Figure 1: An MDP P parameterized by m, T, and an empirical MDP P which has constant probability of being sampled from P. Each solid arrow indicates an action and is annotated with its reward. Arrows which split into multiple dashed arrows indicate possible stochastic transitions, and each dashed arrow is annotated with the associated probabilities.
For this sample size function n, with constant probability we will not observe any transitions the other state from either of the leave actions (that is, the samples from each of these state-action pairs would all be of the form (s, leave, s)). Under such an event, illustrated by the empirical MDP P, no algorithm could distinguish between the leave and stay actions in either state better than random guessing. If an algorithm is forced to return deterministic policy, then there would be a constant probability of choosing the policy where (=(1), (2)) = (leave, stay), which will remain in state 2 (and hence have gain 0). To generalize to algorithms which may choose randomized policies.

---

we add more copies of the stay action to state 2, so that "guessed" randomized policy has a low chance of returning state 1 quickly enough for good performance. Also P is not unichain, but we can add an arbitrarily small (O(m-2)) probability for the stay actions in state 2 to return to state which ensures unichainedness without meaningfully changing the story. We emphasize that the hardness is not due to the inability to identify the stay action in state 1, since in general we cannot expect to perfectly match the stationary distribution of the target policy (and this example, the policy (leave, leave) still has suboptimality only O(T/m)). Rather, the hardness is due to the fact that it nontrivial to navigate (quickly) back to the target policy's s stationary distribution after leaving it, and learning to do requires data coverage beyond said stationary distribution.
Conclusion
We developed the first wverage-rewart offline RL algorithmms for MDPs where not all policies have constant gain, and also the first convergence rates depending only the bias span of single policy. main limitation of our work is its focus on the tabular setting, hence an important direction is to extend these improvements to function approximation setups avoid dependence S in the results. While Theorem 3.3 demonstrates the necessity of data from the target policy from all states, this may be limiting in practice, so interesting future direction is explore additional assumptions or information that could be provided to the algorithm to circumvent this requirement.
Acknowledgments and Disclosure of Funding
Y. Chen and M. Zurek acknowledge support by National Science Foundation grants CCF-2233152 and DMS-2023239.
References
Alekh Agarwal, Sham Kakade, and Lin F. Yang. Model-Based Reinforcement Learning with a Generative Model is Minimax Optimal, April 2020. URL http::///arxxi org/ ha/abb//1999 /1966 03804. arXiv:1906.03804 [cs, math, stat] version: 3.
Dimitri P. Bertsekas. Approximate dynamic programming. Number volume 2 in Dynamic pro- gramming and optimal control Dimitri P. Bertsekas, Massachusetts Institute of Technology. Athena Scientific, Belmont, Massachusetts, fourth edition, updated printing edition, 2018. ISBN 978-1-886529-08-3 978-1-888529-4411..
David Cheikhi and Daniel Russo. On the Statistical Benefits of Temporal Difference Learning. In Proceedings of the 40th International Conference on Machine Learning, pages 4269-4295 PMLR, July 2023. URL https: httpppsss///cceeedeeeeee mlr 2640-3498.
htwp:inss.........//eeeeeee.seee www.erreeesavvee cheikhi23a html. ISSN:
Richard Durrett, Probability: theory and examples. Cambridge series in statistical and probabilistic mathematics. Cambridge University Press, Cambridge, fifth edition edition, 2019. ISBN 978-1- 108-47368-2.
Germano Gabbianelli, Gergely Neu, Nneka Okolo, and Matteo Papini. Offline Primal-Dual Rein- forcement Learning for Linear MDPs, May 2023. URL. arXiv:2305.1221 12944 [es].
wwwerrvwv....r..eeo org//ogg/////ooooooooooooooe 2305. 12944.
Ying Jin, Zhuoran Yang, and Zhaoran Wang. Is Pessimism Provably Efficient for Offline RL? In Proceedings of the 38th International Conference on Machine Learning, pages 5084-5096. PMLR, July 2021. URL https:://// settp::/ppoceedinngg mlr
vttp//vvv/jjj// (ta//////nnnnniee html. ISSN: 2640-3498.
Ying Jin Ramki Gummadi, Zhengyuan Zhou, and Jose Blanchet. Feasible SQ$-Learning for Average Reward Reinforcement Learning. In Proceedings of The 27th Internutional Conference on Artificial Intelligence and Statistics, pages 1630-1638. PMLR, April 2024. URL https: // //proceedings.. mlr, pwwss/evs33 http///3//jji/j j html. ISSN: 2640-3498.
10

---

Michael Kearns and Satinder Singh. Finie-Sample Convergence Rates for Q-Learning and Indirect Algorithms. In Advances in Neural Information Processing Systems, vol- ume 11. MIT Press, 1998. URL https: /ttpc//eppoeeceseee/eepepce www.:iiinnnnnn.is...oum www.iee.....ppaeeeeee hearrpppscc/pppe///1///aaaaaa (addd4665500002995000000222.022
Abstract hhtml.
John G. Kemeny and J. Laurie Snell. Finite Markov chains. Undergraduate texts in mathematics. Springer-Veriee New York, 1976. ISBN 978-0-387-90192-3..
Gen Li, Laixi Shi, Yuxin Chen, Yuejie Chi, and Yuting Wei. Settling the Sample Complexity of Model-Based Offline Reinforcement Learning, February 2023. URL http: /wwpvv.//vvvvvva////////a///aav org/ abb/ 2204. 05275. arXiv:2204.05275 [cs, eess, math, stat].
Yao Liu, Adith Swaminathan, Alekh Agarwal, and Emma Brunskill. Provably Good Batch Off-Policy Reinforcement Learning Without Great Exploration. In Advances in Neu- ral Information Processing Systems, volume 33, pages 1264-1274. Curran Associates, Inc., 2020. URL https://prrcceediinng neurips wwwurpps.cc/iie /pappraper.//e cc//pappe_fiieee www.fflllsppppee wttps/apppp///////aa//ae/e 0c2210aaee401399995Bddfffadad Abstratt.ssttt......e... html.
Pascal Massart, Concentration inequalities and model selection: École d' Ete de Probabilites de Saint-Flour XXXIII 2003. Number 1896 in Lecture notes in mathematics. Springer-Verlag, Berlin New York, 2007. ISBN 978-3-540-48503-2.
Andreas Maurer and Massimiliano Pontil. Empirical Bernstein Bounds and Sample Variance Penal- ization, July 2009. URL http:///rxixx org/abg/ hts//bb/0000 0907 3740. arXiv:0907.3740 [stat] version:
Gergely Neu and Nneka Okolo. Dealing with unbounded gradients stochastic saddle-point optimization, June 2024. URL http://arxiva ottg///s/////.....././/// 13903. arXiv:2402.13903 [cs, math, stat] version: 2.
Asuman Ozdaglar, Sarath Pattathil, Jiawei Zhang, and Kaiqing Zhang. Offline Reinforcement Learning via -rooar--no with Error-Bound Induced Constraints, December 2024. URL http://arxive http:/axxivvorrgaaaa/ org. abt//2/b2222222 13861. arXiv:2212.1385 [cs].
Charles Chapman Pugh. Real mathematical analysis. Undergraduate texts in mathematics. Springer, Cham Heidelberg, 2. ed edition, 2015. ISBN 978-3-319-17770-0.
Martin L. Puterman. Markov Decision Processes: Discrete Stochastic Dynamic Programming, Wiley Series in Probability and Statistics. Wiley, 1 edition, April 1994. ISBN 978-0-447--61977-2999 978- 0-470-31688-7,
doi: 10. 00011002/9880470316698777 URL https: http:///onnnnnnnnneeeee www.bbrrrrrwrll..............eee com/
doi/book/ 10 /1t..0000000000770011100000
Paria Rashidinejad, Banghua Zhu, Cong Ma, Jiantao Jiao, and Stuart Russell. Bridging Offline Reinforcement Learning and Imitation Learning A Tale of Pessimism. IEEE Transactions Information Theory, 68(12):8156 156-)88556881 8196, December 2022. ISSN 1557-9654. doi: 109/TTT 2022.3185139. URL https: //ieexxpooreeeeeee///o ieee. org/ (alocummnt/9800255
Slavko Simic. On a global upper bound for Jensen's 's inequality. Journal of Mathematical Analysis and Applications, 441 July 2008. ISSN 0022247X. doi: 10.1016/j, 1aa.10066.jjaaa2000 1maa.2008.00 0000.00.0600
URL https: /tip:::///iiiiigni/iu elsevier.
Adrienne Tuynman, Rémy Degenne, and Emilie Kaufmann. Finding good policies in average-reward Markov Decision Processes without prior knowledge, May 2024. URL http://arxivy org/ abs/2405. 17108. arXiv:2405.17106 [cs].
Masatoshi Uehara and Wen Sun. Pessimistic Model-based Offline Reinforcement Learning under Partial Coverage. October 2021. URL http://///pppeeeeeeeee///o/r//na
Martin Wainwright. High-DDmensional Statistics: A Non-Asymptotic Viewpoint. Cambridge University Press, edition, February 2019. ISBN 17- 10.1017/9781 108627771. URL https://///// http://///.....ccct/or/////////a 9781108627771//ppe/bbo
doi:

---

Jinghan Wang, Mengdi Wang, and Lin F. Yang. Near Sample-Optimal Reduction-basse Policy Learning for Average Reward MDP, December 2022. URL http://arxiv..rrg///////////// /tt.g////////.////////// 00603. arXiv:2212.00003 [es].
Shengbo Wang, Jose Blanchet, and Peter Glynn. Optimal Sample Complexity for Average Reward Markov Decision Processes. October 2023. URL /trrp:://peerrviev.neett
c0m5p3q7c7.
Tengyang Xie, Ching-An Cheng, Nan Jiang, Paul Mineiro, and Alekh Agarwal. Bellman-con consistent Pessimism for Offline Reinforcement Learning. In Advances in Neural Information Processing Sys- lems, volume 34, pages 6683-6694, Curran Associates, Inc., 2021. URL https::/ppoccee:: ings. neurips. cttccc//pppao
wwtp:cccpppppppeeee 200/p/r//22//// http://2222/ahaaha/aaaa (ataa//9991141111111111100000000 Abstract html.
Zihan Zhang and Qiaomin Xie. Sharper Model-free Reinforcement Learning for Average- reward Markov Decision Processes, June 2023, URL http:://rxiiii....////// wwt.aaawww...i.rrr..aa/eaeea wwgg/bs/////////o//e//e/e/ 16394. arXiv:2306. 16394 [cs].
Matthew Zurek and Yudong Chen. The Plug-in Approach for Average-Reward and Discounted MDPs: Optimal Sample Complexity Analysis, October 2024. URL http::ttaa///tt/ org /bss/ ..661. arXiv:2410.07616 [es].
Matthew Zurek and Yudong Chen. Span-Agnostic Optimal Sample Complexity and Oracle Inequal- ities for Average- Reward RL, February 2025a. URL http://arxiv... org/ ha//abbs/20000 11238. arXiv:2502.1 1238 [es].
Matthew Zurek and Yudong Chen. Span-Baser Optimal Sample Complexity for Weakly Communi- cating and General Average Reward MDPs. Advances in Neural Information Processing Systems, 37:33455-33504, January 2025b. URL https: //twee/eeee.eeeee////eeeeec neurips. ttt paper/2024/har Sacbeseeccaaeeddaaaaaoooeeeeeeee Abstract- Conf erence. htmll.
12

---

A Additional notation and guide to appendices
Let be stationary policy. Note that P. (defined above the Markov chain over states induced by policy π on the transition kernel P) is equal to M P. We also define 7 = Mr Then we I1- and |I-11, denote the usual -nomms, respectively, || bo- denotes the |1-1100 - ll operator norm of a matrix W. In particular [] - -+= - -
have V - -
We note that the action maximization operator M and the policy matrix 2 both satisfy monotonicity: V > V (elementwise, for Q. Q' E RSxAA) implies M(Q) 2 M('), and likewise that M 2 M"Q'. These two operators also both satisfy the "constant-
property, that for any C E R and any Q E RSXA we have M(Q cl) cl M(Q) and M/*(2 + cl) cl + M MT (Q). Also we note that M and M" are both 1-Lipschitz with respect to Illl that is | - MQ'Il < IQ Q' and | M 0c & ||Q Q' lox. For any vector x we let z denote its elementwise kth power. We let Il denote the usual indicator function used probability where 11 1(E)) is random variable with value if the event E' holds and 0 otherwise.
In Appendix B we prove the main theorem, Theorem 3.2. In Appendix C we prove Theorem 3.3 and in Appendix we prove Theorem 3.4. Appendix E contains additional supporting results.
B Proof of main theorem
B.1 Well-definedness
We also define a fixed- phee-ppoicyyppolccy evaluation version of Tpo which will be useful within the analysis. For any fixed stationary policy æ, we let
F (Q) a) r(s,a) + max (Ps (saTstsaa)PPa M Q) b(s, M Q), min(MM
(8)
We also define lemma).
v pe
pe where @ is the unique fixed point of Toe (justified in the below M S
The following is more comprehensive variant of Lemma 3.1. Lemma B.1.
1. Tpe satisfies the following properties:
(a) Monotonicity: IfQ 2 Q' then mpe (Q) 2 Tpe
(b) Constant shift: For any e E R. (Q + cc) = Fp) + 7cl.
(c) 7-contractivityy Tpe is a 7-contraction and has unique fixed point Q
(d) Boundedness: 0 S Tr. S 1
2. For any fixed stationary deterministic policy π, the analogous statements hold for t
(a) Monotonicity: IfQ 2 Q' then i (Q) TT)
(b) Constant shift: For any c E R. ( -T) +c1.
(c) y-contractivity: tpr is a c-cottractoon and has a unique fixed point Q pe-
(d) Boundedness: 0 < E < 1
3. For any fixed stationary deterministic policy n, we have Qj. 2 Q
Proof. We note that a few steps are similar to Li et al. [2023, Lemma 1], but our new choice of penalty requires much more involved analysis.
We define an auxiliary operator T R.S. + RAA by, for any V E R.S.
(Pan (PaTT (P.., V) b(s, V), mijn(())))))
pe (V), a) r(s,a) + max
We defer the verification of the following fact, which involves somewhat lengthy calculations, to Appendix E.
13

---

Lemma B.2. Let V, V E R be arbitrary and suppose that V 2 V Then (elementwise)
pe 2 7 (V
Given Lemma B.2, we can relatively easily verify Lemma B.1. We note that Lemma B.2 makes use of the quantile clipping in an essential way.
Now we will show item except for the boundedness property. Notice that (Q) = pe (MQ) (for any Q E RRAA). Therefore letting Q, Q' E RSA with Q 2 Q', we have by monotonicity of M that MQ 2 MQ', and thus by monotonicity of T pe we conclude that
(Q) T (MQ) T po (MQ') (Q')
as desired. Next check the constant shift property of T pe Fix c R, V e R and E S,a E A. Then we have that a) V+cl) = Tote.a) (Pan, V)+cl, regardless of whether [(, a) E [0 or B(s,a) a) > 1, since when B(s, a) 1 we have T)( (Psa. V + +el) min.es(V + +c1]1 (min (V) + c)l, and when ((8, a) < 1, by (4) we have
and
Te(s,a) V +cl((s) min V(s) +c, sup +c:'ES
E
Psa(5') 2 B 8]]
("E
=c+ min { ((s), sup ((ss))s'EE
E Psa 2 B /]
="
c CC+TT(sn) Ta(so)) (Pas ())).
Therefore
Ppn Talaaa(PPa sa. V + cc]]
= Ppp. [Ttaa) V) + cl =Vp (oso v)]
and Tace.a) (Poas V + +c) span
| (Paa: V) + cl = T (Pea: V)
span
and therefore we have that b(s, a, V) blss, a, V cl). Additionally we have that (V cl) (8') min V(5)) +
min
Hence
T Te (V + (c))(s,a) = r(s,a) + max P T (Pa so V + cl) - b(s, V + min + cc)(('))
rr(s, a) + + max (PanToinaa V) v)+ cP.. b(s, V) min()) + +c]
=r(s,a) + yc + max ( (PaaTstana) V) b(s, a, V), *'
minn()(ss)))
+ T po (s) a)
(since 1oo1 1). Using (9) and the fact that M(Q+cl) = MQ + cl show that 7pe satisfies the constant shift property as well:
(Q cl) T (M + el)) = pe c1) = (M() 7e1 (p) ye1
as desired. Finally we can check contractivity of App. We note that it suffices to show that T pe is Lipschiizz since then we would have for any Q1, Q2 E R.S.A that
p. - 7 po ST|MQQ 1MMMQ--MQ2ll+ 57111 Q2
as desired, where the first inequality is due to the (assumed) Lipschitzness of 7 T inequality is due to the 1-Lipschitzness of M. Now we verify that T is indeed -Lpiscciit.. For any V1, V22 S we have V1 S V22 + |[V V2ll.0 1 (clementwise), so by monotonicity of T pe (Lemma
pe and the second
14

---

B.2), and then using the fact that T pe satisfies the constant shift property (shown in (9)) in the next inequality, we have
T pe (Vi) S T pe + 11V V2llo0 1) po + ?l|| V21loo
so by rearranging
T (V1) T (V2) 7 | V2ll 1.
By reversing the roles of V12 and 1/2 we also have
T (V2) T po S >|V 1/2l00
or equivalently
-7 [[V V2lloc S To - pe pe (V2).
inequalities involving (V2)) T (V)) we conclude that pe -V pe22) co < 7 ||V Vollao as desired and thus Te is a y-contraction. By the Banach fixed- sred-ppoittee theorem (e.g. [Pugh, 2015, Chapter 4.5)) this implies the existence of unique fixed point of Tpe. which we call Qpe- (We check that O S Upe - later.)
Combining these
Now will show item except for the boundedness property. Notice that similarly to the previous case, Tpe (Q) T (M*QQ (for any Q E R.AA). The only properties of M used in the proofs for the previous case were monotonicity (that 2 Q'
MQ MQ'), that M(Q + cl) MQ + cl, and that M is I-Lipschitz. All of these properties are also true with M in place of M, so in fact all proofs used verify item I can immediately be applied (with this minor modification) to also verify item 2.
Next, item would follow by showing that for any fixed Q E RAA we have
7pe (Q) Tp (Q)
(10)
since then by a standard argument we can show for any integer k 2 0 that
(Tpe)
(0)
(0)
(where (k) denotes & compositions of an operator) and therefore that
@ lim 100
Tpp
lim {
(0)
Q
So now we focus on showing (10), but this follows immediately from the fact that MQ 2 M and that T pe is monotone (Lemma B.2), since we have
Fp (Q) = (M()) 2 T (M=Q) = F (Q)-
[Mathhew: should be B(s, a) not 3 in the below paragraph?] [Guy: yes] Finally, we check both boundedness properties. Since we already have that Qpe I Qp.. it suffices to show that < Q7. and that Qi. S 1- 1. First, note that have 7,s (0) 2 O, since for any S, E A,
Fr (0)s,, a) = -(ss a) + 7 max { ( (P.. M) - b(s, a, M* min( mmnmmmnm)) O)
2 r(s, a) + minn(m = r(s 2 0.
Then by monotonicity of t. we have for any integer that
(k)
(k-1)
a pe
(0)
7
pe
and so
(A)
230 =
lim
{ pc
(0)
2
000
15

---

as desired. Similarly, we have that (po(1/(1- -7)) - 1 7), since for any s E, Tno - (s))
-r(s,a) 1.7mmm max (i M1/(1 7)) b(s, a, a1/(1 (mn
1
1-?
By an analogous argument to the previous bound, we have from monotonicity of Tpe that (Tre (k)
(1/(1-7)) S 1/(1 -7) for all positive integers and thus that Qpe S 1/(1 7). n
In the above proof we defined the operator T pe and verified its Lipshitzness, which state in the following lemma as T pe will appear again later. Lemma B.3. T is 7-Liscchitz
B.2 Optimization
In this subsection we establish the basic properties of the outputs of Algorithm 1.
Lemma B.4. Algorithm returns Q suchh that
- Qp S Q
and Tpe 2 Q.
2nto
Proof. First we note that (0) 2 0, which follows easily from the definition (3) since (for arbitrary E S,a E A)
(0) r(s, a) + y max {Peo ()s.0) (Po.. MO) b(s, a, MO), min min(M))(s))) 2 r( a) + min (MO) = r(8, a) 2 O.
s'
ppe 2 @ follows from this fact and monotonicity of Toe by standard arguments, since if for any
t tEl N we have that ppe (Q.) 2 Q, then
Tp = Tpp (Tpc 2 ppc (i:)
so by induction (since @ 0)
(pp(( (Qi) 2 Q holds for K, and we have QK Q by definition.
Now we argue that Q s Qie, which follows from ppe ( 2 Q and monotonicity of Tpe by standard
arguments, since assuming for some 2 that 7pd (Q) Q. then we have by monotonicity that
(Tpe)
(++1)
2 TTp
(t) ()) 2 ppe ( 2 Q
and so by induction (TrO)
Q 2 Q for all
2 1, and thus
(1) (@)
i = lim
Tpp
2 lim Q = Q
1+
(+000
as desired.
Finally we check that Q < Q + 2n
1. Again note that Q = QK. By the definition of K
log
2reoo
as well as the fact that log(1/7) 2 1 for any we have
lag
Bugot
1ox
K K log(n)
<e
log(t)
log(1/7)
< log Tureot
21
Using this bound, 7-contractivity, and the fact that 0 < O < - from Lemma B.I, we have
@x - --pipll 5x 10 @ic =x 0 Q 5g 1 1- 2ntot
<
which implies Qic < Q 2neat
1 11. 1.
16

---

B.3 Concentration
In this subsection we establish the key concentration inequalities, given Lemmas B.7 and B.8, using leave-one-out techniques. We start with two helper lemmas which abstractly handle the leave-one-out-base covering steps before proving Lemmas B.7 and B.8.
S, E A. Suppose that for some random vector X E RR, there exists (deterministic) set U and some random variables Xu E E for each (that is, for each E U, Xy, is random vector in R such that
Lemma B.5. Fix some 8' > 0 and some
1. For all U, X,, is independent of all samples , sin(s,a)
drawn from P(: s,
2. Almost surely there exists some u E U such that || Xu- 1lx0
virot
Also assume n(8,0) a) 2 2. Then with probability at least - 60', we have that
log 1///8' + 2n(s, a)
log |0/1/8
(Pan - Paa)X S 1|Ix
1
Yltot
2n(s, ())
(11)
(Paa - PPa) S/
P., [X] log((U1/8")
P..
+ ||
log(1U1/8)
n(8, a)
3n(s,a)
llgg(UU1/88
log(1U1
2
2 3n(8,a)
n((sa)
Thoo
(12)
n((saa) a)
log 101/8'
2 log 10//8'
n(s, a) Vp [X] VV [X]
< || span
2
+
n1ss, a) -1 Thaa
nis,, a) -
(13)
24 P... [X] (og(((U())))))
7 7log((U1/8)
(P Psn)X S
+ || span ns, a)
n(s,a)
2log(1U1/8")
14 log([U1/88))
2 1+
That
n(s, a) -1
3 n(s,a) -
(14)
Proof. We start by showing that
(P..c Pxa)X
(P Xs
(P Pxa)(X Xx.)
< (Peu Pe
P.n. Pea 11X - Xx, Xu 11:00
(Pou Pea)Xa.
2
(15)
Thoo
where the final inequality is because
|Psa -Psa
Psu S and ||X Xx. 11.0 S nent
Then since for any fixed U have (Peo. Poa)X, En(s,a) (xten)(X (Xa(S))) - P Po.X.), by Hoeffding's inequality conditioned on X,, (since by assumption X,, is independent from the S and each term in the above sum contained within the interval [mii X,,, max X,) which has length || (pan)) we have that
n(s.a)
log 1U//8' 2n(ssa) a)
28
IP
Σ 1=1
(X,, (Saa)) Pau Xw) 2 |xal |Xullspan
X,
UU]
17

---

and so
n(s.a) PP Σ (Xu(S))))
log 1U1/8' 2 21 sspan V
28'
28'
Xa)
E
2n(s,a) a)
U
U
Taking a union bound, the above inequality holds for all u E with probability at least 1 - 28'. Finally, since
[| span I
|| span + a
X1I X1
span
|
span span
+
||
span +
(16)
Thoo
combining with (15) we have that
(P PPoa
Pso)X
I
2
+ 1
log 1U/8'' 2n(s, a) Nhot
I
2
||
log 1U//8' 2n(s, a)
2
log 18//8
Ntot
span
noot
2n(s,a)
Next would like apply the concentration inequalities of Maurer and Pontil [2009]. To apply their theorems as stated, we must shift and normalize to define (for each u E U)
Xu min (x)
X
X span
so that X E [0, almost surely. Fixing some E U and applying Maurer and Pontil [2009, Theorem 10], assuming (ss, a) 2 2, we have with probability at least 28' 2
that
nss a) n a) - V [
2ln |U//8'
V
X
S
n(ss, a) -
using the facts that by standard calculations, abbreviating ń n(s a) for convenience,
n(n 1) 2n
-X,())
-X,
2
27( - 1)
2E (X:( 2B [((
(S P.a [X
and
1
Vosii pe
(S - Po.u.s (S%
ñ
Pon ( - 1
1)
i=1 j=1
V
[
Pec
Maurer and Pontil [2009, Theorem 10] stated involves the quantity 28(n-1) E. 8 Σ j- (S..) X (SSaa) and its expectation). and undoing the normalization and shifting, we have for all E U that
(since
Taking a union bound
n(s, a)
2 log UU//8' n(s,a) -
V
(((s a)
V Vr. [Xm] Vea [..]
< || Ispan
(17)
with probability at least 28'. For any arbitrary probability distribution μ E RS we have that
Vy [X] VVa [Xw-] <
(18)
That
since
V X
VX + (X
-xx,)) < V V [X Vn (X X
18

---

(where the inequality step follows from triangle inequality since Y + EY variables Y) and then we have
is norm on random
V V4 - X
s 1|-
Xu- S
Prot
Thus combining (17) with (18) we conclude that
n(s,a)
V a(s,a)
Pr. [X]
V. Paa X
(19)
a(s,a)
n(s,a)
1
Vp, (Xai]
V.n. aa
+
+
n(s,a)
n(s,0 a)
Neot
7tot
2og U1/6'
a(s,a)
< X Ilapan
+
a(s,a) -
n(s,a) -1noot
Plro
log 10/5' n(s,a)-1 -1
2
2log 1U1/6'
n1x,a)
1
< X
span
+
Reot
V
n(s,a)-1 -1
+
n(s, a)
1
+
neot
(20)
using (16) again in the final inequality. To obtain the slightly simplified bound (13) that by n(saa)
assumption n(s, a) 2 so
n(..0) < 2.
Now, similarly to our use of Hoeffding's inequality, using Bernstein's inequality (e.g., Maurer and Pontil [2009, Theorem 3J), as well union bound over all u E U, we have that with probability at least 1 28', for u E U,
2V.... (x_]1o(((U1/0)) n(s,a)
log((U1/88) 3n(s.a)
(Pea Xa S
||allspam
Combining this inequality (for u²) along with (15), (16), and (18), we obtain that
(Psa P
P Pua)
2
Ptot
Pse [Xu. log((U1/8))
log((U1/88)
2
| I1 span
n(s,a) a)
3n(s,a) a)
Phot
2Vr. P... [X] (o]o(((U1/8
2 log (U//8))
log((U1/8')
2 log((U1/88)
2 nhot
||
|| span
n(ssa)
Nhot
n(ssa) a)
3n(8, a)
Thot
3n(8, a)
19

---

Combining this with (20) we furthermore obtain that
(Pan P
PM [X] log((U)/8")
log((U1/8")
2 llg((U1//0))
log log((U1/8))
+
|| spaa
+ 3n(saa)
n(s,a)
3n(s, a)
n(s,a)
24 P.o
2Mp,. [X] log((U1/8))
log((U1//8)
2 2log([U1/8) n(s, (),,a)
log log(UU) (U1/8')
X| spon
n(8, a)
3 a)
Thot
3m(8,a)
2log(1U1/8))
2og |U1/8'
2log [U]/8' n(s,a) -
n(s, a)
1
+
| span
+ V n(s,a) - 1hot
+
al
n(s, a) -1
Rsoc
Nhoo
24 P.o [X] log((U1/8))
7 7log(1U1/0")
|| span 3 (1(880) a)
n(8,a)
1 llo(((U)/8))
log ( 11'))))
2 1lg((U11/8)
2 [log((Ui//
+ +
n(s,a) -1 2 2
nooo n(s,a)
3n (n(s,a)
n(ss, a)
24 P..
[X]
log((U)188))
7 (log(UU//8))
+ || spum 3 n1, a) -
m(s,a) -1
1
[log(1U|/00
14 log((U)))) (oog(UU(/8)) 188")
+
2
Yeen
n(8, a) -1
3 n( a) -
Now we develop several leave-one-out constructions which satisfy the conditions of Lemma B.5. Lemma B.6.
1. (LOO construction for Vis) For each there exists set U S R with
U1
I-y and random vectors (Xu)ueU,, such that 1) for all U X] is inde-
S1 say sm(s.a) and 2) almost surely there exists some U such that
pendent from
V+
X1
Phot
2. (1.00 constructions for as (Psay Vice) For each 8, a, there exists set U2 C with 1-y
U2al SSTi, and random vectors (X2) such that 1) for all u E U2 X2; is inde-
pendent from S1....., smn(sa)) and 2) almost surely there exists some E U2 such that
T (T (Pra, v7)) x2
3. (LOO construction for V Fix any policy For each 8, there exists set U3 C R with IU3, S I-7 and random vectors (X3)uEUs, such that 1) for all U3 X3 is
independent from S1 , Sea and 2) almost surely there exists some u U3 such
sa
that 1/2
x3 Reat
4. (LOO constructions for Te( (Poas VEE) Fix any policy π. For each s, a, there exists a set U4 C IR with I S S Beat I-7 and random vectors (Xa)uEUs, such that 1) for all u E U4 X is independent from S1 ..., S (((aa)) and 2) almost surely there exists some E U4 such that [Tst.aa) (Pea, pe)
X
Proof. We start by showing item 1. Fix arbitrary s E S, E A. For any IR we define the reward function s.u SAA (random) transition matrix po E SSAX and (random) operator
20

---

Tpe R + RSA by (for arbitrary &' E &, E S, V E R
e
s
Pe p'a'
Paw
8 88
=8
"51"('' = (r(s',d')
8' #8
(V) - (s' (6'',') + max {Pa Toe V) (8', a', V), mip( (iip(V((s")
where
be ('(5',d = max {V [Ta vi] B[s's a)) T V)
5
span
Thot
(21)
Note E, is vector which all except for in state s, meaning that state is absorbing in Pe.u for all actions. Also all actions receive reward u in this state. All other state-action pairs have the same rewards and transition distributions as in the MDP (P,r). Also, we have defined b* and Th in an identical manner to and T pes except we now use yr and Pe in place of r and P. Since all of the properties of T pe verified above only required P to be valid transition matrix and for to be vector in [0, 1j$4, the properties hold identically for T and thus by Lemma B.3 we have that pe
The is y-Liscchitz
Now we define E'. R$ + RS as (**(V)= == (V) (for any V R-)). By the 7 Lipschitzness of T and the 1 1-Lipschitzness of M, we immediately have that _ is -cootraccioon, since
( = || (V1) - MT* pe (12) <
7 pe (V1) - pe S IIV - V 0o
for any V1, 1/2 E R.S. Therefore contractivity implies that there exists a unique fixed point of Z.. (e.g. [Pugh, 2015, Chapter 4.5)), which we call X Note that since E*H is defined without using P... it independent of all samples Sia...., sT((s.a) S drawn from P(- s, a).
Now, as intermediate steps, we show the following two properties:
A. For any u, u' E R, we have ||x - X 1lo S u-w'l
B. Letting U* = Ppe(s) maxaaA max (Ps Toco.a) (Pos st0 Vie)
5 moo
ming" De (s")
we have X per and U [0. 1].
For A, letting u, u' E I. can calculate that
| X 1l
s. (x,)) En (X.)
|| (X.)) MT (x+
T 9.11 pe
(x!)) - pe (xx²)
+ pe (X - T -
pe (X22
Tom
pe (x1) - Toni
pe (x
K |u w11 X X oc
where the key equality step was that T 5. we used 7-Lipschitzness of 7 Rearranging we obtain that || - Xt 5 verifying A.
(x - yo + +T nnn po (X2)), and in the final inequality
po
|u-w'l I-
desired,
21

---

For we first check that x- pi. pe- then we would have that
sufficce to check that MT pe (Vio) = MT pe (Ppp) because
E. (Vpe) = MT
(ppe) MT po MTpc (ppp) = M Dp pe
pe
thus showing that pe is a fixed point of E* and by uniqueness of this fixed point we must have Xb. pe. Comparing the definitions of T pe (Vpp)) and Tp (Vpe). it is immediate that M Tpi (Voo)) (s') MM (T (Ppo(()))) (s') for all s' s, so it remains to check the equality for 8' 8.
First argue that for all a' E A. we have (8 a', Ppe)
___ If ((s 1 then have Auot
To To( Peo Vio) = minng Die Ppo())) 1, and if ((s,a") I 1 then we have T Pear, Vie) =
eg (Pas transitions state s with probability 1). Either way ) Vio) a multiple of the all-ones vector, which implies V [Tatsr,ar) (P Kie) =
(s)(,),, since Po.
O and (
(Po p Poo)
= O, and thus that i*(s, a', Vie)= = 5_ Therefore by the construc-
span
tion of U we have that
M
U
pe (Vio)) (s)
max U + 7 max {
p: P BB (Paar Pixe) - bs, Vie); min(V (s")))
a'
8"
U* + max
sa' P Tes (Pear, Vpe)
5
min Vo (i"")
Nhot
x²
(p)(() - max max REA
pe Po (aaaa
[P saa
Vpe)
5
min (pe(s") 8r
noot
+ max max
{
Pe seo Ta(s,ar) (Pan, Vpo)
5
min
pe (s") s"
V
noot
= (s) = M (T (s)
as desired, so we have checked that X Vi-
Now it remains verify that U E [0, a' E A) above, have the alternate expression for U*
1]. Given our calculation of Ta(s,a') (Pa Vpe) (for any
V (s) pe max min,"
neot ming (s")s
5
Ea' A: :(:(s,a') S
max
U = (0) -
(sn(s"") noot ming" Vpo (s")
O.w.
= (5) -
max
Vite (8) Vi (s")
5 min. D (6")) Rest
3a' E A: A:: 3(s, <
ming
O.W.
We consider the two cases in the above expression. If 3a' E A ((s,a') < 1, then we can upper bound ( as
{ ( (s)
5
1tte (6()6)) S De (8) -7 < (1 7) 1
- =1
- U < - max
min
Nhot
8
where the last inequality is due to the fact that V. pc For the lower bound in this case, we have
= MÂ² I M 1-7
1 1-7
1 (by Lemma B.
U min { (1-
D22(0) - min Dr
(s*)
pe
Vent
which is clearly 2 (note the first term within the min is 2 0 by Lemma B.
Now we consider the case that there does not exist a' E A such that B(s, S 1, that is, the case that 3(s,a' for all a' A. Then argued above we have for all a' e A that ( Vite)
22

---

ming" p vpo(s")) 1. and so by the definition of Tpe and the fact that Q is its fixed point and
Vio = -MQ per we have
Vr- (s) max r(s, a') + + max { (Ped Teceree P (Pad. - b(s, a', ppo) min Vio (s")
a'EA
maxr(s, d') + max { min Ppo(o") - b(8, a', Vpee, min pe (s")}
a'EA
-maxr(s, d') + y min (s")
a'EA
8"
(using the fact that b(s, a', Vpe) 2 0 to compute the max). Hence in this case
U = (s) min
7+ pe (s") = max r(s, d') + min V (s")) - y min Vit (5") max r(s, a') d'EA
x²
a' E'
which is clearly in [0, 1]. We have thus verified B.
Now unfix and let U!a be a set of Rist 1-y points chosen by dividing [0, into Reot intervals and 1-7 placing a point at the midpoint of each such interval. Note this guarantees that for any 2 E [0, 1] there exists some u E U such that J u| S 1-2, Therefore, letting Ú* E U be this closest point in U to the value U*, we have by A and B that
2miii
[ - Ppel - x Xb. 1. S
U
1 1-7
1
7
2Ment
2nont
Thent
Therefore we have confirmed item 1.
Now we continue to item 2. Fix E S, a E A, and define U2. = Una x S. For each u, E U2,, sax we define
x² u.s clip(XX,,
that is, we clip all entries of the vector X constructed in the previous part so that they are S (s')..
Since X was independent of all samples 81 S1,..... ......, saa(sa)) drawn from P(- s, a), the same is true of X2. Define S a) to be state such that Q3(s.a) (Pees ViJ) (S (S (s, (s)a)) (if multiple states satisfy this, we can break ties in some consistent manner). Then for any u, s E U we have
|| (Tesaaa (P.a, Ppe) x2
clip
(per QB(e,a) (Pany viz))
clipí clip(XX), X
clip (Pie, (S*
(s, a)) clip(X, u: X! (s())))
I clip (it Dit (S* a)) - clip (Xi, Pia (ST
+ clip (2) Ppo (8, a))) - clip(X x²(s)))
< 1 pe
x
| 1i-- -x:
(st, x2
(22)
From item we know there exists some u E U such that
S 2mici and furthermore
if s' = S* a) then
-x(()) - - x s <| 1 xa2
S 2nhot
Combining these with (22) we conclude that almost surely there exists some (u, s') E U x = sq.
such that [TB(...)( (Pan; V+t) - X2, < I as desired. Therefore we have confirmed item 2.
For item 3 and item 4, we use nearly identical constructions, with the only difference being that for item 3 define X3 be the fixed point of the operator _=,,,u IRS R$ [v)).((V == * u (V) (and otherwise use the same construction as for X!). and then for item we use X in pe
place of X3 in the construction for X Thus, the key difference is replacing M with M within the construction for X3. and since the only properties of M used were 1 1-Lipschitznes: and that M1 = 1,
which both hold with M " in place of M, and also the fact that V M Q which is analogous to pe the fact that V M xh Qu per all steps work in an analogous manner.
23

---

Now we can prove the key concentration inequalities needed for the rest of the proof.
655 An
Lemma B.7. With probability at least 1 - 5, for all 8 E S, E A. if) 2 1 1+8 8 log then
(1-736
(Pmn - PPa)
Tō(o,a) (Poa, ppo)
VV(s,,) Pmo (P(o,a)(Poa Proi) 3(s, (Tocaaa)PPPp ppo)
4.5 Rhot
<max
spon
1
= b(s a, Vpc))
2ntot
where 8 log
6.8 Amat and ((s,a) max ( (1-7)0
Proof. Fix some s E and check. Otherwise, can immediately combine item 2 of Lemma B.6 (which gives [U] S S with Lemma B.5 (since our condition on n((8, a) clearly implies n(8, a) 2 2) to conclude that with probability at least 1 68',
((s,)) + &1+8log
(GS Aneot (1-3)8 then we have nothing to
(Pee Pso IT (T(. (Psa))(PPa P
2V p...
Ta(aaa (Psur Vite) n(8, a)
log S (1-9)0'
log (S (1-
To(oaa) (Pear Ppo) span n(s a) -
2 2og (S (1-7)8)
14 log (S (1 (1-7)80)
2 31
That
n(8, a)
3 n(3,a) -1
Taking union bound over all s e S,a E A, and setting 8' = 65 we obtain that with probability at 6.82 An (1-7)6 ). we have
5
least 1 - 5, for all E S,a E A where n(s, a) 2 + 8 8log
(Pen Paa)TB(roon (Peas )
2V T Peas pe)
log
G52 Anua (I-7)6
7 log
GGS Anuua
TD(s.a) (Psas Piei Ippnn 3 n(s, a) 1
(1-7)6
n(s,a)
2 log 2 2+31
6652 Anya (1-
14 log [B52 Anyul (1-710 a)
+ Phoo
n(s,a) ()
-
2V Pmc
T Te(s,a)
(Pees Vite)
G52 Aniua log
(1-7)0
T To(o (Pos. poo)
7
An log
(1-736
4.5
$
n(s,a) -1
span 3 n(s, a)
Phoo
2V Pm To(s.a) (Pon. P7to)
log
6.2 Anawi (1-710
7 log
[8S Ariul
< 2 max
Tois (Poa Paas
(po)
(1-7)6
4.5
n(s, a)
span 3 ne(s, a)
Noat
8V Pen Tel (Poa ]
log
An (1-7)0
|| (Taee (Pon, Pic)
14 log
G52 Anios (1-7)6
4.5
max
+
a( -1
span 3
(ss
< <b(s,,, Vite)
2n
24

---

where the second inequality uses the assumption that nxs,, a) 1+8
Antaz (1-2)6
and the fact that
2 2+3
141 < <.55, and then we bounded a+b S max {a, b). We also note that since we are in the 3
case that ro(s, a) 2 1 8og 65 Anrot
9, we have that n(s, a) -
1,,11
(1-7)8
Lemma B.8. Fix any policy x². With probability at least 1 25, for all s E E E A. if 2
6.5 Ansut )
1 1+ 8ln
then
(1-7)0
(Psa Psa)
To(o,a) (Psa: Ppo))
max
V3(s,a) Pan (T(saa)(Pau P (p0)){((0,,0) (oaaa//Toee To(ma)) (Pas upp))
((((,a)
span
Thoot
b(ss, a, Viti)
and
2 log
6Sa Artzot
Va pe
S V
Vp
Psu
Vx pe
+
Dr pe
n(s,0) ())
[1-3J0
Yhoot
(23)
and
2V Pau
x log
6.82 Aneas (1-7)0
log
6. Arrzot
(Pea
Peu) 1/5'
$1
V pe
(1-7)6
(24)
pe
ra(s, a)
span
3n(s, a)
Thot
where a 8 8log
655 Anzot (1-7)6
and ((s a) max(n(s.e
Proof. The first statement analogous Lemma B.7 uses the construction of item of Lemma B.6 in place of item 2. Thus combining item of Lemma B.6 with Lemma B.5, taking a union bound and performing the same simplifications, we obtain that with probability least 5, for all
E S, A, if,, 2 + 81n 6.5 Anags
.then
(1-7)8
(
(Peu Psa)
T)(s,a) (Pea, Pir') S b(s,bsss a, PT
Now we establish the second two properties. We will show that they both hold with probability 1 5. after which we are done since we can then use a union bound to combine with the above. Fixing some
E S and E A, if nsss, a) 1 log can immediately combine item 3 of Lemma B.6 (which gives |0| S Ruo < S Reat with Lemma B.5
(6S² Anaes then we have nothing check. Otherwise, (1-7))0
1-7
(since our condition on n(s, a) implies ra,s, a) 2) conclude that with probability at least 60'. we have both
2V P.a
x log
S (1-7)8'
log (s (1=2)or)
(Pea - Pao) D=' pe
D pe
S
n(s a)
span
3n(ssa)
2 log
(S 71-8
log S [1-7)0"
2 +
2
(25)
Ntot
r2(s,a) a)
3n(s, a)
and
n1..00 0.)
V
Pra
xx pe
S
/Vp.
P.u
+
2 log
(1-9)0'
Sneat
(26)
7(8,0) a)
n(ssa) -1
span
2
log
Syieat (1-7)07
1
+
21
+
(27)
n1(8, a)
14ot
25

---

Taking a union bound over all 8,a E S, A and setting 8' = 5
68.A we have that with probability at
least 1 - 8, for all 8, such that nlss a) 2 + 8ln 6.5 Anya (1-7)0
) both
2V Pm
V pe
log
6.5 An (1-776
log
68 Antol [1-7]0
(Pea - Peo)
Peo)
V' pe
Dx pe
3 Rhoo
(2(s a)
3m((sa a)
and
V
Puu
Va.
S
n(s, - n(s, a)
V
V Pae
Va-
V
2 log
n(s.a a)
6.5 Amens (1-9)8
span
2 log
GS Anzot (1-730
21
+3
Nlot
n(s.a)
log
GS2 An
V pe
D= pe
(1 (1-7)6
S
V
Pen
+
span
n(s a)
Thoo
where for the first bound we simplified (25) using the condition on n2ss, a) and the fact that + v
21 3, and for the second bound we simplified (27) also using the condition on n(s, a) and then 388
the fact that 2 + = 4.
B.4 Pessimism
In this subsection we establish the following essential pessimism property, making use of the previous concentration results and our construction of pe-
Lemma B.9, Under the event Lemma B.7, we have that
Q² 2 Q
Proof. We will show that T²()) 2 Q (where (Q) = + PM* is the Bellman evaluation
operator for î) which by standard argument implies that Qa Q since we can then easily derive (by monotonicity of a that ((*)))))))))))()) (²) 2 Q for any integer 2 0, and thus
Qº lim (T (8) 2 Q
k
Fixing arbitrary s E S, a E A, we will now verify that T (Q) a) 2 ((s, a). From Lemma B.4 we have that (p)(Q)(s, a) 2 ((s, We consider two cases based upon the value of Tp) a). which by (3) is either 1) equal to r(s, a) PP (P.., MQ) 7b(s, Mā) or 2) equal to r(s, a) + 7 (MQ)(s In the simpler case 2, we thus have that
Tpo (s, a) = r(s, a) + 7 min(MQ) S rr(s a) + 7Po MQ = +P.. -
using the facts that ming V(s') < P.e V for any V E R (since P.a is probability distribution) and that M¹ M since greedy with respect Q. We therefore have that ((s,a) < Tpe (Q) a) S ( a) in case 2, as desired. Now we consider case Note that since we are in case 1, we must have that 3(s, a) S 1, which implies that n(s. a) a + 1 (because if we had (Pr..
B(s. a) > 1, then we would have T T sa: .Q) = min, (M))(s))) and b(s, a, MQ) > 0, so
M³) - b(s, MQ could not have achieved the maximum in the definition (3) the term To (PP.. (Peo,
26

---

of ppe.. Then we have that
as) S (po
S po (p,)) = r(s, + PPaaTp(s, (Pear Mapp) 7b(s, a, M
S (((,,) + p Paa st (Pau Mape) + y (Pes - (eaa (Pea: M 2pp
7b(s, a, MÔpp)
S <r(s,a) + +- Psu (( (Pas Ma rb(s, Mara) a,
7b((s, Mapp
2n
I <((s,) + Psa 2n
<r(s,0) + +7 MQ
-(,,0) 77 M = (8)
where the first inequality is due to (Q) 2 Q from Lemma B.4, the second inequality is due to monotonicity of Pe (Lemma B. and the fact that @ Qie (Lemma B.4), the third inequality by triangle inequality, the fourth inequality is from Lemma B.7, the fifth inequality is from the trivial fact
that elementwise Ta( (P papp I MỘ the sixth inequality follows from Q Q + 2m
1 due to Lemma B.4 (since by monotonicity of M, M S <M@ 1 MQ 2m 1), and
the final equality is from the definition of गे (from Algorithm 1) since it is greedy with respect to @ Combining the two cases have shown that T (Q) Q as desired. Combining the two cases
have shown that T (Q) Q as desired.
B.5 Policy hitting radius lemmas
In this subsection we establish some key properties regarding the relationship between Thit and certain discounted policy occupancy measures which will appear in later analysis steps. We also establish some facts about Thit of general interest and compare it to the mixing time.
Recall that 17s := inf(t 2 S. = =} is the first hitting time of state s. We define an additional useful quantity: for any s* S, let
(Pi n. s*) sup TT 773
This is the maximum expected hitting time state s* in the Markov chain Pa (which can be infinite).
Then we have
This (P, .T = inf (P, inf sup E. 7/--
Thit (P, finite if and only if Pa is unichain: Lemma 1.10. Fix a policy n and an MDP transition kernel P. Then the Markov chain Pa is unichain and only if Thie (,,)) w) is finite.
Proof. First, suppose that Thit (P, π) is finite. Then there exists some s* such that for all so E S, ET, n6 < 0c. Therefore s* is reachable from any state, so all recurrent classes must contain s*, but since the irreducible closed recurrent classes (along with the transient states) form a partition of S, this implies that there can only be one closed irreducible recurrent class, that is that P, is unichain.
Next, suppose that Pa unichain. Let 3" be some state in the single closed irreducible recurrent class of P.. Now argue that ES [7a=] < oc for any 8n E S. First, it is standard fact (in finite Markov chains) that letting C' be the recurrent class, we have M max ET [na+] < co (e.g. Kemeny and Snell [1976]. where E", [7s-] is referred to as the mean first passage time). Now letting 8p any fixed transient state, since there exists unique irreducible recurrent class C, letting Vlc inf (1 2 0: St E C} be its first hitting time, it is also standard fact (for finite Markov chains) that E", MCC < oo (replacing C' with single absorbing state, the new chain becomes an absorbing chain, and the absorption time formulas in Kemeny and Snell [1976] imply E E,, nJC < oc). Then
27

---

calculation using the strong Markov property (where Fue is the stopped with the stopping time 1c) implies that
associated
E [7-- = E 1% [ms-- [
Snc
[m--] 1c
S E [M + +nc!
Since there are only finite number of such transient states so, the maximum of 1 [ms-] over all such states is finite. Hence (P, x) I max Eg [Ta-] < co.
Define 2,50
R
7,50 (8) = Σ
P.c..
2=0
We often drop the dependence on 7, and simply write dag We also define ds T- (s).
Lemma B.11. Let 8* E S satisfy Thit (P, x) (P. 8*). Then
sup
dd (s) d.. s (P.
SES
and
sup
- -d, -s),
S
(P,
$0.81 SES
Proof. We use a coupling argument, and these calculations are somewhat inspired by those in [Cheikhi and Russo, 2023, Lemma B.13]. Starting with the first statement, fix some 5o E S. Let Sū: Si..... .... be the stochastic process with distribution given by the Markov chain Pa with starting state s*, and let So. Si...., the stochastic process with distribution given by the Markov chain Pz but with starting state sp. Let .7.- = inf S = s*} be the first hitting time of the state s* by the process (S.) Now define the process Sy S ... identically (5 but to follow (S)) once reaches s*, that is Sy Sj. Sy +1 = Sf, and so on. It is standard fact due to the Markov property that (8)) has the same distribution as (St) ) Now add an absorbing terminal state q (which we do consider as an element S) and for all t 2 let Z, Bernoulli(y) (independently), and define
processes (5 and (5)) by 5% Sg S St. and for 2
$i+1 = {q 1
3k E fI.....t
t + 13 such that Zμ =
otherwise
{q
3k E (l....,t t
1} such that Zμ
$
otherwise
Intuitively speaking, ($1) and (8)) will reach the absorbing state & the same time, and the probability of reaching it on any given timestep is y it has not yet been reached. is a standard fact
that d:,, (5) = E - I($) = 8) and that d. (s) = EE E 1(5; = s). Hence using the above coupling we can bound d= (+) - d= (s). Specifically we have
Σ SES
7,00 (8) - d. (s) Σ (s)
(1() = s) I(S; =))
SES
1(5) = 8) I(ST = s))
E
#ES
1 1
E
Σ
Σ
(I(5) = 5) I(;; =5)=
(28)
SES
0=
28

---

where in the final equality we let f2y = inf 2 1: Z, = 1) be the first hitting time of the terminal state. Now we consider two cases. On the event that Fy 77s we have
1g
(1(5) - 5) - 115 = 3))
U(S = 8) - -1(57 =
SES
1=
SES
t=0
110 1-
Σ
211(5 + Si)
2n S 2M
On the event that 77+- < Ng. we have
M--
T(S =) - -(St =))
1/ 1
(TS)) = 8) - I[S =
#ES
1=0
ne
I(S + 10
11 - -1
9--
Σ
Σ
I(S = s)
Σ
I(S s)
Σ
I[; = s)
t=
(= 9
f4
Σ
[(S) Σ
I(S) =
SE
(=
Σ
[1() 5) 11(Sitm n =s))
I(S) = 8) - I(S n. = =s)
#ES
1=
1e -1
= 2
Σ (=0
U(S
S 277-
using the fact that S Sj, Sy Sh = -i.... cancel terms. Combining the bounds for the two cases with (28), we have that
dc Σ BES
(s) (s)
(s) S E2n. 2Thii (P,
as desired.
The second statement of the lemma follows immediately from the first, since by triangle inequality
sup
Σ Idao (s) - ds, (s)l sup 60.81
Id - do S sup lide, de 1l + ld - day ll S (PTht((, 80.81
9p.81 SES
Lemma B.12. Let be policy such that Pa is unichain, and let ftt E SRS denote its stationary distribution. Then
Σ
dr (s)
1 1-7 (0)) s 4hha (P, T).
#ES
Proof.
Since nºt a stationary distribution, we have for any that
Σ 1 (d)dd, (8) = (1=) ''ES
-(=)T
Σ
p 6 = Σ
(1))))
es =
1
(x)
1-1
1=0
t=
29

---

(since Pxx = (1²)T),
Then we can calculate by Jensen's 's inequality that for any fixed s S,
o0 (s)
-1
1 n" (s)
(s)
d (s) Σ
N0 os)
7,50
F'ES
Σ u (s') (c) - d dr)a(()))
EE
2
Σ 1 (s') (07,0(()) cs)
SEES
Therefore
Σ sES
d (t)
1z
(s)
2 Σ Σ 10 (0'()
(G (.) (s))(()) [001=Eme
(5'))) Σ
7:00 (8) - (s)
#ES
E'ES
6'ES
EES
Σ 1
4Tht (P,)t
#ES
where in the second inequality step used Lemma B.11.
Lemma B.13. For any policy x. |1 span S 47im (P,
Proof. Note that by Lemma B. if P.. is not unichain then Thit (hi .) oc and so the desired bound holds trivially (note ||h* 1 is always finite). So we can now focus on the case that Pa unichain. This implies pa is state-independent constant. this case it is standard fact (c.g. [Puterman, 1994, Corollary 8.2.4)) that for any s, E S,
1et (5) h (8')
lim ViT -77)- (s))
Therefore
|
max h- h5)( 1:T (s') 5.
span
max lim (7) (7) --
max lim eg c 7P*) - -. 7P=)
max lim (d d= )r= e
< max lim | di du 1| r
< max lim (P, 8, E. Ee
= (ht
where the inequality steps are by Holder's inequality and Lemma B.11.
B.5.1 Relationship between policy hitting radius and uniform mixing time
Here we argue that there is generally no relationship between the policy hitting radius and the mixing time. First, if P. is unichain and periodic Markov chain, then the mixing time will be infimite/undefieed whereas (he T) < oc by Lemma B.10.
Now show example where the mixing time can be arbitrarily smaller than the policy hitting radius. Suppose that P. ग are defined so that Px is the random walk on the complete graph on L nodes, where L is any positive integer. Then μ fc"(s (s)
1/L for all S. and after just step from any starting state we have that S₁ has distribution μz so T(T)) = 1. However, for any fixed starting state so and any state # So. have that 7, Geom 1 L), so By, n L, and hence Thit (P, ④) L.
30

---

B.6 Error analysis
Now we can continue with analyzing the relationship between Ti and pm for comparator policy n² Having established pessimism (Lemma B.9), which implies an upper bound on O we now seek lower-bound this quantity. Since (by Lemma B.1) Ope 2 Qp it suffices lower-bound 2pe in terms of V**, which is then related to p
Lemma B.14, For any probability distribution E A any E TR,, and any 3 E [0, 11. we have that
12 VII [V].
Proof. We prove this by showing the more general statement that for any random variable X and any scalar a.
v [min(XX,)) = [X).
Let = min(X,a) a) and =
Then
=
= v
V [ + (C).(T,A).
Thus to show V 2 [7] it suffices to show that Cov(T, A) 2 0. Now we compute
Cov(T, A) = E ( ET)]
E. E ET)T(X at} +E(A(T ET)T(X <a)]
On the event (X a) we have A = 0, E AT ETI{X < a 0. On the event (X a). (T ET) 2 since T = a and IET < a, and A 2 0, so E AT ET)T(X a}) 2 0. Therefore Cov( (T, A desired.
Lemma B.15. Fix any deterministic policy x². Under the event in Lemma B.8,
V"" pc < <1 - - -2mb,
where
by (s) (s)
B(s, (s))V p.
V + +3(ss, (s))
12
span
Prot
We also have that
7 pe
- Pp D:8" + t 2 rnt
(29)
Proof. Fix s E S,a E A.
First we handle the case that B(s, a) S 1. This implies that nl(s, a) 2 By the definition (8) of T we have that
ass
1 1 = 1- 8lgg
[1-7]8
Q (s, a) 2 r(),0) + 7P P (( (P V - 7b(8, a, V=
(30)
31

---

By the definition of T T)(.,)) (Psa. V we have that (elementwise)
Pa T ((o.a) p Σ
Pan (s (s))T((s (Pau. Vo
(s')
pe
Σ
Prald')Ta(saaa (Pear Dp (s')
2 (6)) (P Peainee)
Σ
(a (Psa: (s))
(s¹)
s': Vin 70
(6)) (Pa
Σ
Pea Ud
pe (s')
V. (Pan P2t))
Σ
(((s)) V7z')
+
'' (1))
E
Vs
pr (s')
s' vet (1)Q (Pa. (Pai Pre))
Σ
Poals')
1 (s') -
pc
st: Qoco Poa Pro")
span
Peu Vx - B(s,, a)
(31)
span
where in the final inequality we used that E Eet Qac., PP P....pp')) Poals)) < B(s,a). Using (24)
from Lemma B.8 to relate P.o Dx pe to Paa pe
we can further bound
Pxa Bis.)) (Psa, Pa') pe
2 Psa Dr pe
(P
Psa)
[ss a)
D pe
pe
span
Pm
a pe
log
652 Amect (1 (1-7)6
log
GG5 Amsos
Pau Vr pe
|
(1-
n(ssa)
span
3n 3n(s,a) a)
3
B(s,a)
14ot
span
Pa V pe
8(3,a)
223(s,
(32)
pe
pe
span
Thoo
To finish lower-bounding (30) we must also lower-bound b(s, a, 1z."). It is immediate to see that
(Tpisaa) (Pra.
V
and also by Lemma B.14 (since we in the B(s, a) S
span
pe
span
case) we have that V Prn (P(s. (Pen;
V=
S V P.a
These two facts yield that xx
= max { ((s,a)VP.
b(8, pe
(o(s.a) (Po.: (o:') ,(ss, a)
span
nrot
5
< max
B(s, aVV
((s,a)
+
span
Rtot
$ 3(s,a)
V pe
+ +(ss
5
(33)
P.n.
pe
span
Rhot
32

---

Furthermore, using the bound (23) from Lemma B.8, we can further bound (33) as
b(s, a, ))pe)
Va pn
+
B(s,
+
5
span
Nooo
((s,a)
V
v
span
2 log
n(s, a)
654An (1-7)0
ntot
4
+ 3 ((,,a)
pe
span
Tito
5
S ((((s))
+
v (3,
+ 4
B(s, a)
/1/0000""
+
5
span
neot
span
S \VB(,,))P.. Pm
V. pe
+ 2,3x,
a)
(34)
pe
That
(using the definition of ((),a) and the fact that we in the B(s,a) case).
Combining (34) and (32) with (30) we obtain that
12y
Ope (s, a) 2 r(s, a) + 7Peo V 2%/ ((s,a)V
47,(3s, a)
pe
span
Tht
= =r(8, a) + PPa pe ab(s,a)
where we define b(s, a) = (((s,))P..
V
+ 43(s,
ViT"
12
ssan
Now for the simpler case that B(s.a) 1. we have that
@ a) = r(s, a) + min pa o' pe (s')
2 r(8,a) a) + 7Pas Va -7 Fo
span
2 r(, + 7 V= - 3 a)
span
2 r(, + P v. - 7)(
Combining the two cases of ((s, a), we have for all s, a that Q7 (s. 2 r(s,a) + ypss V= 70(s,a) Therefore by monotonicity of M
DIT 1 Q 2 M= (r+ (T+7PV pe - -76) = r.. + PP. Det
pe
pe
We also have V -Pp- V= +7b.. 2 rx., which will be needed later. By the Bellman equation for x² we also have that V/" FT. + + Pr Vaa Combining these, rearranging, and using the monotonicity of multiplication by (1 - -pp- -1 (since all its entries are nonnegative), we obtain
v -
D= S Tx- + 7Paa V* - r + 7bn 7Px- V. = =7b.. + 7Pa. (V*' D= pe
pe
(I - Pa.))(VV - -ixz') < 7bs.
V= pat pe < (1 (1-7P -p- -laba.
as desired.
Lemma B.16. Fix a deterministic unichain policy n². Suppose that for all s E S, n(s, (s)) 2
myx" (8) 4 4Thi TT,,,, 1 m, and 1 2 2. Then under the event in Lemma B.8, we have
that
(so)
(so) - nr
pe (so)
max #oES
2048S
p pe
log
A52AAmu (1-
640S
p pe
log
6.5 Arcaa
(1-
12
span
771.
(1
7mm
(1 7 Poot
33

---

Proof. First we note that, using Lemma B.15, we have
max V (so)
Vipi (su)
max #oE
co T (I (Pr.) -/x
max suES
We will now fix some arbitrary so E S and try to bound (ai bar) By the assumptions in the lemma statement we have that for all E S,
n(8, x (s)) 2 myr (8) + 47hh (P, x²) = (1 -1-7)m
1 1- 16 (8) + 4Thic (P,"")
1
(s)
1
2 (1 m) 100 (s) - (1 - 7)m di (b) - - 7 1ttt (s) + 4Pni
2 (1 7m 3.50 (s) - (1 - (001-))m440 7) (P,5') + 4T (P,
2 (1 mm 1 (s)
where the third inequality is a consequence of Lemma B.12. For convenience we will let C == (1 - 7)m, and so we have shown that n(s, (+)) 2 Cut (s) for all E S. Also for
convenience abbreviate L = log 655 Antot
Using the fact that n(8, n" (s)) 2 4 which implies
(1-7)0
max(n(s,5' (1),, 11)) (o))- S mx).
4/3
we can simplify b.. as
((),""()))
(s) = 2/ (s)) Part
V pe
+ 48(s,, ' (s))
| pe
12
Ipan
=2 V n(s, n(s, (8))
88
V Port(e))
V
+ 4 (8, (s))
8e
V
12
span
Thot
s 2/ n(s, (s)) Vp VP
168
V pe
+ 4 (15,, क (s))
166
7 +
12
span
Noot
Using this and the fact that n(8, x (+)) 2 Caty Cee (8) for all 8 E S, we have
(e Bm.)
Σ
d
3,00
(s)
2/
nls, T (s))
168
(an pe
+ 4 n(8, x (s))
168
Da
pe
+
12
span
8E
d
s (s)
2
168
W
VP
V pe
+ 4
168
| pe
12
2,50
Cdty 7.80 (s)
Cdyy 7.30
(s)
span
Ntot
2/
d=
(8)
168
W Pant(ai
Dix pe
S4
168
12
7,80
pe
spun
Thot
64S
Σ d=
(8)
Pantca)
Vir pe
64S
12
(35)
C
pe
span
(1 7 Mott
where in the final inequality we used Cauchy- bound the first term.
Now we focus on bounding the quantity Eses di. (s)V
(rr pe
Va Let c minges pe (s)
and V Va
cl. Then
pe
P (V pP. V) (V + V)..V)
S SV - 7Pp.V V + Nb. + (1 - ()- o (V + 7Pa..
< < < 100 (V -p V + 7bnr + - 7)c1)
(36)
where for the first inequality we used that V +yPp. 7. V > 0 and that b.- + (1 - 7) cl > 0. and for the
second inequality we used that V V++P=t V < V which follows from the fact that
1 and that V - V + + (1 --cc cl 2 0.
V P V + 76 + (1 - 7)
-z Pp. D= + 7bb. 2 Tx. 2 0
34

---

using (29) in the inequality step. Thus
(1 Vp..
Vir
10 Pp,. [V])
dr 7,00 Ps. (v) (Pa. P)22
(V) 1 d 7:00:
72 (V)
+ 72
1
((V) (p ()-)))))0))
d='
7,80 Pm. (V)
7 (V) + 72
(V - -ppp. V + +7 + (1 -)(1)
(16)
1
d 7,80
2
V 00
(V -pp. V + +ō + (1 - --)c1)
72
2
V
Do 60 (1 - 7Pp'' -1 (11 (Pa VV + +7ber + (1 - (1-7)c1)
2
|V
600 (T )Pr.) 1 - Voo + +7bm.)
?2
2
4
DC
D+
(it (dtt 7im)
y2
pe
722
2
V
1
4
4
+
(d
7,80 bax).
(37)
x²
7
In (i) we use (36) and in (ii) we use that
G Pa. (V-)
(V)00)
<
C 4,000 Pa. : (V) - (V)c22
-
72
Coo -I -
0) 5o.
Combining the bound (37) with (35) (and noting that
|
Dr pe
), we obtaín that
x0
span
2
Vx
4
V pe
S
64S
squa
+
spam
(d% byn.
C
7/2
64SÉ
12
+
C'
pe
(1
- Moot
span
512
Se
(VI 11-7 + (d% by.
spam
C'
64S8
12
+
C'
pe
span
(1 - y
where we simplified by using that Va +
bb S v Vb and that s (since - 2 implies that
y N 2) The above is quadratic inequality in = V (15 by. of the form
Syy
12
x²
x
8y
+
+ y +
(1-2) m
048 Pr-
where y
From the quadratic formula we obtain that
8y +
8y +
4
V
8y 1-7
+ y
+
12
(1-7)meot
2
35

---

and then squaring both sides we obtain that
2
V8y + 8y + (V
1-7 + y
By
12
(1-7)ma
Fi (iioorbar by.)
x²
8y
12
S 2
8y + 8y + 4
V
-
+ +y+ +
(1 -1- Mo
32y
12
10y +
+
(1
7)
64$
f
64S
7
12
10
span
+
32
span
C
C(1 ((1-7)
(1 y
using that b)2 < 2a 263.
Recalling the definitions of C (1 7)m and l log
[o8² Amsas
(1-7)8
and also since the above bound held for arbitrary Sp, we have thus shown that
max (T (80) #0ES
(80) - 17p (80)
2048S
Va
log
6682Anoo (1-7)6
640S
log
[GS² Areeat
1
(1-7)8
12
span
spun
+
7-7
7mm
(1 7 Meot
B.7 Controlling the empirical span
While Lemma 1.16 approaching the desired result, involves the empirical span term which we would like bound in terms |[V**] span" Such bound the objective of this subsection, and makes crucial use of our assumption of data even for states which are transient under Px..
p
pe
span
Lemma B.17. Fix a deterministic unichain policy n². (h (P)="))) log (25) for all Then with probability at least
Suppose that nls, (s)) 2
[ha(P, (,)) S (P,
Proof. The proof of this lemma is inspired by that of Zurek and Chen [2024, Lemma 4]. For any MDP M and s E S we let _T denote the expectation with respect to the Markov chain induced by x in the MDP M from starting state sy. and similarly we let IP (..,.( (E) = E M denote
associated probability measure, Let 8* E S satisfy Thie π*) = Thic (P, ग, oT, Let M be
MDP (P, r). Then
This (hic(P,T') S Thit (P, xP,=",8") )²*= max ET SoES
ea.M [.
(38)
36

---

Supposing that & E N satisfies m P (1 2 k)
S
then we have for any so that
2
20
Ea
M--1 Σ
P
t =t)
k-1
Mi (16 > ik + t)
Ny. 1/. ik)
1= t=0
k
% (11a > ik)
20
k
2- 2k
(39)
where the final inequality step used that
P
(1 > ik)
max P
(7 > ki) 2-
#gES
which follows from the following standard arguments: for any integer 2 (since this formula obviously holds for i 0), we have
%6 2a ii)
P 11 2 ik)
si (1/. $ (i. 1)k- 1) and 77-- & {(i 1)k..... -1)-
xi ii N6. (no- & :o,....... (i - 1)4- 1} and n & {(i - 1)k, ., it - 1) F
[1/5- $ (o.....( (i- 1)k 1}) P M (1a- & {(i - 1 1hi ........ ik 13 F F((-1)))
R
(00
E
[Iro- & (o..... (i 1)k 1}) P S (n & fo...., 13)
M
(20)
[I (11. $ (0,.... (i - 1)k 1})]
2
P
(1
2
where F(s-1)k is the sigma-algebra generated by So,..., S step (7) is the tower prop- crty, step (ii) is because the event 77.- & {O...., (i - 1)k - (i2i) is the Markov property (e.g., [Durrett, 2019, Theorem 5.2.3I.. and step (iv) because P M (1). (O..... - 11) P 5 2 k) 1 (this last inequality holding almost surely, due to the assumption that max P $0 (1.- 2 k) S 1). Since these arguments held for arbitrary i, we can repeat them to obtain the desired bound.
1} is F(i- measurable, step
Now try to find such k. Define the reward function F by F(s, a) = I(s * s*) and also let P' be the same transition matrix as P except with state s* made to be absorbing for all actions. Then, for some 7 to be chosen later, letting V Vir be the discounted value function for policy x in MDP M' (P', F). and letting Ex MM Ex M denote expectations with respect to the MDPs M' and M
37

---

respectively, we have that
V (s0) = 1 M
7'((S( **)
t=0
= E
7/((11+ 21)
M
1=0
20
R
T(pss > 1)
M.
= E
S (h ,',"'"))
This implies || 7.M span S Tha (P, x², ,²), which will be needed shortly.
Let fr similarly be the same transition matrix as P except s* is absorbing for all actions. Let M' be
the MDP (P",7). Then for any & E IN we have
VT T.
(50) = ET
71((s # s*)
M
1=0
ET
T'T( >
M
h-1
RT
71((11-- > 1)
M
1=0
ET
3-11((1/- > k - 1)
80 M
1=0
k
2o. k - 1).
Rearranging this implies that
Vn
(80)
3V (80)
J.M
7.
(1.
k-
(40)
sone
by
k
where for the second inequality set 7 and used the fact that (1 1 1)a-1 1/e 1/3 for all integers le > 1.
Now we bound V=a .. (su) using concentration inequalities. For concreteness in the following
application of Hoeffding set 12T (P, so 1 11 (P, (P) By Hoeffding's inequality, we have for any s + s* that with probability at least 1 8 8'
V= 7.M
2
log (3)
(P n², s²)) log (3)
c ( Pd, VV.
S
span
2n(ss, n (s))
2n(s, π (s))
and trivially we have (. PH.) VTM 0. Therefore by union bound over all s S and
setting 8' 6 we have with probability least 1 that
(Thie (P,T*, nT, s))² log (25)
PP-- PP.
< min SE3
<
2n(s, (s))
12
12a where the second inequality uses the condition that n(s, ++))) 2 72(Tnac(P, T* 7²² log (25) for all E S.
(Thit T
(P,T*,"*)) 8²)) log (25)
z
38

---

Following standard arguments for the difference between two value functions with different transition matrices we have
V 3.40
V Tu = (I 7I T.. - (I- T.-
=I -T--7p* (1
- )p- - (1 = =7(I - -Px - (Px. - PI -TP*.)
- -/p-- Tm
- - 1 P V=.M0.
Hence
|| || 7, - Vor
= 711 PPx)) -
PM.)VT.M T.M
T.
1 7T - - Pkx.)= ) -1
(P - -Pa. Vi.
100+00
7 1
< 1 - y 12
k
< 12
Thic (P,
Combining this with (40), we have that
max P #
(1 2 k) = max
so.M mTs
5oES
V
7.M
loc
3111
Vaa
7.00
7.M'
+
k
k
k
hit (P,T*) + 3Thhil (P,T*)
1
127 (P, =*)
2
Using k = 12Tnn x)) in (39) and combining with (38), we conclude that
Thit (P, x=)
max EE a
2k: [l S
24Thhit (P,=")
as desired.
Lemma B.18. Fix a deterministic unichain policy n², Suppose that n(s; (576T (P, =²) for all s E S, where 8log 665 Amas (1 (1-7)6
). Then with probability at least
1-20 1-25,
4 pe
S 3
+ 2. span
span
Proof. By the definition (8) of Trp
we have for any s E S that
D (s) = g n Qz.
= Mr 9.. (2p-)
=r(s. + + max { (s) (s),
M M=' 2%) - b(s, M " Q%:)
min(M (6')
= (s) + y max { (o Dat b(s,, (s), Dx*), ), min( Vx*' (s } pe
pe
= =r. (s) + y (oo pi + + max max (Patr(s) (IR(E (Par (o)) Vzz' - v -bs, (s),, VT))
min((
s. pe (s')) - (o)
(s) + 7p ST (s) D'. (s'(ss)
39

---

where we have defined D' E R- as
(s) = max { (s) (Tolax Ppee) - pe
- b(s, x (s)), Dpe') ), min minn(pp
pe )s²) (ppe))))))))))))))))))) P Pex (0) Pp²) S.
Note that both terms within the max in the definition of ((() are I 0, so B/ z 0. and also we can bound
B'(s) - - (Por(() (ImLs (PST(())) (s), Pppe') - Ppp"') b(s, nT' (s), Vpp ) (a)a (Pa (Por (s); P) + b(s, x:' (s). Pio")
(en (0) (Pro'
- B(s, क (s)) |
||
+ b(ss, T- (s), ppp))
span
V B(s, x (s))
V pe
+ +28(s, x (s))
V pe
+
(41)
span
span
Nhoo
where (i) is due to the fact that (3) (s)) (s)) (s), 3(s ((s.
Vpt')
2
Patt (s) Vpp
which holds by an argument identical to that of (31), and (ži) holds since V span
(s), P
max { ((s p.... P. [T (Po)) Ppt
B(s, (s)) ( (Por (P) (s), Pro
]
5
+
Reot
< max { B(s, (s)) (a))
Vz pe
1(s x (s))
}
+
5
pe
spen
nhot
s max { 3(s, x (s))
(8,,
|
}
+
5
span
span
neot
((s.
+ B(s, (s))
||
+
5
span
span
Root
where we used Lemma 1.14 and the fact that ( (P (o))
D pe
in the
po
span
span
2 and then bounded the max by the sum.
first inequality, then that V P
<
pe
pe
span
(While Lemma B.14 is stated for B(s, x² (s))
I 1, if B(s, > 1 then (o)s (Por- (s): V7o')
is a constant vector so the bound is still true.)
Now since i/ satisfies Vpp rr- - 70' + P.
Da we can rearrange to obtain that Vx = (T pe
pe
y - (In.--70) Likewise by the standard Bellman equation we have that V* rr +yP P V** so V* = (I - -ypp- -1r,,. Then we can calculate that
Vx 7r
= (I (I- -Ppx)) 1x (I--/: 7P.) (- (r 70") -17)
pe
(I - -pp..) (I 7P,
(II ((x
Txx
- (1 (P-7Pm.) ) (1 - yPa.) - -Pxx.) ) -1 (Txx -
= 71 (P. - Pr.)(1 - -P..)) + (1-7Px- 1176b
= 7( pp -((p. Pr.) +(I + -P..) ) -!7
(42)
Now we can bound
x
max(c, - exr) T
pe
span
8,8'
pe
max(e; - ex.) T (VT* + V
- v+))
8,8"
pe
S max(e, ex)) T (VT*) + maxies - ex.)
(Prz - -va)) pC
4,8'
2,5"
yT
+ max(cs
eT.) (vzz - vx¹)
(43)
span
3,3"
40

---

Fixing arbitrary s, E S and letting? & = - Eg', and using (42), we have that
<T
Vi pe
v: v=+)= = (7(1 - ((p.) (Pp. Pa.)v"' -1 (P--Pa-)-
< (I- - - -11 Pr | (
(44)
S 4Tit (P; x²) by Lemma B.11, and furthermore by Lemma B.17, since its conditions are satisfied under the conditions of the present lemma (since 2 log( 29 )) we have with probability at least 5 that Thi (P,
Next bound all the terms in (44). First,
(T
(P, x²) S 24Tm xP, Hence [< (1 7P-.) ) s 96Thie π²) Next, for any S, by Hoeffding's inequality, with
probability least 1 8' we have
Va
log (
(P - PP.)
SV
span
2n(s.T((s)
and so by a union bound over all & E S and setting 8 probability most that
S. we have that with additional failure
28 log(
|1 $
VT
max SES
span
2n(s, n (s))
Finally, using the bound (41), we have
| < max #ES V
8(s (())
xx
+ 23(s, π (8))
17
+
pe
span
span
neat
max 3 ((s,
3/53s, x (s))
span
Throt
because our condition on n(s, n" (s)) VB(s, (s)).
guarantees that (T)
<
1 so B(s) s
Combining these three bounds with (44), using that y I 1, and taking the maximum over all 8, 8, we have that
max(e, ear) (Vrr' -Va)
|||x0|
log( 29 (s x (s))
< (P
max SES
+ 3,
max #ES
((s,)(8)))
7
+
span
Neot
Combining this with (43) and rearranging, we have that
Dar pe
(1-3. 957-96Thii (P, x')
max B(s, (s))
span
SES
1 119hh PT)
max SES
log( 25)
969 (P, x*)
5
(45)
span
(5 n (s))
Thot
Noticing that 576 = 3 2 96, our condition on n2(s, ((s))* that
(s)) in the lemma statement is chosen exactly
1 1-3 3 967 (P,T*)
max #E8
((, (s))
- 1-3 96Thin (P, (P,x*)
max eES
n(s, (s))
1
2 1
2 2
41

---

log 2
Also since for all & E S, B(s, x² (s)) max max n [())--())]] 2 2m(s,x ( (s)) (since
llog( ( and n(s, n (8)) 2 4 so max क (8)) 1.1] = n(, (8) -1 2 2 n (8, (s))),
we can also simply bound
log( (3) 2n(s, π TT)) #ES
- s1+ 1
1 + 96Th 1+96Tha x²)
max
2
We can also bound 96T (,,, neot
I 1 (by lower-bounding Rott ( x (so)) for one arbitrary
80 E S). Combining all these bounds with (45), obtain
3
+1
2
pe
span
2
span
which implies
1
3
V
+
span
span
as desired.
B.8 Average-ewarrdoo-dssoootte reduction
Now we can combine our previous results and relate the discounted MDP quantities to p" and h" Lemma B.19. There exist some absolute constants C1, C2 such that the following holds: Fix
deterministic unichain policy π². Suppose that n(s, x (s)) 2 my. " (s) + 4 (576T (P, (P,""))
for all s E S, where a = 8 log 6.5 Artzan and that 1 least 56, we have that
I-7 2 m and I 2 2. Then with probability
(1-7)0
I-
CiS
[| Issan + +1)
C2S
(11**1 I|span + +1)
1.
m
Proof. By Lemma 1.16 (the conditions which are met here as a( (s)) (5767 his (P; x))² 2 4Thi P. x²) m))), we have under the event of Lemma B.8, which holds with probability at least 1 - 25,
that
max enES
(so)
(5o)
17 (so)
2048S
log
Ansat (1-7)6
640S
log
6.9 Areean [I-9]0
1
12
span
span
+ (1 ? M)
1-7
7)m
Combining this with the conclusion of Lemma B.18 which implies
P pe
3 (||V**) span + 1)
span
and adds additional failure probability at most 26 by the union bound, we have that
6144S
(IV**1
span + 1) log
65 Anica [1-7)6
max 50E5
( (so)
p. pe (5o)
S
1
m
1920S
(||VT')
+ +1) log
6.5 Arsos (1-7)6
span
12
7)m
(1 7 Meot
(46)
For convenience abbreviate the right-hand hand-side of (46) as E. Then since Qa > Q by Lemma B.9 (which holds under the event of Lemma B.7, adding additional failure probability most d) and
Q
Q pe
1 by Lemma B.4, we have that
Intel
v R Q M³ > M @ūp- 2nrot 1)
11)
1
V pe
1 1.
2nror
2n
(47)
42

---

Furthermore we have
(i))
(18)
De V=
c1
p
V
E1
(48)
where (i) is due to Lemma B.1 which gives Qie 2 0% which implies Vi = MQP
pe 2
M
2
M Q using monotonicity of M (ii) is due (46), and (iti) uses V* 1- p"
V sppn due to Zurek and Chen [2025a, Lemma 6]. Also by Zurek and Chen [2025a, Lemma 6].
we have the elementwise inequality p 2 (1 - 7) (minges V v²())) 1. Thus
7) min V (8)1 SES
1 1-
min 7 (s)1
#ES
2ngor
min p= (s)1 - (1 - 7) #ES
|
1- (1
- 7)c1
1 1 7
span
2noor
(i))
p² - (1 - --) |M
1
6144S
(IVV*
"ly="llsom + 1
log
6652 Aniea (1-710
span
2noot
1
19205
(|
11
1spn + 1
log
Annas (I-7)0
12 Phot
m
6144S
(IIV** span
+
log
GS2 Aniat
1933S
(IIV**)
span + +1) log
[o5² Areus
(I-7)8
(1-2)6
m
where (i) uses (47), (ti) uses (48), (tii) uses the fact that p² is assumed to be state- itute-independent and the definition of e (and cancelingssimplitinngg) and (iv) uses that T- 2 m (so (1 7) S J ) that 1 1-7 S 1, and Thot 2 m.
Furthermore, using Zurek and Chen [2025a, Lemma 26) we have (since p" is constant) that
[|V" Ilapon < 2 <2| Ispannn Combining this with the above bound and letting C1 = 2- 6144/88,48880 C2 2 1933/8, we obtain the desired bound.
B.9 Completing the proof
Here we complete the proof of the main Theorem 3.2 by checking conditions and simplifying previous results. The following result is actually more general than Theorem 3.2 because it allows arbitrary unichain deterministic comparator policy x² rather than requiring π to be gain-optimal. Theorem 3.2 follows immediately from the below theorem by adding this additional requirement that pT = p". Theorem B.20. There exist absolute constants Ci, C222 such that the following holds: Fix 5 > O. Let 7 1_ and a 8log (6S* Ansot), ). Let x² be a deterministic policy which unichain with stationary distribution μ²" Suppose there exists some m E N such that
(1-9)66
Diot
n(s, TT" (x)) 2 mp (s) + a Thi (P, (P,**)) x²))² +..
Then letting ã be the policy returned by Algorithm I with inputs D, 11 with probability at least 1 56 that
and ô, we have
Rear
Ci (1s (1 U1sat span + 1 a
pa 2 pT
Proof. Note that the condition n implies that Trro 2 4, so setting
1 = 1-
has
1 I-y 2 2. Also
we have
P4oo 2 Σn
nsss 2 Σ mp= (s) = mm
SES
#ES
43

---

using the assumption on n(s, (s)) for all 8, setting 1 Ntot also ensures 1 2 m. There- 1-y
fore we can apply Lemma B.19 to obtain that if n(s, x =*())) 2 my (s) ++ (576Thu x*))²
for all s S, then with probability at least 56, we have
CiS
(117*1 lpaan + +1)
C2S (11c
Isan +1)
1
77
772
where a log 665 (1-7)6
= 8 log
6682 An
Thus we can set C22 576. To choose C₁, note
5
C2S b qm
+1
that since trivially p"
< and p² 2 0, if the term
then the bound
C2S
(11511
Il +
+1)a
0² 2 pr
m
holds vacuously, and otherwise if it is < 1 then have
G
(110*1lppm + +1)a
C2S
(11TT) Us +1) a
p² p
17
m
since V 2 for E [0, 1]. Since Va + vbs 22(a b), we can take Cj 2((1 + C2).
L
C Proof of Theorem 3.3
Let 2 4 and m E N be arbitrary.
Step 1: MDP construction Define p 3m++7j A
pr and AT- The set of states is
S = (0. 1), and the set of actions is A = {0, 1, 1,... A
1). The reward function r S A (0, 1]
is defined by r(0, a) and r(1, a) = 0 for all A. We define an index set θ = (i. b) E
(0, 1),b E
A - 11}. For each A = (i. b) E θ, we define the transition matrix Po as
follows:
8
a
Po(s'|s, s a)
0
i
I(s 0)
0
1-i
(1 - p) I[s' 0) + pll( = 1)
0
22
T(s' =1)
1
b
IT(s' = + +1 1) I(s'' =1)
1
*
ql((s' = 0) + (1- 1('(s'=
44

---

T
p
0
1-B p
Figure 2: Diagram of the MDP r). Arrows splitting into multiple dashed arrows indicate stochastic transitions, and each dashed arrow annotated with the associated probability. Blue arrows represent action 0 and red arrows represent action 1. In state 1, the red arrow also represents actions 2,..., (which are all identical). The reward function does not depend on the action, and is +11 in state and +0 in state 1. In general, the MDP (P(r,), r) is similar, except that the blue arrow in state 0 represents action and the blue arrow in state represents action b.
See Figure 2 for diagram of the MDP (Po.r) for 0 (0, 0). We state easily verifiable facts about the MDP r):
The unique deterministic gain-optimal stationary policy T is the one that takes action in state and action b in state 1.
The optimal gain is P p -
(1) 0. (0) 1 and pg =
|
The policy hitting radius (Po TH), the optimal bias span are all at most T.
and the diameter span
Suppose stationary policy x usually makes the wrong decisions specificalll π (i]l)) and π (b/1) < 4 Then P3 <
4 4.3+(1-40 I 50+
< 2. In words, our choice
7
of is one that sufficiently large so that randomly guessing the optimal action state will not yield good policy.
Note that action 2 in state is added to keep the diameter bounded by T. and actions 3....,4 in state simply keep the action space independent of the state, consistent with our upper bounds. Since actions 2..... we will assume that (aa(0) 0 for 2 2.
in state 0 are always suboptimal, whenever we consider some policy n,
Step 2: dataset construction For any E (0, [ denote 48 = [ log (+) We define n + N by m00, 0) = n(0 1) = m ts and m((,a) = ts for all a E A. Observe that this choice of satisfies the desired requirements. Indeed, since (4)
"i (0) 1 and 140" - (1) 0, have
T
n00, (0)) r0 m + log
= mp (0) + log
6
8
8
and
m1,, +T()) b)
T
log
1
mp áe
(1) +
T
log
1 8
6
Step 3: impossible to do well in all MDPs algorithm s that maps the dataset D stationary policy म o (D) such that for all 0 e O Fe. (p) I))
Suppose towards a contradiction that there exists an
45

---

Before proceeding, we define some events. Let B be the bad event that D contains no transitions from state 0 to state and no transitions from state state 0. Let Eg be the event that { 2
(t prefers action O in state 0). Similarly, let & be the event that o o 2 (fr prefers action in state 0). For each a E A, let Fa be the event that (aa11) 2 4 in state 1).
A (# gives significant weight to action
key idea is that under event B, the dataset the same no matter the underlying MDP. That is, under event B, we always have
D = Ou.e اليي
2n(0,00 times An(1.0) times
It follows that for all 0, E
Pe.n (E, B) Po (E
Vi {0,1}
and
Po,n (Fa B) = Po. (Fa (B)
Va E A.
For case of notation, going forward will drop the subscript 0, when it does not matter what the underlying MDP is.
Since EE U (3) = 1, we must have (P(Ev) [B) 2 2 for some i' E {0, 1). Furthermore, for some a' E A we have PFFF' B) s J. equivalently, P(F. [B) 4- Indeed, if this were not the case, we would have
4 1 =1 A 4
E
Σ (a
B
E [[a[| Σ AEA
B]
Fan [E
Σ
aed
which is contradiction because we always have EaEA #(a 1.
We have shown that when the dataset does not contain any useful transitions, there must be least one MDP where the algorithm is likely to make a poor guess. Our last step will be to combine this fact with Lemma C.I which tells us that the dataset will be useless with large enough probability. We
noted above that when the underlying MDP is (P(y ["",""))' r) and a policy π satisfies (i'(0) < 2 and T (a'l1) < 4 Subsequently, for O' (1', a'), we have
A we have Plataa)) < In particular, under the the event Eg n.F we have P(y,a') < 1
Por,n P0 -
2 Po (E 2 Po BB
45 = 8,
4
where the final inequality follows from Lemma C.I. In summary, we have shown that
(D) 1
max OEe
18 Pá Po 2 8,
as desired.
C.1 Auxiliary lemmas
Lemma C.1. For all A E ④,, we have (B) 2 46.
Proof. By symmetry PB) equal for all A, for ease of notation drop the subscript O. Let Bo be the event that D contains no transitions from state 0 to state 1, and let B, be the event that D contains transitions from state state Then
P(B) P(B, n B1) = P(B))P((1..
with the last equality following by independence. Now,
P(Bb) = (1 - p) mts. Recall that p = 3(+77)- In the case that m 2 La, we have
2m
1
(1 p) m+tss >
(49)
6m
e
46

---

with the last inequality following from Lemma C.2 with 2m and c = 3. Otherwise, when m tg, have
26s
p) m
2
2 46
(50)
6T
with the last inequality following from claim 3 of Lemma C.3 with x = 27. Combining Equations (49) and (50) and the fact that 48t/3 < L, we have
P(B,) 2 461/3
Next,
P(BB)) = 7) (1 ()(1-1)6,
Claim Lemma C.3 with x = gives us that (1 ) 2 81/3, Moreover, recalling that AT have
Ats AT. Hence, PPBB)) 2 82/3.
(1 - (A-1) (1 a)
2 82/3
AT
with the last inequality following from claim 2 of Lemma C.3 with and consequently, IBB)) 2 48.
Lemma C.2. For all x 2 2 and c 2 2, we have
1
-
Cx
c
Proof. We have
(1-12)
1
log
x log
1
c2
C3
x
C3
2222
C2
2
-1
log (
where the first inequality follows from log(1 3) 2 y 2² for 00,0.6)). Since log xr is monotonically increasing, we are done.
Lemma C.3. For any x 2 4, the following holds:
1. For any e (0, 1] we have (1 (1-1) log(t))
2 6.
2. For any E (0, 3. we have (1 - 2) log( lng(:))
2 61/3
3. For any E (0, }. have (1 - 1
log(
log
481/3
Jec
47

---

Proof. We will prove claim by showing that (1- 22 have
1og(+))
2 8. For any æ 2 4 and E 2)
(og()))
log (1-1)
1
1
log
+ 1
log
1
log
+ 1
x2
log 6
2x
x
x/2
5
log 6
8
16
5
5
log 0 +
log
8
16
1V
log 5
16
Iv log 6,
where the first inequality follows from log(1 y) 2 y - 3²² for E [0, 0.68.. Since log x is monotonically increasing, claim follows.
For claim 2, take 2 4 and å (0, ]. Then 8' = 82/3 E (0, ! so by claim 1 we have
a los(
$ log (1)
=(1 -1-
1 1--
2 8' = 81/3
Finally, for claim 3, take x: 2 4 and 8 E (0, }. and let 3r. Since 8' = =01/3 E (0, + claim gives us that
I 1on( !)]
[ loo( }1
1
1
2 18))1/3 2 481/3
3x
where the last inequality holds because 8//3
D Proof of Theorem 3.4
We define the absolute constants = 4 and = 33. Let T > C1, S 2 k > 0, and m 2 max(TS, kS} be arbitrary.
Step 1: MDP construction Define S' = S - 256 Note that a S 256
Let p = فاS and q = J. The set of states is S =
and the set of actions is The reward function r x + [0, 1] is defined to be when *
A = (0, "0.,,...,,'),, S'). and a < 1, and 0 otherwise. We define an index set = {0, 1]s5 For each θ, we define the transition matrix Ps follows:
8
Po(s'|8, 8,
0
0
q)ll(s 8) + x I(s s")
0
2
(1 T)((' = s) + 23
) T(s'
8 >
0,
[1 (1-p)l(s = + pllss =0
$ s21
1 0
(1 (1- I)] = qIl(s' =
8> 2
} I1((' 1) + 1
2>1 I(s' 8") T(s' s")
# 8, 2 2
i [I((' a) + 25 "
48

---

5
Figure 3: Diagram of the MDP (P(o....0); r) only including actions and Arrows splitting into multiple dashed arrows indicate stochastic transitions, and each dashed arrow is annotated with the associated probability. Blue arrows represent action 0 and red arrows represent action The reward is O at state 0 and the reward is at all other states. In general, the MDP (Pe,r) is similar, except in each state 1, the blue arrow represents the optimal action 0..
Observe that the decision- maker needs to decide between two actions in states ,,..., S". Both actions give an immediate reward of but one action has slightly higher probability of transiting to the bad state 0. At state O, which has reward of O, the agent will likely be trapped for a long time before returning to one of states .,.... S'. See Figure 3 for diagram of the MDP (Po, r) for 0 (O.....07 0). We now state some easily verifiable facts about the MDP (Po,r):
The MDP has S states, is unichain, and has diameter
1/2 -+2-1
There is unique gain-optimal policy иÿ. It takes action in state and action in state for 2 1.
< M' (0) , = -- By symmetry, it follows that p. ró (s) 1t4
1/5" for
18
--
8 2 1.
The optimal gain is P 1 140 n (0) .
Note that actions S' for states & 2 are always suboptimal, and only exist to keep the diameter bounded by T. Furthermore, actions 1,..., S" in state 0 simply keep the action space independent of the state, consistent with our upper bounds. As such, whenever we consider some policy म, we will assume that may only take actions 0 and in states 2 1 and action in state
Step 2: dataset construction
We define n S A + N by n00, 0) = 77 and
2m
n2s, a) 5
for all 8 2 1 and a E 10, For all other (8, a) we set niss, a) = 0. Observe that this choice of n satisfies n(s, (s)) S + mp (s) le for all S.
Step 3: reduction to estimation Given a stationary policy æ and some 0 E e, let Lī(s) be the proportion of incorrect actions π takes in state To be precise, define (g(s) TT(1 0.(s). We also set LØ = ES" (s). By Lemma D.I. we can upper bound the gain of policy in terms of Lg:
1 1 e
p 2 - E(1 LT
Subsequently, for any stationary policy n
1 82
eL L 2
P9 p 2 5
(51)
5 L S')
49

---

Now, suppose the underlying MDP is (Po,r). Let of be an algorithm that maps the dataset to stationary policy मे (D), and consider the estimator 0 whose sth coordinate is #(]ss). By the definition of r.g. we have L. = 0 f Our next step is to show that no estimator can achieve low & error uniformly over θ with high probability, result which will lower bound Lg and consequently also the sub-optimality of ā for some 0.
Step 4: Fano's method We will achieve such lower bound with Fano's method. First, by the Varbha-- Lemma (Lemma D.2), there exists some subset O' C O such that | 2 /8 and ||0 - 0' [a 2 5"/8 /8 for any 0 o 8' E O'. Since maxp,0'ee KL(Po,.. a.,. || PP & (5' 16 1) log 2
by Lemma D..3, Local Fano's (Lemma D.4) gives us that for any estimator 0,
|1o- - [11
S'
(1
(56/16 1) log 2 + log 2
8
max Bg.n 6
16
log (25%/8)
32
which implies that
(10-0)
S' 1
max Pe p.n
64
Since the above holds for estimator of the dataset, it of course holds for 0~ where sf is any algorithm that maps the dataset a stationary policy. Therefore,
(L
5¹
max Po..
2
(52)
64
64
Now, by Equation 51, the event that
1.0
(P(
>
p
Pg
E
e/64
2=²
E
1-1
TS
4
512
with the second inequality holding by S
Thus, plugging back into Equation 52 yields
256
(DD)
TS
max Po.n
Pb
Pa
>
03
2
64
with C3 = 2-17
D.1 Auxiliary lemmas
Lemma D.1. Let a be a stationary policy on MDP Mg. Then
1 s2
p 2 - E(1 - ST
Proof. A routine computation (see Lemma D.7) yields
$ Σ
1+ ==1
where K, = (1- 1-s(1-L3()) (+))
is the probability of transiting from state to state for x > 11, to achieve the desired upper bound
under и. Since 1+x monotonically D
for P it suffices to find an acceptable upper bound for x= = ES 5' - 1-((1-13()))
Defining (x) = 1-z and X =(1 LØ (s)), we have that
g'
s(Aa).
S
50

---

We would like to get bound that looks like f f f - This goal suggests applying Jensen's inequality, but since f' is convex for x < it gives an inequality in the wrong direction. It turns out, however, that because f is nearly linear in the sufficiently small interval interest, we can obtain an inequality in the right direction with some error term of lower order.
Since Ag E for all s E {L...., Lemma D.6 give us
+ +5(0) ((e) 25 (
ASS
5
1 2
+1+
1 c(1 1,755))
1 - -//2 1
$ 1 c(1 17)
+
where the last inequality holds for 3.2 Consequently,
+ +
A 1+ --11-11//5 +
S 1 E
P
e(1 L//S')
Lemma D.2 (Gilbert-Varre Varshamov Lemma [Massart, 2007, Lemma 4.7l). Let d 2 8. There exists Q2 {0, 13dd such that [S2al 2 24/8 and ||l w'll2 2 d/8 for all # w' E Sla-
Lemma D.3. For any 0, 6 E θ, we have
S' log 2.
S
16 -
Proof. Let 0, e O. By the construction of Pø,n and Pø .ss we can decompose
KL(Po,n Po
Σ [(s.
s, Po Pa (-)8,a)).
==0 (0.1.
Recalling our choice of n, we can further simplify
2m S (L.(P(-ls,,)) (+) s, s,) +
KL. .n) =
1)))
where we remove the 8 = O term from the sum because the data coming from state 0 has the same distribution for all possible MDPs. Observing that
2(p -2
D)
2xa
&c2
p(1 p)
(LSS) (2)
5
D
we can apply Lemma D.5 to further simplify
s'
2m
KL. Por,a)
Σ
(KL(Po(-
ss Po 0)) + KL((0(- (1,(--(ss,))) (-
S
2m
(KL (Ber(p) Ber(g)) KL (Ber(g)) Ber(p)))
8
< 2m
D
8 2 16 TS
2m
T
2 5'
S'
< 16
-1)
log 2.
The final incquality holds due to the assumption that S 33 S' 32.
51

---

Lemma D.4 (Local Fano's inequality (Wainwright, 2019, Proposition 15.12, Equation 15.34]). Let be class of distributions with parameter space θ and ler [I....., ,,,, C C.P. Letting ( E Q denote the parameters P, define 5 = minjæ* | - ((Px) For any estimator 8, we have
(
ô m.x (L 3 || 1k)) + log 2
sup E PEP Drup
>
2 1
log N
Lemma D.5. For any p. 4 E (0, 3. satisfying p < q. we have
KI. (Ber(p) Ber(g) < Kl. KKI. (Ber(g) [Ber(p)) - (p q)² p(1 - p)
which implies that
2(p - 9)² p(1 p)
KL (Ber(p) || [Ber(g)) + KL (Ber(g) || Ber(p)) -
Proof. By Lemma 10 in Li et al. [2023], have
KL (Ber(p') || Ber( ) 2 KL (Ber(q)) BBr((p))) (p' -22
p'(1 p')
for any p' E [2 satisfying p' > q' The desired result follows immediately by taking
p' p and o' 1 q. along with the observation that KL (Ber(1 p) Ber(1 4)) KL (Ber(p) (er(g)).
Lemma D.6 (Theorem I in Simic [2008]). Let = [a, b] be a closed interval with a, E R, < For some E Zt, let 21.... In L, and let Pı..... Pn 0 satisfy E Ps = 1. If f [a, b] R convex, then
EpS( Sf
1
ΣEP PiJss
T1
+(a)+ ((b) 2f
a (a+ b
Lemma D.7. Suppose the underlying MDP is (Po.r). Let v be a stationary policy such that for
each # O, if the current state is then the probability of transiting state 0 after taking action
according to π. is Rg. Then
S'
2==1
K2
1 1 87
a=1
Proof. We first solve for 2g (0) by considering the balance equations for the MDP (Pe, For each * O, have
4 - 17 + (1 kz) (s).
Rearranging gives us
(8) = 9
S 16 (0) (0)
Ris
Since Σ 16 (s) = 1, we have
S'
9'
pg = Σ (x) = 1 11 (0)
!
Σ
5
R
s=1
We then solve for (²((0) (0) obtain
1 (0)=
1 g ES
Since the reward is in state 0 and all other states, we conclude that
3. -. R.
1
p = 1 ==-#((0)
1+
1 2
5'
52

---

E Deferred proofs and auxiliary lemmas
E.1 Proof of Lemma B.2
Proof of Lemma B.2. Letting V, V E R satisfy V 2 V' elementwise, we seek to show that
T (V) T (V').
Since this an elementwise bound, we can fix arbitrary & E S, a E A and show that pe (v) pe (V') a). From here on, since s, are fixed, we abbreviate B(s,a) E as for notational convenience.
Consider the simpler function T RSS R (which depends on our fixed s, a) defined as
T(V") == PaaTx(Pso V") max { v pV [To(Pmn [a) To(P v") span
for any V E RR Note that
T pe (s,) = r(s, + max
PsaT's T3 V") b(s,b((ss) a, mii").mii""((
{
(T(V") min (sn)
= =((s, + max
noot
Therefore, if we could show that
T())) then since clearly V V iiplies min. (V)nn((V(5)) 2 (Vn)'. we could immediately conclude that
(53)
T pe (s) r(s, +ymax [(()- (in()))s)) }
Neot
2 r(s, + (T(V)) min((V)
=
desired.
Thus we now focus on showing (53), First we can quickly handle the case that 1, since this case for any V" E R$ we have Ta (Pan, V" = (ming V'('') 1, and then
T(V) P.a Ps To T (P.,, V) max | pV [Ts(pea P..a..V]. (TsSTTT(Pem }
min v(s')) p.o 00 min V(ss)
2 min V'(s)) = (min V's'') 1-
P. PP... V\ max VOVP.
[TolPees Vi) .3 To m
span
=T(V"),
confirming (53). Now we can focus on the case that B < 1.
The fact that means that the following expression for T3 holds: for any s' E S and 4 CRS. we have
T8 sa. (s' = min (s") ( vn}}
where Qp(Peus V") sup(v"(z)) : : S. Poa > 3} is the 1 - 3 quantile of " with respect to P.. (in words, choose the largest (z) such that P... places probability at
53

---

least 3 on states x' with ("(x') 2 (x)). We will make use of the function Qa shordly We also make the useful definitions
(VV) PooTo(Pan v) v) 3 r 1al 1310
TV(V) Poo V) 1OVVp.. Pma [T((Pon, oa. v)
so that we can decompose T as ((V) min [(v) To show (53), suffices to show that this holds when V differ only one coordinate, since then we could decompose V V' + Eves (V VV) and apply the inequalities T 7VV'
-V)) 1
T ((V'+ ee -n) for each k I. Therefore we fix one state E and
try to show T(V is montonically non-decreasing as (z)) increases (with the other entries of V held constant). We will show this by using Lemma E. which says that a univariate function is continuous and at all but a finite number of points has a non-negative right derivative, then it must be non-decreasing.
First we justify that T is continuous. Since we have decomposed T as the composition of many continuous functions, suffices check that Qs(Psa: V) a continuous function of (ar). This follows immediately from Lemma E.3, which shows 1-Lipschitzness (We remark that the B quantile is well- knoln to be discontinuous in 3, a fact which is irrelevant here since 3 is fixed and we instead vary (zz).
We will now compute the right derivative at all values of V(z) such that V(x) is not equal to V(s") for some other s' E S with s' * x (which is a finite set). We define some new notation for this purpose. With respect to this fixed value of V(x), let Sy {s' E S V(s') > V(z) and Sz = {s' E S V88) < (.x)). Define a neighborhood of V(x). the open interval U ==
(maxyess V(s',, mis V(s)). Let V IRS have V'()) V(s') for all s' * x,, and we vary V'(x) within the neighborhood U of (a)) in order to compute the (full/wo--ided) derivatives (V') (z) ((=))=((z)
and d' (v
Once we have computed these two derivatives, we will
V(x))
be able to compute the right derivative of (VV), since if both T(V)) and Tz (V') differentiable
a point (z), then by Lemma E.2 the right derivative of T(V') satisfies
dT(v))
d
mii (T((V))
(V'(+) V(a)+
dv'(s) (())-V()))
(V")
7((V) < Ta())
(=) v(()=V((s)
aT.(V")
TiV) Fz()).
dv'(x)
v*xx==((x)
dT(y')
((()) = =z(V)
min
(V (')===((a)
av'(x)
((()=v())
(54)
To compute the derivatives of (V') and (V'). we also analyze the functions Qo( se, V') and
(s(P.a, sa. V') on the set U (all considered as functions of V'(z)). For any set S C S, let P.o (S')
Eves (s).s'). We define three possible cases depending the (fixed) state
3 3
(55)
P PSa < 3 Psa + Px)
(56)
P (S,)))) Pea(x) <.
(57)
1. In case (55), we have Qs (ra, V')= = V) on the entire interval U and also that for any V'(x) E U. (p s0, V) > V'(x) (since the (1 -)peecnet is achieved at some
54

---

state s' E E,), so Tg(Pea, (')x) = (x) and Tp(P.a: V') = TT (Pec. (s()) for all
s' # x. Therefore
dT sa (')
{1 s = x
(z)
0
otherwise
v(()=V((2)
and (V')
PraTa(Paas vn) 3 T 1n) 1')!_n]
17)-3111
dV'()) (+)=v(v())) dv'(z) ((())V()))
d dv'(x)
(PraT V') - -3]0s(p Vn) + Bmin V ('('))
((())-
d dv'(.)
( V') - (Qp(( V) m V'(s')
((x)))((x))
=
(r)( 3 2 Ps)(t) 20.
00
otherwise
2. In case (56), we have Qs(Psa: Vo V'(x) on the entire interval U. Thus
(Pn,, Ta Ta sn, (''( = V'(x) if s' E Sz u {z}, and Ta(Paa, sas V'{() = v'(s)) = v(s))
for s' E Sc. Thus
dTp sa, V')(s)) (v)
[1 EESuU(z)
otherwise
(((x=V(())
and dT'()')
PeaIo(Paar Vn) - 3 To rn)l
dv'(z) (()=)V()) (v)= dv'(x)
d
(PeaTo(Pan Vn) 3Q0 eu V¹) + Bmin v'(s))
dV'(z)
(()))((()
d
(PenTo(P sa: (V)) + 8 min V'(s')
(x)
dv'(x)
(()=)V(())
(1 S =0
Ps, U (x)) 3 + 3
(0 otherwise
> Pa, U (x}) -20 0.
3. In case (57), we have @s(P.a. sa, VT) Q2(Pau Pas V) and also that Tz(P.s.
sa. V'(())
2 V) < V'(x) (since V'(x) < (Ps: V) in this case), so T3 (P Pa. V')
[p sa. V) on the interval U. Also min, ('s') < V'(x) U, so ming V'(s') ming/ V(8)) on U. Thus
dT d say V') dv'(x)
=0
V2(2)=V(())
for all s' E S, and
dV")
PooTT(PPn V') -")-3Q0 300- (P V") + 3 min V v'(s')
(v))
dv'(x) (()=)V(()) d dv'(s) (()))vV(a)
PaaTo(PPn V) - 3Q2 V) + m V(s')
0.
55

---

Next we calculate dTa( (²)
First, letting T E R if if. P... [T] o 0 then (recalling P.u is
(+))=V(())
row vector so PT is a column vector)
sa
( (PI)02)
VT
2 V
P.o (T)
P oT (Pao T)
V P... [T]
PT sa
(T' (
(Pxat)1)
VV P... [T]
| span
(58)
VVp... Wpp.. [T]
8G
where the final inequality is elementwise and uses the fact that for any 8' T(s') P < max," T(s")- "minn" T(s") = ||
||T span Now we will combine this calculation with the chain rule to
lower bound (V') (=) ((x)) Note that in light of (54), we only need to bound (V2
(v' ((())=((x)
when TVV (V) or equivalently when our fixed value of ((x) satisfies
Ve Ts(Pan. v) vB Ta M)
(59)
span
Since we have already excluded the finite set of values of (zx) where V(x) is equal to V(s') for some other state s' * I, the only way for Vp... [Ta(P... v) 0 is if (x) 1, but in that
case we have T sa, v)
0 which contradicts (59). Therefore we can calculate that if (*))
span
satisfies (59), have
dV²) (z) ((()=V(()) dv'(x) ('()=V(())
d
PaaTo(PPss V) 1V [ToPPaa oa. r)]
Σ
8
(PeaT V P. 171)
dTo(Pen V') dV'
(T
(P..
E'S
v((=)=((a))
0 V P.m.
(T]
dTo Paa: V'((s) dV'(T)
Σ
Pra(s')- 3
0T(s')
T(o)=Ta(PP..
SE
V((a))
To((Pa v)
dT (Paa V')(s)) dV'(x)
2 Σ
Pea(s')- -3
span
Pools')
3
V [To(Pen.)] v) V')(')
('(o)=V(4))
aT sas
Psa Ps'( Pro()))
dV'(x)
3'ES
v(x)=V(())
where the first inequality step is using the fact that (Pa(PP..''(''')
0 for all s' (verified
(v'
(=)=))V(aa))
above in all three cases) and inequality (58), and the second inequality step uses (59).
E.2 Auxiliary lemmas
Lemma E.1. : - R is continuous function that has a nonnegative right derivative for all but finitely many points, then is monotonically non-decraasing.
56

---

Proof. We make the following claim: for a, b E IR with < b. if [a. - R is continuous on la, b] and has nonnegative right derivative on (a, b), then f is monotonically non-decreasing on ba
We first prove the lemma assuming that the claim holds. Let
I be continuous function that has nonnegative right derivative for all but finitely many points. Let z, // E RR satisfy I < and denote by d1..... On-1 the points in (x,, y) where ff either is not dithreiifferettiblee has negative right derivative. Also denote [a:-1.0] 0g] for each i I,..., n. Hence faz f(a)) S f(a1) S .... S f(an) f Since r and y were arbitrary, we conclude that f is monotonically increasing.
x and a2 = y. By the claim, f is monotonically increasing on
It remains to prove the claim. Let a. b I with < b, and let [a, b] + R be continuous on (a, bj with a nonnegative right derivative on (a, b). Suppose towards a contradiction that there exist Jr [a, bj such that < y and (xx > [v). Since / is continuous,
assume that (if
I = a we have x + 5 < y and f( + 6) > (v) for sufficiently small 5 > 0).
Now, set r := [()))((w) 0 and
8-v
f(t)- 1-
f(t) - f(x) r 2
:: inf t t (z,z]
Consider the case where 2 = x. f has a nonnegative right derivative at x, so there exists w E (z, vl such that ((m) for all E (z, w|. However, this implies a contradiction:
2 = inf { t E (æ.vl
f(t) f(x) r t-x
{ 2E>I=2 2
We next consider the case where = > x. Note that by continuity of f. the function g(t) == f(0) 2-z continuity of g there would exist 8 > 0 such that g()) > for t E [2, z + 6). which would imply that would imply
t-z
continuous on (x, w]. follows that g(z) = [(x)-((x) = 5. Indeed, if we had g(z) > 5, then by
2 + 5. And by similar argument, g(z)
5.
At a the right-derivative is nonnegative, so there exists w E (2. yl such that 1(0-((s) > for all t E (z, w). Consequently, for all t E (z, w). we have
t-8
f(t) - f(x) = t- (f(t) - f(z) - t-x
1 ([(t 2) + (z - -x)) =x))== r
f(2) - f(x)) >
= 2'
t- 2
which implies the following contradiction:
z inf { (x, vl
f(t) f(t)- f(x)
w 322
1 x
Lemma E.2. Let f.g: R be differentiable some R. and suppose f(x) g(x). Then 6: + R defined by ő(t) = min(f(t),g(t) is right-differentiable at x, and its right derivative satisfies (4 = min((((x))
Proof. We first consider the case where f((x) < g'xx). Since lim f(x+h)- f(x) dt
lim s(o+h))-((x) there exists some 5 > such that f(x+h)-((z)) g(x+h)-9(x) for all h E (0. 8). Subsequently, since fxx = g(x), we have f(x + h) g(x + h) for all h É (0, 8). It follows that o( + h) = f(r + h) for all h E (0, 5), and thus
6(x + h) o(x)
f(x + h) f(x)
lim ++
lim ++++
Next, the case where f'(x) > g((x) is identical to the previous case except we swap the roles of f and g.
57

---

Finally, we consider the case where f((x) - = (xz). Here we can even show that Φ is differentiable at I. Let fnn be a sequence such that hn O. To show that alath.)) Since [(x+h,)- 1(x)
f((x), fix
An (x) and g(+th,) > g(x) (x)), there exist Ni, N2 E N such that An
bn
f(æ + hn) f(x) (x)
n 2 Ni
S
hn
and
g(x + hn) - g(x)) g((x)
n 2 N2
S.
hn
Taking N = max NN1 N2 we have for all n 2 N.
d(x + hn) ((x)) fx(x)
hn
f(x + hm) - -f(x) f'(x) g(x hn) g(x) - g (w))
< max
hn
hn
< max e,
where the first incquality holds due to f(x) = g(z), f()) g'x),, and the fact that for each n, either 6(z hn) = f(r + hn) or ø(z + hn) = g( + hn). Thus, we have that s(oth))=0(z) - fx))..
Since the sequence inn was arbitrary, conclude that
Φ(x + h) 0(x) f((x) (=))
ø' Φ'xx)
lim h000
h
Lemma E.3. For any probability distribution E RSS and any B E [0, 11. the largest-(1 - 3) -quantile
function
Qo(u, = =
Σ
p(x') 8}
satisfies
1Qs(,,)) - Qolu, V'I & V V'
for any V.V' E R.S.
Proof. First, we note that the definition of Q2 can be written equivalently as
Qolu, V=) = sup
min E'ES'
('(s)) : C and Σ m(s') 2 8 S'ES'
Without loss of generality we can assume that Q3(4, V) 2 Qs(u, V'), so it suffices to lower-bound Qs(u, V'). By the definition of Qn V) (and the fact that S is finite the supremum within its definition is attained exactly), there exists some set S' C S such that
Qs(u, V)
min V(8') E'ES
and Eves u(s') 2 B. Therefore since
v'(s') ((s')2((')) - IV V'lbo 2 Qo(u, V) VIV V'l
for all s' S², we have that
Qe(u, 2 Qo(u - VV |V
as desired.
58

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
All claims made in the introduction and abstract are substantiated in Section 3.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results
be expected to generalize other settings.
is fine to include aspirational goals as motivation as long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: Limitations of the work are discussed in the conclusion Section 5.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification. asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low images are taken in low lighting. Or speech-to-text system might be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach address problems of privacy and faimess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question:
For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
59

---

Justification: All theorems state all required assumptions, and proofs for all formal results are provided in the appendices.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proof's can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should properly referenced.
4. Experimental result reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [NA]
Justification: There experimental results.
Guidelines:
The answer NA means that the paper does include experiments. If the paper includes experiments, No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm. (b) If the contribution is primarily
model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome deseribe the particular way they provide for reproducibility, In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
60

---

Answer:
[NA]
Justification:
There are no experiments requiring code.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.. cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https: /CodeSubmic / //nips. wttpccccpppccccceeececccccccccct /ttpa///giiieeeeeeeuuubiiiiii ssisnnoillllo onPolicy))) for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [NA]
Justification:
There are no experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [NA]
Justification: There are no experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, at least for the experiments that support main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
should be clear whether the error bar is the standard deviation the standard error of the mean.
61

---

It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of enrors is not verified.
For asymmetric distributions, the authors should be careful figures symmetric error bars that would yield results that are out of range (e.g. negative error rates).
show in tables or
error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [NA]
Justification: There are no experiments.
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics https: httperrppp....ppppii//aattaaaaaa
Answer: [Yes]
Justification: Our paper does not have any direct negative socictal impacts nor any potential harms caused by the research process.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative socictal impacts of the work performed?
Answer: [NA]
Justification: Our paper focused on theoretical aspects of offline RL and therefore there are no immediate negative societal impacts.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no socictal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
62

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility MI..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: The paper poses no such risks.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Lieenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [NA]
Justification: The paper does not use existing assets.
Guidelines:
The answer NA means that the paper does existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com com/dataseta has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
63

---

If this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: The paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/mmoel as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question:
Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
16. Declaration of LLM usage
64

---

Question: Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods this research? Note that if the LLM used only for writing, editing, or formatting purposes and does not impact the core methodology. scientific rigorousness, or originality the research, declaration is not required.
Answer: [NA]
Justification: The core method development in this research does not involve LLMs any important, original, or non-standard components.
Guidelines:
The answer NA
that the method development in this research does involve LLMs as any important, original, or non-standard components.
Please refer to our LLM policy (https : httpe/rrpp..cc/oooeeeeeeeeeeeeee / for what should or should be described.
65


Reviews:
[{"review_id": "mnQYZopuwK", "reviewer": "Reviewer_wkNW", "summary": "This paper studies average reward offline RL. In average reward setting, distribution shift and coverage issues are amplified. The paper targets these challenges and focus on overcoming limitations of prior theory that relied on uniform complexity measures. The main contribution is an offline RL algorithm with guarantees that depend only on the target policy’s characteristics, rather than on worst-case MDP-wide constants. They introduce two policy-dependent complexity metrics which measures how long it takes for the policy to reach a representative state in its stationary distribution support. It then derive the single-policy sample complexity bounds for average-reward offline RL.", "questions": "I have no questions.", "limitations": "yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths: \n\n-The paper introduces policy-dependent complexity measures to characterize offline RL sample complexity, the bias span and the policy hitting radius. By depending only on the target policy’s dynamics, these metrics avoid the overly conservative uniform bounds. \n\n-The paper provides matching upper and lower bounds, offering a convergence rate $\\tilde{O}(\\frac{1}{\\sqrt{m}})$.\n\n-The algorithm deals with the weakly communicating MDP, which is more general compared to related work.\n\nWeaknesses:\n\nThe flip side of the paper’s single-policy focus is a stringent coverage assumption: the offline dataset must have adequate samples for every state-action pair along the optimal policy, even for states that the optimal policy would rarely or never visit on its own. This means the behavior policy that generated the dataset needs to have explored a bit of all parts of the state space (at least enough to “cover” the optimal action in each state). While the paper justifies that such assumption is provably necessary in the worst case, it still represents a potential weakness in applicability: if a dataset lacks any support in a part of the state space that turns out to be relevant, the theory suggests no offline algorithm can reliably avoid suboptimal decisions involving that part. The paper’s requirement is essentially to have at least on the order of $\\tilde{O}(T_{\\mathit{hit}}^2)$ samples for each state $s$ of the action $\\pi^*(s)$. In many cases this might be reasonable as $T_{\\mathit{hit}}$ could be moderate and this requirement does not scale with $m$, but in others it may be unrealistic. Thus, the results hinge on an idealized assumption that the offline data, while biased, is somewhat broad in coverage.", "was_revised": true, "final_justification": "I decide to maintain the current score.", "rebuttal": "Thank you for your positive comments. We agree that the transient data coverage assumption, which our lower bound shows is necessary, is nevertheless an assumption which may not always hold in practice. We believe that by identifying this obstacle, our work may help lead to future research which can circumvent this issue, possibly by identifying forms of side information which can be provided to algorithms to prevent them from failing in the difficult scenario where there is no transient data coverage. For example, it may be sufficient to have knowledge that all nonzero transitions have probability at least $p$ for some known $p > 0$ (enabling the algorithm to estimate the support of $P$). Also, as you mention, our work can handle more general classes of MDPs than prior work, and the amount of transient data needed for vanishing suboptimality is $O(1)$ (independent of $m$ and bounded in terms of $T_{hit}$ of only the target policy)."}, {"review_id": "5jX0cwl5cz", "reviewer": "Reviewer_88bt", "summary": "This paper concerns the problem of offline RL in average-reward MDPs, where, due to the long horizon, there are unique challenges in handling distribution shift and non-uniform coverage. As I understand it, the main contribution is establishing a statistical upper bound utilizing only single-policy complexity terms, namely, the bias span and a novel policy hitting radius. The algorithm utilizes pessimistic value iteration with quantile clipping. Lower bounds establish that single-policy coverage alone is insufficient, and that the dependence on certain quantities (such as $m$) in the upper bound are tight.", "questions": "Could you highlight the elements of your analysis or algorithm that enable you to derive single-policy guarantees? (and perhaps what was lacking in previous work?)", "limitations": "I think so", "rating": 4, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "I am not familiar with average-reward RL, so I'm afraid my feedback is largely superficial, and I cannot evaluate this paper well in the context of existing work. As far as I can tell the paper seems carefully done and well-written, and I appreciate that the paper investigates lower bounds against their positive results. \n\nSome parts of the bounds, such as $m$, were unfamiliar to me and so somewhat difficult to interpret from the exposition. Overall the paper is fairly dense, and I'm not sure how easy it is to extract or intuit which analytical or algorithmic interventions (policy hitting radius?) enabled the derivation of single-policy complexity results.", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your positive comments. We now discuss a few points related to your question regarding key elements of the algorithm and analysis. \n1. One key algorithmic feature is the use of quantile clipping and an empirical-span-based penalty function. This point is discussed in greater detail in the paragraph starting on line 195 as well as the proof sketch in section 4, but here we provide a brief summary. Using an empirical-span-based penalty term is essential for the average-reward setting, intuitively because it avoids a dependence on the effective horizon $\\frac{1}{1-\\gamma}$, which must be taken very large to obtain good average-reward performance. Naive implementations of empirical-span-based penalties fail (by breaking the monotonicity and contractivity properties of the associated pessimistic Bellman operator), but the new quantile clipping technique remedies these issues, getting the sharper penalty terms to work. As mentioned by reviewer Agk8/our response to reviewer Agk8, we feel like these sharper penalties may be of broader interest and utility.\n2. It is possible that a key missing idea from previous work was the observation that transient data coverage is required. Since this is shown to be necessary by our Theorem 3.3, it suggests that prior attempts to obtain convergence rates involving single-policy complexity measures without this assumption were doomed to fail.\n3. Many algorithms in the average-reward setting are plagued by the need for prior knowledge of complexity parameters (such as bias span or mixing time) in order to run the algorithm. Our algorithm does not face such difficulties, and we believe the analytical techniques we use to avoid this problem (discussed in the paragraph beginning on line 333) may be of independent interest to researchers working on average-reward RL."}, {"review_id": "ryNP3WxQOq", "reviewer": "Reviewer_6ZrZ", "summary": "This paper addresses the sample complexity of average-reward offline RL in the weakly communicating MDPs. The established bound only depends on complexity measures corresponding to the optimal policy, instead of being uniform over all policies. The lower bounds results demonstrate the unimprovable dependence on two novel measures, i.e., the *transient state dataset coverage* and the *effective size*.", "questions": "1. Is the *transient state dataset coverage* assumption only necessary for a small suboptimality $\\delta$ (as Theorem 3.3 requires $\\delta \\le e^{-9}$)?\n2. How does Alg. 1 perform in the unichain MDPs? Can it learn a near-optimal policy without the *transient state dataset coverage* assumption?\n3. In the hard instance (Section 4.2), the \"difficulty\" may also be explained by the *uniform mixing time*, i.e., it requires a sufficient amount of time to recover the transition from state 2 to state 1 for any arbitrary policy. It seems that both the uniform mixing time and the *transient state* are somewhat equivalent in this case.", "limitations": "yes", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 2, "originality": 3, "strengths_and_weaknesses": "* **Strengths:**\n    1. This paper presents a comprehensive analysis of the average-reward offline RL in the weakly communicating MDPs. The results improve over the previous work in two ways. First, the derived sample complexity bound only depends on the optimal policy. Second, two novel complexity measures are introduced, and the dependence is demonstrated through the lower bounds.\n    2. An interesting result is that sufficient data is required even for transient state-action pairs. This could provide further insights to the community.\n\n* **Weaknesses:**\n    1. The derived bound requires data from all states, which could be limiting in practice.\n    2. It is unclear whether the *transient state dataset coverage* assumption is fundamentally different from the *uniform mixing time* in the construction of the hard instance (see Question 3 below).", "was_revised": true, "final_justification": "The authors' response addressed most of my concerns. I maintain the acceptance of this paper.", "rebuttal": "Thank you for your positive comments. Below we respond to your questions.\n1. Question 1: In Theorem 3.3 $\\delta$ is actually the failure probability parameter. The suboptimality of the policy is $1/2$ (with probability at least $\\delta$) in the theorem, so in short, the transient data coverage assumption is necessary at least for any suboptimality less than $1/2$.\n2. The hard instances used in Theorem 3.3 are actually unichain, so the direct answer is no: even for unichain MDPs, transient data coverage is necessary in general to get a convergence rate scaling with the bias span of the optimal policy (as opposed to a uniform-style parameter like the uniform mixing time; see the paragraph beginning on line 263 for more discussion on which convergence rates are shown by Theorem 3.3 to be impossible without transient data coverage).\n3. You are correct that the uniform mixing time is large for the family of hard instances used in Theorem 3.3, so in this sense, uniform-mixing-based bounds would also suggest that these instances are difficult. However, as mentioned in the paragraph after Theorem 3.3, the uniform mixing time and the policy hitting radius parameter (as used in the transient data coverage assumption) actually behave in fundamentally different ways for these instances: as the parameter $m$ is increased the policy hitting radius stays bounded (by the other parameter $T$), while the uniform mixing time grows proportionally to at least $m$. Notice that because the uniform mixing time is $\\Omega(m)$, any offline RL theorem with a convergence rate depending on the uniform mixing time like $O\\left(\\sqrt{\\frac{\\tau_{unif}}{m}}\\right)$ (in the best case/ignoring other factors) would have a vacuous $O(1)$ suboptimality bound for these instances, whether or not transient data is provided. On the other hand, our lower bound shows that non-vacuous suboptimality is impossible when there is insufficient transient data, but once there is enough transient data, then our upper bound can apply and yield a vanishing suboptimality (as $T$ is fixed and $m$ increases). In summary, no algorithm with a uniform-mixing-based convergence guarantee would yield nonvacuous performance bounds for these instances, while our algorithm and lower bound together reveal that vanishing error is possible but only with sufficient transient data."}, {"review_id": "ImxtBFV16m", "reviewer": "Reviewer_Agk8", "summary": "This paper studies span-based results for offline reinforcement learning in average-reward MDPs. Unlike prior offline results that focus on unichain MDPs, the authors leverage the span-based approach (Matthew et al. (2024)) to derive results for the more general class of weakly communicating MDPs. They introduce a new quantity, $T_{\\text{hit}}(P,\\pi^\\*)$, and show that pessimistic value iteration with a span-based bonus function succeeds if at least $O(T_{\\text{hit}}(P,\\pi^\\*)^2)$ samples are collected for each state. Furthermore, they establish an $O(T_{\\text{hit}}(P,\\pi^\\*))$ lower bound on the required number of samples per state. The theoretical results are supported by rigorous proofs.", "questions": "1. Is this quantile clipping technique useful in online RL, especially in span-based average-reward online RL?\n\n2. The lower bound provided is only linear because it is based on the argument that certain transitions remain unobserved unless at least $O(T_{hit}(P,\\pi^\\*))$ samples are collected for each state. At a high level, I think transitions cannot be accurately identified with fewer than $O(T_{hit}(P,\\pi^\\*)^2)$ samples, which may be a potential avenue to further strengthen and improve the current lower bound result. Is it possible to improve your lower bound result in this way?", "limitations": "yes.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "Strengths:\n\n1. The paper is well-written and easy to follow. The intuition of the newly introduced term $T_{hit}(P,\\pi^*)$ is clear, and the proof sketch can help the reader to quickly grasp the high-level idea of the proof.\n\n2. The negative result for offline RL is both interesting and important. It highlights that offline RL requires sufficient samples for every state, even for states that are never visited by the optimal policy. This is a valuable insight, as many existing offline RL works rely only on the single-policy coverage assumption.\n\n3. This paper is the first to consider the application of the pessimistic value iteration algorithm in average-reward MDPs. The proposed quantile clipping technique is both novel and interesting. The theoretical analysis is rigorous and may also be of independent interest.\n\nWeaknesses:\n\n1. The $\\Omega(T_{hit}(P,\\pi^\\*))$ lower bound result does not match the $O(T_{hit}(P,\\pi^\\*)^2)$ sample complexity result. \n\n2. There is no experiment to primarily examine whether $O(T_{hit}(P,\\pi^\\*)^2)$ samples are needed or $O(T_{hit}(P,\\pi^\\*))$ is enough. Some preliminary experiments that could provide theoretical insight would be great.", "was_revised": true, "final_justification": "I appreciate the author's rebuttal. I will keep my score.", "rebuttal": "Thank you for your positive comments. We would like to respond to some of your listed weaknesses and questions.\n1. Weaknesses/question 2: Closing the gap between the upper and lower bounds (for the amount of data required for transient states) is the main quantitative/information-theoretical question left unresolved by our work and is an interesting question for future research. Our conjecture is that the lower bound is basically tight, and that potentially the same algorithm with a sharper analysis could be used to close the gap. \n2. Question 1: We believe that there is a very high possibility that the quantile clipping technique could be applied in other settings to obtain sharper (span-based) penalty/bonus terms. The most direct application in online RL would likely be to the discounted setting (considered in e.g. arXiv:2010.00587), but as you suggest, it seems likely that improvements for discounted online RL could then be useful for the average-reward setting (possibly through a direct reduction between the settings)."}]

Author rebuttal:

Meta-review: This paper studies the sample complexity of offline RL in the average-reward setting. A notable contribution of this work is a novel lower bound demonstrating the necessity of a transient state coverage complexity measure that is unnecessary in other settings (e.g., finite horizon). While the lower bound does not match the upper bound exactly, the reviewers found the exiting result strong enough for publication.
Decision: Accept (poster)