Sample-efficient Learning of Infinite-horizon Average-reward MDPs with General Function Approximation
Authors: Jianliang He
Han Zhong
Zhuoran Yang
Venue: ICLR 2024 poster (2024)
Keywords: Reinforcement learning theory
General function approximation
Infinite-horizon Average-reward MDPs
Sample efficiency
Primary area: reinforcement learning

Abstract: We study infinite-horizon average-reward Markov decision processes (AMDPs) in the context of general function approximation. Specifically, we propose a novel algorithmic framework named Local-fitted Optimization with OPtimism (LOOP), which incorporates both model-based and value-based incarnations. In particular, LOOP features a novel construction of confidence sets and a low-switching policy updating scheme, which are tailored to the average-reward and function approximation setting. Moreover, for AMDPs, we propose a novel complexity measure --- average-reward generalized eluder coefficient (AGEC) --- which captures the challenge of exploration in AMDPs with general function approximation. Such a complexity measure encompasses almost all previously known tractable AMDP models, such as linear AMDPs and linear mixture AMDPs, and also includes newly identified cases such as kernel AMDPs and AMDPs with Bellman eluder dimensions. Using AGEC, we prove that LOOP achieves a sublinear  $\tilde{\mathcal{O}}(\mathrm{poly}(d, \mathrm{sp}(V^*)) \sqrt{T\beta} )$ regret, where $d$ and $\beta$ correspond to  AGEC and log-covering number of the hypothesis class respectively,  $\mathrm{sp}(V^*)$ is the span of the optimal state bias function, $T$ denotes the number of steps, and $\tilde{\mathcal{O}} (\cdot) $ omits logarithmic factors. When specialized to concrete AMDP models, our regret bounds are comparable to those established by the existing algorithms designed specifically for these special cases.  To the best of our knowledge, this paper presents the first comprehensive theoretical framework capable of handling nearly all AMDPs.

Published as a conference paper at ICLR 2024
SAMPLE-EFFICIENT LEARNING OF INFINITE-HORIZON AVERAGE-REWARD MDPS WITH GENERAL FUNCTION APPROXIMATION
Jianliang He
Han Zhong
Department of Statistics and Data Science Fudan University hej18 fudan. edu. en
Center for Data Science
Peking University
hanzhong@stu. pku. edu.
Zhuoran Yang
Department of Statistics and Data Science
Yale University zhuoran. yang@yale......e. edu
ABSTRACT
We study infinite-horizon average-reward Markov decision processes (AMDPs) in the context of general function approximation. Specifically, we propose novel algorithmic framework named Local-fitted Optimization with OPtimism (LoOP), which incorporates both model-based and value-based incarnations. In particu- lar, LooP features a novel construction of confidence sets and a low-switching policy updating scheme, which tailored to the average-reward and function approximation setting. Moreover, for AMDPs, we propose a novel complex- ity measure average-reward generalized eluder coefficient (AGEC) which captures the challenge of exploration in AMDPs with general function approxi- mation. Such a complexity measure encompasses almost all previously known tractable AMDP models, such as linear AMDPs and linear mixture AMDPs, and also includes newly identified cases such as kernel AMDPs and AMDPs with Bell- man eluder dimensions. Using AGEC, we prove that LooP achieves sublinear (poly(d, sp(ssssVVv sp(V")) regret, where d and 3 correspond to AGEC and log- covering number the hypothesis class respectively, sp(V*) is the span the optimal state bias function, T denotes the number of steps, and Ó(-) omits loga- rithmic factors. When specialized to concrete AMDP models, our regret bounds are comparable to those established by the existing algorithms designed specifi- cally for these special cases. To the best of our knowledge, this paper presents the first comprehensive theoretical framework capable of handling nearly all AMDPs.
INTRODUCTION
Reinforcement learning (RL) (Sutton & Barto, 2018) is a powerful tool for addressing intricate quential decision-making problems. In this context, Markov decision processes (MDPs) (Puterman, 2014; Sutton & Barto, 2018) frequently serve fundamental model for modeling such decision- making scenarios. Motivated by different feedback structures in real applications, MDPs consist of three subclasses average-reward MDPs. Each of these MDP variants is of paramount significance and operates in parallel fashion, with none being amenable to complete reduction into another. Of these three MDP subclasses, mhite-horizon MDPs have received significant research efforts in understanding their exploration challenge, especially the presence large state spaces which necessitates function approximation tools. Existing works on finite-horizon MDPs have proposed numerous structural conditions on the MDP model that empower sample-efficient learning. These structural conditions include but not limited to linear function approximation (Jin et al., 2020), Bellman rank (Jiang et al., 2017), eluder dimension (Wang et al., 2020), Bellman cluder dimension (Jin et al., 2021), bilinear class (Du et al., 2021), decision estimation coefficient (Foster al., 2021), and generalized
mnite-horizon MDPs, -efiiitehhorioon discounted MDPs, and infinite-horizon

---

Published as a conference paper at ICLR 2024
eluder coefficient (Zhong et al., 2022). Moreover, these works have designed various model-based and value-based algorithms to address kmite-horizon MDPs governed by these structural conditions.
In contrast to the rich literature devoted to finite-horizon MDPs, the study of sample-efficient explo- ration in infinite-horizon MDPs has hitherto been relatively limited. Importantly, it remains clusive how to design in principled fashion sample-efficient RL algorithm in the online setting with general function approximation. To this end, we focus on infinite-horizon average-reward MDPs (AMDPs), which offer a suitable framework for addressing real-world decision-making scenarios that prioritize long-term returns, such as product delivery (Proper & Tadepalli, 2006). Our work endeavors to provide a unified theoretical foundation for understanding infinite-horizon average- reward MDPs from the perspective of general function approximation, akin to the comprehensive investigations conducted the domain of hnrte-horizon MDPs. To pursue this overarching objec- tive, we have delineated two subsidiary goals that form the crux of our research endeavor.
Development of a Novel Structural Condition/Complexxty Measure. Existing works are re- stricted to tabular AMDPs (Bartlett & Tewari, 2012; Jaksch ct al.. 2010) and AMDPs with linear function approximation (Wu et al., 2022; Wei et al., 2021), with Chen et al. (2022a) as the only exception (to our best knowledge). While Chen al. (2022b) does extend the eluder dimension for finite-horizon MDPs (Ayoub et al., 2020) to the infinite-horizon average-reward context, their complexity measure seems to be only slightly more general than the linear mixture AMDPs (Wu et al., 2022) and falls short in capturing other fundamental models such as linear AMDPs (Wei al., 2021). Hence, our first subgoal is proposing a new structural condition. This condition is envisioned to be sufficiently versatile to encompass all known tractable AMDPs, while also potentially introducing innovative and tractable models into the framework.
Algorithmic Framework for Addressing Identified Structural Condition. The second subgoal is anchored in the development of sample-efficient algorithms for AMDPs characterized by the structural condition proposed in our work. Our aspiration is devise an algorithmic framework that can be flexibly implemented in both model-based and value- based paradigms, depending on the nature of the problem at hand. This adaptability guarantees that our algorithms possess the ability to effectively address a wide range of AMDPs.
Our work attains these two pivotal subgoals through the introduction of (i) novel complexity measure - Average-reward Generalized Eluder Coefficient (AGEC), and (ii) a corresponding al- gorithmic framework dubbed as Local-fitted Optimization with OPtimism (LOOP). Our primary contributions and novelties are summarized below:
AGEC Complexity Measure. Our complexity measure AGEC extends the generalized eluder coefficient (GEC) in Zhong et al. (2022) to the infinite-horizon average-reward setting. How- ever, it incorporates significant modifications. AGEC not only establishes a connection between the Bellman error and the training error, akin GEC but also imposes certain constraints on transferability (see Definition 3 for details). This modification proves instrumental in attaining sample efficiency in the realm of AMDPs (see Section 5 for detailed discussion). We demonstrate that AGEC not only encompasses all previously recognized tractable AMDPs, including tabular AMDPs (Bartlett & Tewari, 2012; Jaksch et al., 2010), linear AMDPs (Wei al., 2021). linear mixture MDPs (Wu et al., 2022), AMDPs with low eluder dimension (Chen et al., 2022a), but also captures some new identified models like linear Q' /V AMDPs (see Definition 14), kernel AMDPs (see Proposition 7), and AMDPs with low Bellman eluder dimension (see Definition 8).
LOOP Algorithmic Framework. Our algorithm LOOP is based on the optimism principle and features novel construction of confidence sets along with a low-switching updating scheme. Remarkably, LOOP offers the flexibility to be implemented either in the model-based or value- based paradigm, depending on the problem type.
Unified Theoretical Results. From the theoretical side, we prove that LooP enjoys the regret of
(poly (p. ())) where d and 3 correspond to the AGEC and the log-covering number of the hypothesis class respectively, sp(V*) denotes the span of the optimal state bias function, T is the number of steps, and Ô hides logarithmic factors. This result shows that LooP capable of solving all AMDPs with low AGEC.
In summary, we provide a unified thcoretical understanding of infinite- -orizzon AMDPs with general function approximation. Further elaboration on our contributions and technical novelties are
2

---

Published as a conference paper at ICLR 2024
Linear Mixture
Algorithm
Assumption
Type
Tabular
Linear
Fluder
Bellman optimality
Model-busee buseel Value-based
Loor (Ours)
(finite span)
(Chen al., 2022a)
SIM-10-REad
Communicating AMDP
(finite diameter)
Model-based
d
X
V
X
K
X
UCRL2-VIR (Wu 2022)
Communicating AMDP (finite diameter)
Model-based
/
X
K
X
K
K
FoPo
Bellman optimality (finite span)
Value-based
x
K
X
X
K
(Wei et al., 2022)
UCRL2
Communicating AMDP
(laksch 2010)
(finite diameter)
Model hased
X x K X
K
Table I: A comparison with the most related algorithms on AMDPs. We remark that our assumption weaker since the communicating MDP satisfies the Bellman optimality and the diameter bound by the span. Besides, average-reward Bellman eluder dimension (ABE), kernel AMDPs, and AGEC are new complexity measures proposed by our work. In particular, AGEC serves as unifying complexity measure capable of encompassing all other established complexity measures.
provided in Appendix A. Due to space limits, we only provide comparison between our results and mostly related works on AMDPs in Table 1. More related works are deferred to Appendix A.
2 PRELIMINARIES
An infinite-houe -hriiin average-reward Markov Dependent Process (AMDPs) is characterized by M (S, A, r, P)),, where S Borel state space with possibly infinite number of elements, is finite set of actions, r S x A [-1,1] is an unknown reward function' and P(-|s, a.) is the unknown transition kernel. The learning protocol for infinite-horizon average-reward RL as follows: the agent interacts with M over fixed number of 7' steps, starting from pre-determined initial state 81 S. At each step & [T], the agent observe state 8N and takes an action de E A, receives
reward r(s,, az) and transits to the next state 8141 drawn from P(-|s), (t).
Denote ((A) the probability simplex over the action space A. Specifically, the stationary policy is a mapping S + ((A) with ralss) specifying the probability of taking action at state Given a stationary policy æ. the long-term average reward starting is defined as
(*)(s = lim inf
Σ r(se, at)ls =
Vs E
where the expectation is taken with respect to the policy, i.e., at (-((s) and the transition, i.e., 8141 P([|st, at). In infinite-horizon average-reward RL, existing works mostly rely on additional assumptions to achieve sample efficiency. The necessity arises from the absence of natural coun- terpart to the celebrated Bellman optimality equation in the average-rewan RL that is self-evident and crucial within episodic and discounted settings (Puterman, 2014). To this end, we consider a broad subclass where modified Bellman optimality equation holds (Hernández-Lemme 2012).
Assumption (Bellman optimality equation). There exists bounded measurable function Q* : A RR, V* S R and unique constant J E [-1, 1] such that for all (s,a) a) E S A. it holds J" (s. r(s. a) Ex [V*(())),
V*(s) max Q" (s, aeA
(2.1)
The Bellman optimality equation, adapted for average-reward RL, posits that for any initial states 81 E S, the optimal reward is independent such that J*1ss) J" under a deterministic optimal policy following (.1s) = argmax,c. (" The justification is presented in Wei et al. (2021).
Note that functions (*) and (* a) reveal the relative advantage of starting from state s and state-action pair (s, a) under the optimal policy, and are respectively called the optimal state and
"Throughout this paper, consider the deterministic reward for notational simplicity and all results readily generalized the stochastic setting. Also, assume reward lies in [-1, without loss of generality.

---

Published as a conference paper at ICLR 2024
.' state-action bias function (Wei al., 2021). Denote sp(V) = s [V(s) [ as the span of any bounded measurable function. Note that for any solution pair (V*, Q*) satisfying the Bellman optimality equation in (2.1), the shifted pair (V- - c, Q - c) for any constant с is still solution. Thus, without loss of generality, we can focus the unique centralized solution such that ||V |0 < {sp( Following the tradition in the average-reward RL (Wei et al., 2020; 2021; Wang et al., 2022; Zhang & Xie, 2023), the span sp(V*) is assumed to be known.
As aforementioned in the paper, distinct assumptions have been employed in average-rewait RL re- search to ensure the explorability of the problem, which includes ergodic AMDPs (Wei et al., 2020; Hao et al., 2021; Zhang & Xie, 2023), communicating AMDPs (Chen et al., 2022a; Wang et al,, 2022: Wu et al., 2022) and the Bellman optimality equation (Wei et al., 2021) 1). Among these widely adopted assumptions, we remark that the Bellman optimality equation is the least stringent one. Note that the ergodic MDP suggests the existence of bias functions for each x E II, while the latter two only require the existence of bias functions for the optimal policy. As for weak communicating assumption, a weaker form of communicating MDP (Wang et al., 2022), it directly implies the exis- tence of the Bellman optimality equation and thus is stronger (Hernández-Lerne 2012). Given the Bellman optimality assumption in (2.1), we introduce the average-reward Bellman operator below:
(T,F)(s, := r(s, ~P(lsa))
max F(s', J, V(s,a) E S d'EA
(2.2)
for any bounded function F: 88x A R and constant J [-1,,, 1]. Then, the Bellman optimality equation in (2.1) can be written as T,. Q = Q-, Moreover, we define the Bellman error:
E(P, J),, = (TF))(,))
V(s, a) ESXAA.
(2.3)
Learning Objective Under the framework of online learning for AMDPs, the agent aims to learn the optimal policy by interacting with the environment over potentially infinite steps. The regret measures the cumulative difference between the optimal average-reward and the reward achieved after interacting for T steps, formally defined as Reg(T)- ΣT= (J ((S),a)))
GENERAL FUNCTION APPROXIMATION
To capture both model-free and model-based problems with function approximation, we consider general hypotheses class H which contains a class of functions. We consider two kinds of hypothesis classes, targeting at balue-based problems and model-basee problems respectively.
Definition (Value-based hypothesis). We say H is value-based hypotheses class if all hypothesis f E H is defined over state-action bias function Q and average-reward such that f (Q,, JJ) e H. Let V-(-) = m (5 a) and π. (-) = argmax,c. a) be the greedy bias function and policy induced from hypothesis f E H. Denote f be the optimal hypothesis under true model M.
Definition (Model-based hypothesis). We say H is a model-based hypotheses class if all hypothe- sis f E H is defined over the transition kernel IP and reward function r such that f = (Fy, E H. Let Qy. Vy. Jy, and 5 respectively be the optimal bias functions, cerrage-rwward and policy in- duced from hypothesis f E H. which satisfies the Bellman optimality equation such that
Q, a) + J = (ry + PP
Py)V(ss,a) := Ey- (Vss))))
for all 8 E S and a E A. Denote /" as the hypothesis concerning the true model M.
The definition of hypotheses class over the value-based (see Definition 1) and the model- (see Definition 2) problems in AMDP is different from the episodic setting (Du et al., 2021; Zhong et al., 2022). The most significant difference that the Bellman equation has a different form. As result, in the value-based scenario, instead of using single state-action value function Q, in episodic setting, the paired hypothesis (Q,, JJy is introduced to fully capture the average-reward structure. Besides, we retain the definition of hypothesis over model-based problems, augmenting it with an additional average-reward term J, induced from (Py.ry). Since we do not impose any spe- eific structural form to the hypothesis class, we stay in the realm of general function approximation.
As function approximation is challenging without further assumptions (Krishnamurthy et al., 2016), introduce the realizability assumption, which is widely adopted in literatures (Jin et al., 2021).
4

---

Published as a conference paper at ICLR 2024
Assumption (Realizablity). We assume that f" H.
Moreover, we establish the fundamental distribution families over the state-action pair upon which the metric is built. Considering the learning goal defined over the empirical regret, throughout the paper we focus on the point-wise distribution family DA = () a) E S A), which includes collections of Dirac probability measure over S A. Discussions are deferred to Appendix A.
3.1 EVERAGE-REWARE GENERALIZED ELUDER COEFFICIENTS
In this subsection, we are going to introduce a novel metric - average-reward generalized eluder coefficients (AGEC), to capture the complexity of hypothesis class H. for AMDP. Extended from the generalized Eluder coefficients (GEC; Zhong et al., 2022) for finite-horizon MDPs, AGEC is variant fit the horiion learning with average reward, and imposes an additional structural constraint transfcrability motivated by Eluder condition (EC; Xiong et al., 2023) and proved mild in Section 3.2, to ensure the tractability of the problems.
Definition (AGEC). Given hypothesis class H. discrepancy function set { and constant e > the average-reward generalized eluder coefficients AGEC(H, {1y}.e) .c) defined as the smallest coefficients Kig and da such that following two conditions hold with absolute constants C1. C2 > 0:
(Bellman dominance) There exists constant dG >> such that
T
T
t-1
{(f)(s;;
do
f. C011
+ C1 -p((V)) min T} + Te.
Burn-in cost
Bellman error
In-sample training error
iii (ransferabillity) There exists constant Kig 0 such that for hypotheses fa...., H, if
Be. Br (Fe, Sr. 401113 33 holds for all E [7]. then we have
[R Ir (fe, for 4ill < NG 33 3og + C2 sp(V")² min(KG, T) 2T
Burn-in cost
Out-sample training error
In the definition above, is a subset of trajectory with varying meaning concerning the specific choice of discrepancy function. and the expectation is taken over it; C1. C2 are absolute constants related span sp(V*). To simplify the notation, we denote {s)) a) := (() a) for all (s. E S x A. Besides, the Burn-in cost is taken at the worst case and it varies across different settings but usually non-dominating. The intuition behind the metric that, on average, if hypothe- ses have small in-sample training error the well-explored dataset, then the prediction error on different trajectory expected to maintain a consistently low level (Zhong et al., 2022). In specific, the dominance coefficient du encapsulates the challenge inherent in assessing the performance of prediction, specifically the Bellman error, given the consistently controlled in in-sae training error within the designated function class H. Moreover, due the unique challenge of infinite-horizz average-reward setting, we introduce the transferability coefficient KG to quantify the transferability from the in-sample training error the out-of-sample ones. Despite this additional structural con- dition, we can verify that nearly all tractable AMDPs admit low AGEC value (see Section 3.2). Moreover, in Section 5, we will demonstrate the importance of such additional structural conditions for achieving sample efficiency in AMDPs from the theoretical perspective.
Moreover, facilitate further theoretical analysis, we make further assumptions on the discrepancy function and hypothesis class as Chen et al. (2022b); Zhong et al. (2022). Assumption (Boundedness). Given any f H. it holds that |lyllo S C.. sp(V*) with Ce
The boundedness assumption is reasonable and uniformly satisfied, as in most cases, it takes the Bellman discrepancy, defined as: for all G, = {8c, de, Tr, 8141 } E S x A
S, we have
(f ()) = (s, a.) r(se. at) - V/ (s++1) + Jg.
(3.1)
other natural derivatives, so that the discrepancy is generally upper bounded by O (sp((V)))
5

---

Published as a conference paper at ICLR 2024
Assumption 4 (Generalized completeness). Let & be auxiliary function class and there exists functional operator P: H. + g. we say that H. satisfies generalized completeness in g concerning discrepancy function ly. if for any (f.9) H x (H U G), holds that
gf -
E (f.)..
(3.2)
where the expectation taken over trajectory Ç. Besides, the operator satisfies that P( f"
The completeness assumption is an extension of the Bellman completeness for value-based hypoth- esis (Jin et al., 2021), incorporating the notion of the decomposition loss function (DLF) property proposed in Chen et al. (2022b). Our assumption diverges from the one posited in Zhong et al. (2022), where an auxiliary function class P(H) S 9 is introduced to enrich choices, accompanied with modifications tailored to accommodate the nuances of the weeage-rrward setting.
Example (Bellman completeness C Generalized completeness). Let the discrepancy function be the Bellman discrepancy in (3.1) with & = ={s,, at, Tt, St+1), and takes the sypothesis-schemee Bellman operator, defined as T() = (Ta, (Qy), Jy} for all f H. modified from (2.2). Then,
(f.g. - Ly (f. T(), (.) (s ae) - TJ Qy ar)
= (st a²) - r(s,, a.) + E,, [V (s++1)] + , Es, (r. where the expectation is taken over the transition state 1 from IP([|se,a))
The preceding example illustrates that the Bellman discrepancy, a frequently employed discrepancy function across problems, satisfies both assumptions. More examples and choices of the discrepancy function for MLE-based algorithms are respectively provided in Appendix B and C.
3.2 RELATION WITH TRACTABLE COMPLEXITY METRIC
To bridge the gap between concrete function approximation instances and the relatively abstract measure AGEC, this section introduces two intermediate metries: the Eluder dimension (Russo & Van Roy. 2013) and the Average-reward Bellman Eluder (ABE) dimension. In particular, Chen et al. (2022a) employs the Eluder dimension to gauge the complexity of model-based hypothesis classes for infinite-horizon learning. To provide an intuitive complexity of value- additionally propose the ABE dimension, which is generalization of the standard BE dimension (Jin et al., 2021). These two metrics provide valuable insights into the nature of AGEC.
hypothesis classes,
Eluder Dimension We start with point-wise e-independence notation (Russo & Van Roy, 2013). Definition 4 (Point-wise e-independence). Let be a function class defined on X' and consider sequence {2, .2, E X. We say is e-independent of {I1, (Eli....,,,, In with respect to H if there exists f. f E H such that (f(z)) (z)x S e, but [f(=) f'(2)
Based on e-independence, the Eluder dimension can be efficiently defined as below. Definition 5 (Eluder dimension). Let H be a function class defined on X. The Eluder dimension dimp(H, +) is the length of the longest sequence {.11,..., C X' such that there exists e' 2 6 where 2; is e' é'-independent of {. 3 for all i [n].
The following lemma shows that a model- based hypothesis class with a low Eluder dimension has low AGEC. Motivated by Ayoub et al. (2020); Chen et al. (2022a), we consider the Eluder dimension over function class derived from the model-based hypotheses class H. defined as
Xx = (x a) (ry + VP) (8, a) S E H}.
Note that Chen et al. (2022a) considered function class Xx,Y == (s, / E ((H))) V V). where IHH) denotes the hypotheses class over the transition kernel and V denotes the hypotheses class over the optimal bias function. We remark that definitions over function class based on (F', V) with (f, V) E H x V and rF) with E H. is almost equivalent and in this paper we focus on Xx under the latter framework, aligning with the model-basee hypothesis (see Definition 2).
Lemma 1 (Low Eluder dim C Low AGEC), Consider the discrepancy function
(f 9. (i) = (rg + VyV a.) - r(st, at) + +V ($(+1),
(3.3)
with P(f) = f", and the expectation is taken over $:+1 from PP-|s az). Let dg = dimp, (Xxr e) be the e-Eluder dimension defined over Xzz, then have de 2dg log T and KG S dr.

---

Published as a conference paper at ICLR 2024
Average-Reward Bellman Eluder (ABE) Dimension Before delving into details of the average- reward BE (ABE) dimension, we start with two useful notations, distributional e-independence and distributional Eluder (DE) dimension proposed by Jin et al. (2021), which is generalization of point-wise e-independence and Fluder dimension defined above (see Definitions 4 and 5).
Definition 6 (Distributional e-independence). Let H. be function class defined on X' and sequence {v, P1...... j be the probability measures over X. We say v is e-independent of {u1..... Pa with respect to H if there exists f E H such that v 2i (IE [f])2 < but [[], 2 c.
Definition 7 (Distributional Eluder dimension). Let H. be a function class defined on X' and I be family of probability measures over X. The distributional Eluder dimension dimpE I, is the length of the longest sequence (pI...., Pr. C I such that there exists é' 2 < where Ai is é' <'iindependent of the remaining distribution sequence f Pi-1) for all i [m].
Now we are ready to introduce the average-rewarr Bellman Eluder (ABE) dimension. It is defined as the distributional Eluder (DE) dimension of average-reward Bellman error (2.3) over H. Definition 8 (ABE dimension). Denote EH {f) a) :f HH be the collection of average- reward Bellman errors defined over S A. For any constant c > 0, the c-ABE dimension of given hypotheses class H. is defined as dim (H, c) == dimDE (Ex, C2.
The lemma below posits that the palue-based hypothesis problem with low ABE dimension shall have a low AGEC in terms of the Bellman discrepancy.
Lemma 2 (Low ABE dim C Low AGEC), Consider the Bellman discrepancy function as defined in (3.1). and the expectation is taken over the transition state s1+1 from P(-)s,, a.). Let dABE dimABE(H,, c), then we have du < 2dABE log T and KG S dABE-
The Eluder dimension and ABE dimension can capture numerous concrete problems, respectively under model-based and value-based scenarios. Specifically, the Eluder dimension incorporates rich model-based problems like linear mixture AMDPs (Wu et al., 2022), and the ABE dimension can characterize tabular AMDPs (Jaksch et al., 2010), linear AMDPs (Wei et al., 2021), AMDPs with Bellman Completeness, generalized linear AMDPs, and kemell AMDPs, where the latter three prob- lems are newly proposed for AMDPs. Details about the concrete examples are deferred to Appendix C. Combining these facts and Lemmas and 2, we can conclude that AGEC serves as unified complexity measure, as it encompasses all of these tractable AMDP models illustrated above.
4 LOCAL-FITTED OPTIMIZATION WITH OPTIMISM
To solve AMDPs with low AGEC value (see Definition 3), we propose the algorithm Local-fitted Optimization with OPtimism (LOOP), whose pseudocode is given in Algorithm 1. At a high level, LOOP modified version of the classical fitted Q-iteration (Szepesvári, 2010) with optimistic planning and lazy policy updates. That is, the policies are only updated when certain criterion is met (Line 2). When this is the case, LOOP performs three main steps:
Optimistic planning (Line 4.1): Compute the most optimistic fe E H within B, that maximizes the corresponding average-reward Jr by solving constrained optimization problem.
Construct confidence set (Line 4.2): Construct the confidence set B, for optimization using Dt-1, where all f. E H satisfying LD.,, (fe, fi) inf ges LD.,, (fr. g) < B is included. Here, / > 0 defines the radius, corresponding to the log covering number the hypothesis class H.
Execute Policy and Update T, (Line 8- 10): Choose the greedy policy n. F. as the exploration policy. Execute policy, collect data, and update trigger Y, LD, (fe, ft) inf LD, (fe, g).
Note that both the confidence set B, and the update condition Y, are constructed upon the (cumula- tive) squared discrepancy, which is crucial to the algorithmic design. It takes the form
(f.(f inf (p.(fg) where gEG
= Σ 1 C01.. (FeCDED
(4.1)
where fa and Ç = (s,, aq S141) are drawn from D,, and (f.(f. is the discrepancy function, which varies across different RL problems. The sum of squared discrepancy serves as an empirical estimation of the in-sample training error (see Definition 3). Besides, we highlight two key designs:
7

---

Published as a conference paper at ICLR 2024
Algorithm Local-fitted Optimization with Optimism - LOOP(H,
Parameter: Initial 81, span sp(V") optimistic parameter / log (TN Hus (1/T)/6) sp(VV))
Initialize: Draw a1 Unif(AA and set TO t O, To 0, Bo - 0. Do + 0.
I: for = 1,..., do
2: if or T 2 4,3 then
3: Set l.
4: Solve optimization problem Jt = arginax Ji where
B, { | LD, (1,1) - inl Lr. (1:9) 5 gEg
(4.2)
5:
Compute Qi = Q. 1/2 = V4, and Jj J..
6:
else
7:
Retain (ft, V1, Q1, Ti) -f ff-11. V Qi-1, 8: Take a, argmax Qr(
9: Observe 7; = r(s,, at) and transition state 81+1-
Update D. D 1 (8t, dt rts 8141i and Tr CD. inf CD. (ft.g).
Consistent control over discrepancy: The construction of confidence set B, ensures that the cumulative squared discrepancy is controlled at level each step. To see this, suppose = t, i.e., policy switches at the t-th step, then (4.2) ensures that LD.-, fe) inf yng L (fu.g) S 3. Otherwise, we do not switch policy at step f, then we must have Y,-1 = LD.,, (fr, ft) inf fDD (fr,9) 4,3, as hypothesis fa ft-1 remains unchanged.
Lazy policy update: The regret decomposition in (5.1) elucidates that each policy switch incurs an additional cost ( - (1 )l regret at each step (see (5.3)). This underscores the necessity of implementing lazy updates achieve sublinear regret. Within the LooP frame- work, policy updates occur adaptively, triggered only when a substantial increase in cumulative discrepancy surpassing 3,3 has occurred since the last update. Intuitively, a policy switch occurs when there is a notable infusion new information from newly collected data. Importantly, such it provides the theoretical foundation for the implementation of lazy updates,
gap is pivotal leveraging the problem's transferability structure (see (ii), Definition 3). Here, LOOP employs threshold of 43, considering inherent uncertainty and estimation errors between the minimizer g and (ff), ensuring that the out-of-sample error will exceed / under the updating rule.
Similar to previous works in general function approximation (Jin et al., 2021; Du et al., 2021), our algorithm lacks computationally efficient solution for constrained optimization problems. Instead, our focus is on the sample efficiency, as guaranteed by the theorem below.
Theorem 3 (Regret). Under Assumptions 1-4, there exists constant such that for any 5 E (0, and horizon T, with probability at least 56, the regret of LOOP satisfies that
Reg(T) < o (sp(')) dvTB).
where 3 e log (1/T)))))
sp( sp") and d = max VTl kG). Here, (dg, KG) AGEC(H.
{1y), 1/) are AGEC defined in Definition 3, G is the auxiliary function class defined in Definition and (+ denotes the covering number as defined in Definition 17.
Theorem 3 asserts that both value-based and model- problems with low AGEC tractable. Our algorithm LOOP achieves ((VT) regret and the multiplicative factor depends on span sp(V*), problem complexity max / Vdg, KG } and the log covering number. The proof sketch is provided in Section and the detailed proof deferred to Appendix D.
PROOF OVERVIEW OF REGRET ANALYSIS
In this section, present the proof sketch of Theorem 3. In Section 4, we elucidated the construc- tion of the confidence set and the circumstances in which updates are performed. Here, we delve into the theoretical analysis to substantiate the necessity of such designs.
8

---

Published as a conference paper at ICLR 2024
Optimism and Regret Decomposition In LOOP, we apply optimization based method to sure the optimism J 2 J at each step t E [T]. Based on the optimistic algorithm, we propose a new regret decomposition method motivated by the standard performance difference lemma (PDL) in episodic setting (Jiang et al., 2017), following the form as below:
(eg(T) S Σ (L))
Pe (V Vi(a).
(5.1)
Bellman error
Realization error
Step 1: Bound over Bellman Error The control over the Bellman error achieved through the design of a confidence set and update condition that combinely controls the empirical squared discrepancy. Note that the construction of the confidence set filters ft with a limited sum of empirical squared discrepancy. Note that Lp._, (ft, fe) inf LD__, (fr. 9) can be regarded as an empirical overestimation of the squared discrepancy, controlled at ((3)) regardless of updating. Then,
In-sample training error 2
||E Pr, (Si, Jr, G)Il S
E
(5.2)
with high probability, and ,9 is pre-determined optimistic parameter depends on horizon T and the log p-covering number. Recall that the dominance coefficient dG regulates that Bellman error X
dG Ein E (Be 1/2
thus we have Bellman error < dG,T).
Step 2:
The realization error small the switching cost is low as the concentration arguments indicated that with high probability it holds
Bound over Realization error
Realization error S sp(V") + O(sp(V") (Too((1/))
(5.3)
Switching cost
Azuma- Nouma-Hoeffding term
where (t)) denote Switching cost defined as N(T) = #(t E (T) Te * Tt-1). Motivated by the recent work of Xiong et al. (2023), the main idea of low-switching control is summarized below. The key step is that the minimizer is good approximator of ((fe) such that
(D. P(f.) inf (D.()..)) S 3, E
(5.4)
gEg
with high probability based on the minimization and the definition of optimistic parameter 3. In the following analysis, we assume that (5.4) holds. Suppose that an update occurs at step + 1, then it implies that LD. (ft, - inf LD, (ft. g) > 43 and the latest update at step t ensures that (Dre fr.) inf LD.,-1 (Fre 9) S B. Combine (5.4) with the arguments above, we have
(1). LD, fi) (F., 38, (ii). LD (Fr LD.,- (Fr, P(F..) S B.
(5.5)
Based on the concentration argument and (i), (ii) in (5.5), the out-sample training error between two updates is lower bounded by Eiz [| 14, (fr, fu. Gi]l > B. Let ......,b((T)). be the sequence of updated steps, take summation over the T steps and then we have
N(T) but1-1
N(T) <
Ba for G0l1B
|B 1. (fe, fc, GO) O 3 log T), (5.6)
where the first inequality follows arguments above and the second is based on the definition of transferability (see Definition 3) given [ (., fe, c.]1 0()) for all t [T]. Thus, have (TT) O(KG log 7') and the Realization error is bounded by O(NG sp(V*) log Please refer to Lemma 11 in Appendix D.4 for a formal statement and detailed techniques.
CONCLUSION
This work studies the infinite-horizon average-reward MDPs under general function approximation. To address the unique challenges AMDPs, we introduce a new complexity metric average- reward generalized eluder coefficient (AGEC) and unified algorithm named Local-fitted Opti- mization with OPtimism (LooP). We posit that our work paves the way for future work, including developing more general frameworks for AMDPs and new algorithms with sharper regret bounds.

---

Published as a conference paper at ICLR 2024
REFERENCES
Yasin Yadkor,, Dávid Pál, and Csaba Szepesvári. Improved algorithms for linear stochastic bandits. Advances in neural information processing systems, 24, 2011.
Yasin Abbasi-Yadkori, Peter Bartlett, Kush Bhatia, Nevena Lazic, Csaba Szepesvari, and Gellért Weisz. Politex: Regret bounds for policy iteration using expert prediction. In International Conference on Machine Learning, pp. 3692-3702. PMLR, 2019.
Alckh Agarwal, Daniel Hsu, Satyen Kale, John Langford, Lihong Li, and Robert Schapire. Taming the monster: A fast and simple algorithm for contextual bandits. International Conference on Machine Learning, pp. 1638-1646. PMLR, 2014.
Alekh Agarwal, Yujia Jin, and Tong Zhang. Vo q I: Towards optimal regret in model-free rl with nonlinear function approximation. arXiv preprint arXiv:2212.06669, 2022.
Peter Auer, Thomas Jaksch, and Ronald Ortner. Near-optimal regret bounds for reinforcement learning. Advances neural information processing systems, 21, 2008.
Alex Ayoub, Zeyu Jía, Csaba Szepesvari, Mengdi Wang, and Lin Yang. Model-based reinforcement learning with value-targeted regression. In International Conference on Machine Learning, pp- 463-474. PMLR, 2020.
Yu Bai, Tengyang Xie, Nan Jiang, and Yu-Xiang Wang. Provably efficient q-learning with low switching cost. Advances in Neural Information Processing Systems, 32, 2019.
Peter L Bartlett and Ambuj Tewari. Regal: A regularization based algorithm for reinforcement learning in weakly communicating mdps. arXiv preprint /205. 2661, 2012.
Qi Cai, Zhuoran Yang, Chi Jin, and Zhaoran Wang. Provably efficient exploration in policy opti- mization. In International Conference on Machine Learning, pp. 1283-1294. PMLR, 2020.
Xiaoyu Chen, Jiachen Hu, Chi Jin, Lihong Li, and Liwei Wang. Understanding domain randomiza- tion for sim-to-real transfer. International Conference Learning Representations, 2022a.
Zixiang Chen, Chris Junchi Li, Angela Yuan, Quanquan Gu, and Michael Jordan. general framework for sample-efficien function approximation in reinforcement learning, arXiv preprint 1rXiv:2209.15634 2022b.
Varsha Dani, Thomas Hayes, and Sham M Kakade. Stochastic linear optimization under bandit feedback. 2008
Christoph Dann, Mehryar Mohri, Tong Zhang, and Julian Zimmert. A provably efficient model-free posterior sampling method for episodic reinforcement learning. Advances in Neural Information Processing Systems, 14440-1220 2021.
Omar Darwiche Domingues, Pierre Ménard, Mattco Pirotta, Emilic Kaufmann, and Michal Valko. A kernel-based approach non-stationary reinforcement learning in metric spaces. In International Conference on Artificial Intelligence and Statistics, pp. 1538-35446 PMLR, 2021.
Simon Du, Sham Kakade, Jason Lee, Shachar Lovetr, Gaurav Mahajan, Wen Sun, and Ruosong Wang. Bilinear classes: A structural framework for provable generalization in In International Conference on Machine Learning, pp. 2826-2836. PMLR, 2021.
Dylan J Foster, Sham M Kakade, Jian Qian, and Alexander Rakhlin. The statistical complexity of interactive decision making. arXiv preprint arXiv:2112.13488 2021.
Dylan Foster, Noah Golowich, and Yanjun Han. Tight guarantees for interactive decision making with the -estimatontt coefficient. arXiv preprint arXiv:2301.08215 2023,
Ronan Fruit, Mattco Pirotta, Alessandro Lazaric, and Ronald Ortner. Efficient caass-paa-coosstainne exploration-exploitaiee in reinforcement learning. In International Conference on Machine Learning, pp. 1578-1586 PMLR, 2018.
10

---

Published as a conference paper at ICLR 2024
Botao Hao, Nevena Lazic, Yasin Abbasi- Yadkori, Pooria Joulani, and Csaba Szepesvári. Adaptive approximate policy iteration. In International Conference on Artificial Intelligncce and Statistics, pp. 531-531. PMLR, 2021.
Jiafan He, Heyang Zhao, Dongruo Zhou, and Quanquan Gu. Nearly minimax optimal reinforcement learning for linear markov decision processes. arXiv preprint arXiv:2212.06132 2022.
Onésimo Hermández-Lerma Adaptive Markov control processes, volume 79. Springer Science & Business Media, 2012.
Jiachen Hu, Han Zhong, Chi Jin, and Liwei Wang. Provable sim-to-real transfer in continuous domain with partial observations. arXiv preprint arXiv:2210.15598, 2022.
Jiayi Huang, Han Zhong, Liwei Wang, and Lin F Yang. Tackling heavy-tailed rewards in rein- forcement learning with function approximation: Minimax optimal and instance-dependent regret bounds. arXiv preprint 2xXiv:23000068366 2023.
Thomas Jaksch, Ronald Ortner, and Peter Auer. Near-optimal regret bounds for reinforcement learning. Journal of Machine Learning Research, 11(51):1563-16) 2010.
Nan Jiang, Akshay Krishnamurthy, Alekh Agarwal, John Langford, and Robert E Schapire. Con- textual decision processes with low bellman rank are pac-leamable. In International Conference on Machine Learning, pp. 1704-1713. PMLR, 2017.
Chi Jin, Zhuoran Yang. Zhaoran Wang, and Michael Jordan. Provably efficient reinforcement learning with linear function approximation. In Conference Learning Theory, pp. 2137-2143. PMLR, 2020.
Chi Jin, Qinghua Liu, and Sobhan Miryoosefi. Bellman eluder dimension: New rich classes of rl problems, and sample-efficient algorithms. Advances neural information processing systems, 34:13406-13418, 2021.
Dingwen Kong, Ruslan Salakhutdinov, Ruosong Wang, and Lin F Yang. Online sub-sampling for reinforcement learning with general function approximation. arXiv preprint arXiv:2106.07203, 2021.
Akshay Krishnamurthy, Alekh Agarwal, and John Langford. Pac reinforcement learning with rich observations. Advances in Neural Information Processing Systems, 29, 2016.
Nevena Lazic, Dong Yin, Yasin Abbasi Yadkori, and Csaba Szepesvari. Improved regret bound and experience replay in regularized policy iteration. In International Conference Machine Learning, pp. 6032-6042, PMLR, 2021.
Xiang Li and Qiang Sun. Variance-aware robust reinforcement learning with linear function approx- imation with heavy-tailed rewards. arXiv preprint arXiv:2303.056/ 0500000606, 2023.
Qinghua Liu, Alan Chung, Csaba Szepesvári, and Chi Jin. When is partially observable reinforce- ment learning not scary? In Conference Learning Theory, pp. 5175-5220. PMLR, 2022.
Qinghua Liu, Praneeth Netrapalli, Csaba Szepesvari, and Chi Jin. Optimistic mle: A generic model- based algorithm for partially observable sequential decision making. In Proceedings of the 55th Anmual ACM Symposium on Theory of Computing, pp. 363-376, 2023a.
Zhihan Liu, Miao Lu, Wei Xiong, Han Zhong, Hao Hu, Shenao Zhang, Sirui Zheng, Zhuoran Yang, and Zhaoran Wang. One objective to rule them all: maximization objective fusing estimation and planning for exploration. arXiv preprint arXiv:2305. / 18258, 2023b.
Ronald Ortner. Regret bounds for reinforcement learning via markov chain concentration. Journal of Artificial Intelligence Research, 67:115-128. 2020.
Yi Ouyang. Mukul Gagrani, Ashutosh Nayyar, and Rahul Jain. Learning unknown markov decision processes: A thompson sampling approach. Advances in neural information processing systems, 30, 2017.
11

---

Published as a conference paper at ICLR 2024
Scott Proper and Prasad Tadepalli. Scaling model-basee average-reward reinforcement learning for product delivery. In European Conference on Machine Learning, pp. 735-742. Springer, 2006.
Martin L Puterman. Markov decision processes: discrete stochastic dynamic programming. John Wiley & Sons, 2014.
Daniel Russo and Benjamin Van Roy. Eluder dimension and the sample complexity of optimistic exploration. Advances in Neural Information Processing Systems, 26, 2013.
Niranjan Srinivas, Andreas Krause, Sham M Kakade, and Matthias Seeger. cess optimization in the handit setting: No regret and experimental design. arXiv preprint arXiv:0912.3995, 2009.
Gaussian pro-
Wen Sun, Nan Jiang, Akshay Krishnamurthy, Alekh Agarwal, and John Langford. Model-based rl in contextual decision processes: Pac bounds and exponential improvements over model-free approaches. Conference on learning theory, pp.
PMLR, 2019.
Richard S Sutton and Andrew G Barto. Reinforcement learning: An introduction. MIT press, 2018.
Csaba Szepesvári. Algorithms for reinforcement learning. Synthesis lectures on artificial intelli- gence and machine learning, 4(1):1-103, 2010.
Jinghan Wang, Mengdi Wang, and Lin F Yang. Near sample-optimal reduction- policy learning for average reward mdp. arXiv preprint arXiv:2212.00600 2022.
Ruosong Wang, Russ R Salakbutdinov, and Lin Yang. Reinforcement learning with general value function approximation: Provably efficient approach via bounded eluder dimension. Advances in Neural Information Processing Systems, 33:6123 6135, 2020.
Yining Wang, Ruosong Wang, Simon S Du, and Akshay Krishnamurthy, Optimism in reinforcement learning with generalized linear function approximation. arXiv preprint arXiv:1912.041 2019.
Chen-Yu Wei, Mehdi Jafarnia Jahromi, Haipeng Luo, Hiteshi Sharma, and Rahul Jain. Model- free reinforcement learning in infinite-horizon average-reward markov decision processes. In International conference machine learning, pp. 10170-10180. PMLR, 2020.
Chen-Yu Yu Wei, Mehdi Jafarnia Jahromi, Haipeng Luo, and Rahul Jain. Learning infinite-horizon average-reward mdps with linear function approximation. In International Conference on Artifi- cial Intelligence and Statisties, pp. 3007-3015. PMLR, 2021.
Yue Wu, Dongruo Zhou, and Quanquan Gu. Nearly minimax optimal regret for learning infinite- horizon average-reward mdps with linear function approximation. In International Conference on Artificial Intelligence and Statistics, pp. 3883-3913. PMLR, 2022.
Nuoya Xiong, Zhuoran Yang. and Zhaoran Wang. A general framework for sequential decision- making under adaptivity constraints. arXiv preprint arXiv:2306. 14468, 2023.
Lin Yang and Mengdi Wang. Sample-optimal parametric q-learning using linearly additive features. In International Conference on Machine Learning, pp. 6995-7004. PMLR, 2019.
Andrea Zanette, Alessandro Lazaric, Mykel Kochenderfer, and Emma Brunskill. Learning near op- timal policies with low inherent bellman error. In International Conference on Machine Learning, pp. 10978-10989, PMLR, 2020.
Zihan Zhang and Xiangyang Ji. Regret minimization for reinforcement learning by evaluating the optimal bias function. Advances in Neural Information Processing Systems, 32, 2019.
Zihan Zhang and Qiaomin Xie. Sharper model-free reinforcement learning for wverage-reaard markov decision processes. 5476-5477. PMLR, 2023.
The Thirty Sixth Annual Conference on Learning Theory, pp-
Zihan Zhang, Yuan Zhou, and Xiangyang Ji. Almost optimal model-free reinforeement learningvia reference-advantaee decomposition. Advances in Neural Information Processing Systems, 33: 15198-15200 15207, 2020.
12

---

Published as a conference paper at ICLR 2024
Heyang Zhao, Jiafan He, Dongruo Zhou, Tong Zhang. and Quanquan Gu. Auriance-dependent regret bounds for linear bandits and reinforcement learning: Adaptivity and computational efficiency. arXiv preprint arXfv:2302.10371 2023.
Han Zhong and Tong Zhang. A theoretical analysis of optimistic proximal policy optimization in linear markov decision processes. arXiv preprint urXiv:2305.08844 2023.
Han Zhong, Wei Xiong, Sirui Zheng, Liwei Wang, Zhaoran Wang, Zhuoran Yang, and Tong Zhang. Gee: A unified framework for interactive decision making mdp, pomdp, and beyond. arXiv preprint arXiv:2211.0196. 2022.
Dongruo Zhou and Quanquan Gu. Computationally efficient horizon-free reinforcement learning for linear mixture mdps. arXiv preprint arXiv:2205. 1507, 2022.
Dongruo Zhou, Quanquan Gu, and Csaba Szepesvari. Nearly minimax optimal reinforcement learn- ing for linear mixture markov decision processes. In Conference Learning Theory, pp. 4532- 4576. PMLR, 20
Dongruo Zhou, Jiafan He, and Quanquan Gu. Provably efficient reinforcement learning for dis- counted mdps with feature mapping. International Conference on Machine Learning, pp- 12793-12802. PMLR, 2021b.
13

---

Published as a conference paper at ICLR 2024
A BACKGROUNDS AND TECHNICAL NOVELTIES
Notations. For any integer E N+ take the convention to use [n]] = {1, {l....,n) n...
Consider two non-negative sequences h220 and {bn if lim simsupa,, an/bn < oc, then we write it as
On (b,,). Else if lim sup /n, O, then we write it as on = (bba). And we use Ô to omit the logarithmic terms. Denote A be the probability simplex over the set X. Denote by sup, [e(x)) the supremum norm of a given function. A stands for min(x, 2) and V stands for max y). Given any continuum S, let |S] be the cardinality. Given two distributions P. Q E A(X), the TV distance of the two distributions is defined as TV(P.Q) (ee-))=@eeellllle plee=elld(()) (d))) 1l].
Infinite-horioon Average-reward MDPs Pioneering works by Auer et al. (2008) and Bartlett & Tewari (2012) laid foundation for model-based algorithms operating within the online framework with sub-linear regret. In recent years, the pursuit of improved regret guarantees has led to the emergence of multitude of new algorithms. In tabular case, these advancements include numerous model-based approaches (Ouyang et al., 2017; Fruit et al., 2018 8; Zhang & Ji, 2019; Ortner, 2020) and model-free algorithms (Abbasi- Yadkori et al., 2019; Wei et al., 2020; Hao et al., 2021; Lazic et al., 2021; Zhang & Xie, 2023). In the context of function approximation, POLITEX (Abbasi-Yadee Yadkori et al., 2019); variant of the regularized policy iteration, is the first model-free algorithm with linear value-function approximation, and achieves Ö(T&) regret for the ergodic MDP. The work by Hao et al. (2021) followed the same setting and improved the results to Õ(T3) ) with an adaptive approximate policy iteration (AAPI) algorithm. Wei et al. (2021) proposed optimistic Q-learning algorithm FOPO for the linear function approximation, and achieve a near-optimal ((VT) regret. On another line of research, Wu et al. (2022) delved into the linear function approximation under the framework of linear mixture model, which is mutually uncoverable concerning linear MDPs (Wei et al., 2021), and proposed UCRL2-VTR based on the value-targeted regression (Ayoub et al., 2020). Recent work of Chen et al. (2022a) expanded the scope of research by addressing the general function approximation problem in average-reward RL and proposed the SIM-TO- REAL algorithm, which can be regarded an extension to UCRL2- VTR. In comparison the works mentioned, our algorithm. LOOP, not only addresses all the problems examined in those studies but also extends its applicability to newly identified models. See Table for summary.
Function Approximation in Finite-horizon MDPs. In the pursuit of developing sample-efficient algorithms capable of handling large state spaces, extensive research efforts have converged on the linear function approximation problems within the finite-horizon setting. See Yang & Wang (2019); Wang et al. (2019); Jin et al. (2020); Ayoub et al. (2020); Cai et al. (2020); Zhou et al. (2021a;b); Zhou & Gu (2022); Agarwal et al. (2022); He et al. (2022); Zhong & Zhang (2023); Zhao et al. (2023); Huang et al. (2023); Li & Sun (2023) and references therein. Furthermore, Wang et al. (2020) studied RL with general function approximation and adopted the eluder dimension (Russo & Van Roy, 2013) as a complexity measure. Before this, Jiang et al. (2017) considered a substantial subset of problems with low Bellman ranks. Building upon these foundations, Jin et al. (2021)
combined both the Eluder dimension and Bellman error, thereby broadening the scope of solvable problems under the concept of the Bellman Eluder (BE) dimension. In parallel line of research, Sun et al. (2019) proposed the witness ranking focusing on the low-rank structures, and Du et al. (2021) extended it to encompass more scenarios with the bilinear class. Besides, Foster et al. (2021: 2023) provided a unified framework, decision estimation coefficient, for interactive decision making. The work of Chen et al. (2022b) extended the value-based GOLF (Jin et al., 2021) with the introduction of the discrepancy loss function to handle the broader admissible Bellman characterization (ABC) class. More recently, Zhong et al. (2022); Liu et al. (2023b) proposed a unified framework measured by generalized eluder coefficient (GEC), an extension to Dann et al. (2021) that captures almost all known tractable problems. All these works are restricted to the knite-horizon regime, and their complexity measure and algorithms are not applicable in the infinite-horizon average- reward setting.
Now-Switching Cost Algorithms. Addressing low-switching cost problems in bandit and rein- forcement learning has seen notable progress. Abbasi-Yadkon et al. (2011) first proposed an algo- rithm for linear bandits with Oloo T) switching cost. Subsequent research extended this to tabular MDPs, including works of Bai et al. (2019): Zhang et al. (2020). A significant stride was made by Kong et al. (2021), who introduced importance scores to handle low-switching cost scenarios in general function approximation with complexity measured by eluder dimension (Russo & Van Roy,
14

---

Published as a conference paper at ICLR 2024
2013). Recently, Xiong et al. (2023) introduced the eluder condition (EC) class, offering a com- prehensive framework to address all tractable low-switching cost problems above. In the context of average-reward RL, Wei et al. (2021); Wu et al. (2022); Chen et al. (2022a); Hu et al. (2022) de- veloped low-switching algorithms to control the regret under linear structure or model-based class, leaving unifying framework for both value-based and model-based problems open problem.
Further Elaboration on Our Contributions and Technical Novelties. Compared to episodic MDPs or discounted MDPs, AMDPs present unique challenges that prevent straightforward exten- sion of existing algorithms and analyses from these well-studied domains. One notable distinction a different regret notion average-reward RL due to a different form of the Bellman optimality equation. Furthermore, such difference is coupled with the challenge of exploration in the context of general function approximation. To effectively bound this regret, we introduce a new regret de- composition approach within the context of general function approximation (refer to (5.1) and (5.3)). This regret decomposition suggests that the total regret can be controlled by the cumulative Bellman error and the switching cost. Inspired by this, we propose optimistic algorithm with lazy updates in the general function approximation setting, which uses the residue of the loss function as the in- dicator for deciding when to conduct policy updates. Such lazy policy update scheme adaptively divides the total of T steps into (log 7') epochs, which is significantly different from (OLSVL. Wei al., 2021) ) that reduces the infinite-horizon setting to the finite-horizon setting by splitting the whole learning procedure into several H-length epoch, where H typically chosen as O ((VT) (Wei et al.. 2021). We remark that such an adaptive lazy updating design and corresponding analysis are pivotal in achieving the optimal ((vT) rate, as opposed to the ((73/1) regret in (OLSVLFH; Wei et al., 2021). Moreover, our approach an extension for average-reward setting (Wei et al., 2021; Wu et al., 2022) that leverages the postulated linear structure and not applicable to problems with general function approximation. Furthermore, to accommodate the average-reward term, we introduce new complexity measure AGEC, which char- acterizes the exploration challenge in general function approximation. Compared with Zhong et al. (2022), our additional transferability restriction is tailored for the infinite-horizon setting and plays a crucial role in analyzing the low-switching error. Despite this additional transferability restriction, unifying complexity measure in the
the existing lazy update approaches
AGEC can still serve ting. like the role of GEC in the finite-horizon setting. Specifically, AGEC captures a rich class of tractable AMDP models, including all previously recognized AMDPs, including all known tractable AMDPs, and some newly identified AMDPs. See Table for a summary.
average-reward set-
Discussion about distribution families Beyond the singleton distribution family DA taken in this paper, there exists a notable distribution family Dx = (DH,t he(r), proposed in Jin et al. (2021), where DH,, characterizes probability measure over S x A obtained by executing different policies induced by fi...., ft-1 E H. measures the detailed distribution under sequential policies. However, in this paper, we exclude the consideration of Dit for two principal reasons. First, evaluations of average-reward RL focus on the difference between observed rewards r(st, as) and optimal average reward J as opposed to the expected value V," (i.e expected sum of reward) under specific policy and optimal value at step h E [H] in episodic setting rendering the introduction of Dz unnecessary. Second, infinite settings, the measure of such distribution becomes highly intricate and impractical given different policy induced by /i,..., Jr over a potentially infinite T -tepps. As a comparison, in the episode setting a fixed policy induced by fo is executed over a finite H -step.
B ALTERNATIVE CHOICES OF DISCREPANCY FUNCTION
Note that there is another line of research that addresses model-based problems using Maximum Likelihood Estimator (MLsE)-based approaches (Liu et al., 2023a; Zhong et al., 2022), as opposed to the talue-targeted regression with reward function known. We remark that these MLE-based ap- proaches can be also incorporated within our framework through the use of the discrepancy function:
(r.(5.g.. Ct) - IP, (st4 /I) az) 1/,
(B.2)
where the trajectory is Ge = (St, az, 12+1) with expectation taken over the next transition state 8 from [P(1|s,, a:) such that E,, discrepancy function in (B.2), we introduce a natural variant of AGEC defined below.
G.)] = TV (P (-1,,, at). y. (-Is,, az)). To accommodate the
15

---

Published as a conference paper at ICLR 2024
Algorithm 2 MLE-based Local-fitted Optimization with MMLtiis0nn
Parameter: Initial 81, span sp(V") optimistic parameter / c log (1T))(1/T)/0)
Initialize: Draw a1 Unif(AA) and set To t O, To 0, Bo < 0. Do + 0.
I: for = 1,..., do
2: i or T 2 3y then
3: Update Tr
4:
Solve optimization problem Jr = arginax Ji where
B, { sE#: :: LD, (s, - inl LD. (f.9) s 5 $). gEg
(B.1)
5:
Update Qi Q1 V/ Ví, Jr = Jj. and 91 = inf LD. (fr
gEg
6:
else
7:
Retain (Je, Jz, V,, Qc, Tp) =
Je-1, V 01-1,
8:
Execute a, argmax Qx(s,,
9:
Collect reward = r(st, az) and transition state S1+1-
10:
Update D, = 1 (8t, at, re, (41)), Y, E..EDD TV ( (a (1),
Definition 9 (MLE-AGEC). Given hypothesis class H. the MLE-discrepancy function (ly fen in (B.2) and constant > O, the MLE-based average-reward generalized eluder coefficients MLE-AGEC(H, (1y),e) e) is defined as the smallest coefficients Kg and de such that following two conditions hold with absolute constants C > 0:
(i) (MLF-Bellman dominance) There exists constant de > 0 such that
{(f)(s)))) do sp(V*) Σ
(fe Gilll.
(ii (MLE-rranseerbbiiitt) There exists constant KG such that for hypotheses fi...., E H. if it holds that Σ fee S /Bt for all E [T]. then we have
T
Σ E& (f,, poly(log /R Re BT + C1 sp(V*)3 minfro: T) minf")mmn((n 2Tc
The main difference between the MLE-based variant (see Definition 9) and the original AGEC (see Definition 3) is that the coefficients are defined over the & -ormm rather than the nornm, and similar condition is considered Liu et al. (2023a); Xiong et al. (2023). Now, we are ready to introduce the algorithm for the alternative discrepancy function in (B.2) and please see Algorithm 2 for complete pseudocode. The main modification lies in the construction of confidence set and update condition Y,. Here, the confidence now follows
B, = (f+ H: CD inf Co._, (f..9) Lolf.9) DEG
Σ (s.0,)))D
log (s'ls, a).
In comparison, the update condition follows that Y, E(,a)E (-ss, (-Is, a)). Un- like the standard LoOP algorithm, the the confidence set and update condition in the MLE-based varint longer shares the same construction. Following the literature of MLE-based algorithms, we adopt the bracket number to approximation the cardinality of the function class.
Definition 10 (p-brackes) Let p > and F is a set of functions defined over X. Under -nomm, a of functions (F) is p-bracket of F if for any E F. there exists function f' F such that the following two properties hold: (i) ('(x)) > f(x) for all x E X', and (ii) | f']] S p. The bracketing number (p) is the cardinality of the smallest p-bracket needed cover F.
The theoretical guarantee is provided below.
16

---

Published as a conference paper at ICLR 2024
Theorem (Cumulative regret). Under Assumptions 1-2 and the discepancy function in (B.2) with self-completeness such that g = H. there exists constant c such that for any 6 E (0, 1) and time horizon T,, with probability at least 1 - 46, the regret of MLE-LOOd satisfies that
Reg(T) < (sp((V)) dVTB).
where 3 clo (1T//( sp(v"), d= /GG. Here, (do, kG) AGECA {4y), 1/VT) denote MLE-AGEC defined in Definition and (x(() denotes the bracketing number.
The proof Theorem 4 similar to that of Theorem 3, and can be found in Appendix H.1.
C CONCRETE EXAMPLES
In this section, we present concrete examples of problems for AMDP. We remark that the under- standing of function approximation problems under the average-reward setting is quite limited, and to our best knowledge, existing works have primarily focused on linear approximation (Wei et al., 2021; Wu et al., 2022) and model-based general function approximation (Chen et al., 2022a). Here, we introduce variety of function classes with low AGEC. Beyond the examples considered in exist- ing work, these newly proposed function classes the finite-horizon episode setting (Jin et al., 2020; Zanette et al., 2020; Du et al., 2021; Domingues al., 2021), which can be extended to the average-reward problems with moderate justifications.
mostly natural extensions from their counterpart
C.I LINEAR FUNCTION APPROXIMATION AND VARIANTS
Linear function approximation Consider the linear FA, which encompasses a wide range of con- crete problems with state-action bias function linear in a d-dimensional feature mapping. Specif- ically, linear function class H is defined as H. {Q(-.-)
(w, ()..)),J J Jxll|w|le I >sp(V))VV) where the feature satisfies that || S 2 with first coordinate fixed to 1. We remark that such scaling is without loss of generality justified in Lemma 19. To begin with, first introduce two specific problems: linear AMDP and AMDP with linear Bellman completion.
Definition 11 (Linear AMDP, Wei et al. (2021)). There exists a known feature mapping é S SxAA + Rd unknown d-dimensional signed measures
(HI..... :4)) over S, and unknown reward parameter O Ed such that the transition kernel the reward function can be written as
P(-|s, a) (ő(s, p(-)), r(s, a) (ő(s, 8).
(C.1)
for all (s, a) ESEXXX Without loss of generality, we assume that the feature mapping & satisfies that 1|0b|2.000 S 2 with first coordinate fixed to 1, ||0||2 vd and [|m(S)]l2 S vd, where we denote ((S) = (I)....... and (4(5) = Is (s), be the total measure S.
We remark that the scaling on the feature mapping can help in overcoming the gap between the episodic setting and the average-reward one by ensuring the linear structure of Q- and V-value func- tion under optimality (Wei al., 2021). To illustrate the necessity, note that
as) - r(s,a) Ex (s') - - J== a(s (D-J'a + / (
where denote e (1,0,... (1. 0) E Rd. Next, we provide the AMDPs with linear Bellman comple- tion. modified from Zanette et al. (2020), which is more general setting than linear AMDPs. Definition 12 (Linear Bellman completion). There exists a known feature mapping o: S -SxAA + Bd such that for all (s, a) S A, E Wy and J Jn. we have
(T(w, (Tw,, J),ss, == r(s, a) + (()
a'EAA w (TTTToss o(s's
max
(C.2)
Generalized linear function approximation extend by incorporating link function. In generalized linear FA, the hypotheses class is defined as
To introduce the nonlinearity beyond linear FA, we
17

---

Published as a conference paper at ICLR 2024
H (Q(:)) (((())))) J Jull|ola I Vdl, where (|)(,,))]22,00 S and R R an a-bi-Lipschitz function with |lo|| I {)p((V)) We say is a-bi-Lipschitz continuous if
1 x - - lo(x) -(x a - - Vr, E..
(C.3)
We remark that the generalized linear function class H. degenerates the standard linear function class H. if we choose (x)) = Modified from Wang et al. (2019) for the episodic setting, we define AMDPs with generalized linear Bellman completion as follows.
Definition 13 (Generalized linear Bellman completion). There exists a known feature mapping 6:Sx A + Rd such that for all (s, a)
A, w E Wh and E Jn. we have
= r(s, a) ( max (a (wT o (( (T(w,)) o(-))) (o(,)))()()))))))
(C.4)
a'EA
The proposition below states that (generalized) linear function classes have low AGEC.
Proposition 5 (Linear FA C Low AGEC). Consider linear function class Hi and generalized linear function class Hamn with a d-dimensional feature mapping é S x A + R4, if the problem follows one of Definitions 11-33, then it have low AGEC under Bellman discrepancy in (3.1):
dG ld (sp(V*) (o(V")vde-") Tog
KG S O(dlog (sp(V" (sp(V")Vd==)).
Linear /* AMDP Moreover, consider the linear Q* AMDPs, which is modified from the one in Du et al. (2021) under the episodic setting.
Definition 14 (Linear Q² AMDP). There exists known feature mappings & S A + Rd T S IR 22 and unknown vectors w' E Rdd, 0" E Rdd such that optimal value functions follow (s(s (o(s,)),
V*(s') (v(s'),0*)
for all (s, a, s') E S x S. Without loss of generality, we assume that features 11ol2,,0 v2 and 12 I 22 with first coordinate fixed to and ||| 1|2 }sp(V*)Vdl, |10 12 (sp(V)) Vb.
The proposition below states that linear Q" 2"/V* also has low AGEC.
Proposition (Linear /V Low AGEC). Linear Q* AMDPs with coupled (d1, d2)- dimensional feature mappings o 6::: x A Rd and : S RR have low AGEC such that
de - Od+ log
IogT), KG S Odt log (sp(V")Vate"")
where denote d+ d1 + d2 as the sum of dimensions of features.
The proposition above asserts that in linear Q*/V* AMDPs, with additional structural information in state bias function, add (d2) in complexity from the AGEC perspective. We remark that linear FA, generalized linear FA, and linear Q"/V" AMDPs are typical value-based problems. The proof of this proposition relies on ABE dimension as an intermediate, and then uses Lemma 2.
C.2 KERNEL FUNCTION APPROXIMATION
In this subsection, we first introduce the notion of effective dimension. With this notion, we prove a useful proposition that any kernel function class with a low effective dimension has low AGEC. Consider kernel FA, natural extension to linear FA from d-dimensional Euclidean space 2d to a decomposable kernel Hilbert space K. Formally, a kernel function class is defined Jxl ||ا| < sp(V*)R), where the feature mapping ::8 A IC satisfies that || I 1. To measure the complexity of problems in Hilbert space with a potentially infinite dimension, we introduce the e-effective dimension below.
H. (Q(-.) (6(-)),w))x,>
Definition 15 (c-effective dimension). Consider a set Z with the possibly infinite elements in given separable Hilbert space K,, the c-effective dimension, denoted by dim ( (Z, c), is defined as the length n of the longest sequence satisfying the condition below:
sup
log det [I+ Φ Σ
2i2
3 S EZ
18

---

Published as a conference paper at ICLR 2024
Here, the concept of c-effective dimension is inspired by the measurement of maximum information gain (Srinivas et al., 2009) and is later introduced as complexity measure Hilbert space in Du et al. (2021); Zhong et al. (2022). Similar Jin et al. (2021), augment the assumption by requiring the H. to be self-complete under average-reward Bellman operator, i.e., 9 = H. Next, the proposition below demonstrates that kernel FA has low AGEC.
Proposition 7 (Kernel FA C Low AGEC). Under the self-completeness, kernel FA with function class Hker concerning known feature mapping Φ S x A A K. have low AGEC such that
dG I dimen (X, c/2sp(V") log T, RG S dimett c/22s(VV"))
where denote X' { (s, a) E S x A} the collection of feature mappings.
The proposition above shows that the kernel FA with low e-efeective dimension the Hilbert space also has low AGEC. As special case of kernel FA, if we choose K = R., then we can prove that the RHS in the proposition above is upper bounded by (dd)
C.3 LINEAR MIXTURE AMDP
In this subsection, focus the average-reward linear mixture problem considered in Wu et al. (2022). In this context, the hypotheses function class is defined as H. = (I((''(s,)) = (0, ((, 0, 8)))
r(s,a) = (0, (tss(())))ll)) a))1l0122 S 1} with known feature mappings é S A + Rd
8 x A Rd and unknown parameter 0 Rd. The problem is defined as below.
Definition 16 (Linear mixture AMDPs, Wu et (2022)). There exists a known feature mapping S:5 A x S Rd. 3b: : 8 A + gd, and an unknown vector 0 Rd it holds that
P(s'|s, s, a) (0, ((s, a, s')), r(s,a) = (6, (s)a)).
for all (8, (s,, 8') E 8 x S. Without loss of generality, we assume || S Vd. 1116112,00 S Vd.
Now we show that the linear mixture problem tractable under the framework of AGEC. Proposition 8 (Linear mixture C Low AGEC). Consider linear mixture problem with hypotheses class H. and d-dimensional feature mappings (Ø, v). If we choose discrepancy function as
(f G.) = 0g (v(s),,)) ax) + [ d(s a,, s') v') - -r(st, ax) - -y
(C.5)
and takes H G with operator following P(J) = 1 for all f H. has low AGEC such that KG So =ddlog (sp(V")T/vde).
de s o lol (sp(V")T/vVee)
The proposition posits that AGEC can capture the linear mixture AMDP, based on modified version of the Bellman discrepancy function in (2.2). In contrast to the linear FA discussed in Appendix C. the presence of the average-reward term in this model-based problem does not impose any additional computational or statistical burden, and there no need for structural assumptions on feature mappings, such fixed first coordinate, considering discrepancy in (C.5).
D PROOF OF MAIN RESULTS FOR LOOP
D.1 PROOF OF THEOREM 3
Proof of Theorem 3. Note that the regret can be decomposed as
Reg(T) Σ J ((t),a)))
Σ Jr r((
(optimism)
T
((f) a.)
Eg B (u((s) aeA
max (e(3441.a)
((f)) at)
(M Vi(st))
(D.1)
Bellman error
Realization error
19

---

Published as a conference paper at ICLR 2024
where step (a) and step (b) follow the definition of the Bellman optimality operator and the greedy policy. Below, we will present the bound of Bellman error and Realization error respectively.
Step 1: Bound over Bellman error Recall that the of confidence set ensures that LD (ft, ft) inf geg (ft,g) (3) across all steps. Using the concentration arguments, we can infer
Σ 1 ft, G0112 O(3),
(D.2)
with high probability and the formal statements are deferred to Lemma 10 Appendix D.3. In the following arguments, we assume the above event holds. Take 1/vT, recall the definition of dominance coefficient do in AGEC(H. J.l,e) and it directly indicates that
1/2
Bellman error Σ E(f)ss))))) dG ΣΣ
BB Ur, ft.
+0 -0 =s(s(VV))Vde"
t=1 1=1
and thus the Bellman error can be upper bounded by O (sp((*))
Step 2: Bound over Realization error To bound Realization error, we use the concentration argument and the upper-boundded switching cost. Note that
Realization error
V (((s)))-((()))+0000 ((0
- VT (00
(Shift)
Σ (s+41) - ((41((112))) 1(T T+11) - ( log(1/8))
(og((11)))))))))
sp()) N(T) + (o(sp((")TTTollll
Oss((V*) HG T log( ( 1/8)
(D.3)
where step (c) directly follows the Azuma-Hoeffding inequality and step (d) is based the fact that [|V, V llx I sp(V") and the bounded switching cost such that (T)) S O(KG log where Kg is the transferability coefficient in AGEC with 1/VT. Please refer to Lemma 11 in Appendix D.4 for the detailed statement and proof of the bounded switching cost.
Step 3: Combine the bounded erroes Plugging (D.2) and (D.3) back into (D.1), we have Reg(T) < Bellman error Realization егrоr
< O (p((V)) dr + O(sp(V*s)))))))p JaG log(1/8)) (sp((V)) d dVT3)
where d max VdG KG} is a function of (da, RG) = AGEC(H, (1y) 1/vT). In the argu- ments above, the optimistic parameter is chosen as / = e clog (U . sp((*), which takes the upper bound of the optimistic parameters, aligning with the choice in Lemma 9, Lemma 10, and Lemma 11. Then finish the proof of cumulative regret for LOOP in Algorithm I.
D.2 PROOF OF LEMMA 9
Lemma 9 (Optimism). Under Assumptions 1-4, LooP is optimistic algorithm such that it ensures J 2 J for all & E [T] with probability greater than 1 - 5.
Proof of Lemma 9, Denote VG) be the p-cover of G and Ng(p) be the size of p-cover Vg(9). Consider fixed (i.g) E [T] x G and define the auxiliary function
(g) (f" 99)) F.s)),
(D.4)
20

---

Published as a conference paper at ICLR 2024
where f is the optimal hypothesis in value-based problems and the true hypothesis in model-based ones. Let Ft be the filtration induced by {81, ai....,, St, ar) and note that f fo is fixed under the filtration, then we have
,, (9) = (c s:)1 PPF
= =Ec, -. - (f,(f (1 ((,)), F.
(). = =Ec, Rc, (1" (1)0) si
=IIEs [4, :f. (:)
where the equation follows the definition of generalized completeness (see Assumption 4):
Ec, Ee,lyr ()) - -
(f..l1 =
Similarly, we can obtain that the second moment of the auxiliary function is bounded by
1 ( O (sp((V') |I (S" .. 3)l1().
By Freedman's 's incquality (see Lemma 18), with probability greater than - 8 holds that
(0)
(
0o 1og(1/0)- - sp(V Σ || U4 (f" Sill2 + log(1/6)
By taking union bound over [T] x Vg()), for any (t) E [T] Vg(G) we have - Ei= (o) s OC)), where Ç sp(V*) (og( negative. Recall the definition of p-cover, it ensures that for any g E G. there exists ø E V. such that (lg(s.a) 6(s, als,a)ll1 S p for all (s, E S x A. Therefore, for any
and use the fact that | (f", (f G is non-
we have
Xx,1 <((+tt)
(D.5)
Combine the (D.5) above and the designed confidence set, then for all t E [T] it holds that
inf LD._, (f" - Σ ( s <((+to) <B, 9EG
LD. (D.,,(f,
(D.6)
where ÿ is the local minimizer to LD. (s', (). and we take the covering coefficient as p 1/T and optimistic parameter as B clog Zug Rug((1/T)) (1)T)/8) -s((V). Based on (D.6), with probability greater than - 8, f* a candidate of the confidence set such that J, 2 J for all t E [T].
D.3 PROOF OF LEMMA 10
Lemma 10. For fixed p > 0 and the optimistic parameter c(sp((*)) (TN2 (p)/6)++)
where 0 is constant large enough, then it holds that
Σ Eg. fu (03).
(D.7)
for all E [I'] with probability greater than 8.
Proof of Lemma 10. Denote (H) be the p-cover of H and Nx(P) be the size of p-cover V,(H).
Consider fixed fi E [T] x H. and define the auxiliary function
Ni,,, (f) | (J,S,)) -11e::-11,,,.. (1P))))))
21

---

Published as a conference paper at ICLR 2024
Let F. be the filtration induced by {si, 01 ................................ .t, and note that fi...., ft is fixed under the filtration, then we have
(f)
- (
EE,, (x) [4
(f.
where the equation generalized completeness (see Lemma 9). Similarly, we can obtain that the second moment of the auxiliary function is bounded by
((X <
By Freedman's ' inequality in Lemma 18, with probability greater than 8 we have
(f)
|| (f..
so |oog(1/) sp(V*)2 (
Σ Ba (A 1
Define Ç= (=sp(V*) (8), by taking union bound over p-covering of hypothesis set H, we can obtain that with probability greater than 1 8, for all (1) [T] ()(H) we have
Σ (6)
Σ
B (0. 3
< spp((V))
Be In (o, o, G)
(D.8)
The following analysis assumes that the event above is true. Recall that the LooP ensures that
(-1
Σ (f)) =
E (f.
Σ
inf Σ (f. S1.
geg
i=1
= Co,,,,
inf LD. (fe.g) S O(3). gEg
(D.9)
where the last inequality is based the confidence set and the update condition combined. Note that if the update is executed at time i, the confidence set ensures that
LD._, (fe. fi) inf LD._, (f...((i.9) 9) < 3,
.EG
within the update step Otherwise, the update condition is not triggered, we have fr. = fo and inf LD.., (fr, 48.
r, = CD...ff
gEG
Recall that based on the definition of p-cover for any f H. there exists ò E V,() such that llg(s, a) a)ll & for all (s, a) E S x A, we have the in-sample training error is bounded by
Ex Pa fes Je.
Ec, (Gr, 6r, Gi] 1 O(p))
(p-approximation)
( + +0tp
( ((D.))
+0p=
0(3),
(D.10)
where the last inequality follows (D.9), and takes B c((sp(V*))og (TN2 (P))0) Tp).
22

---

Published as a conference paper at ICLR 2024
D.4
PROOF OF LEMMA 11
Lemma 11. Let (T) be the switching cost with time horizon T, defined as
N(T) # E [2] # T--1}.
Given fixed p 0 and the optimistic parameter c(sp(V*) (V*) log Hug TT)) where > 0 is large enough constant, then with probability greater than 1 - 26 we have
N(T S (KQ log + + --"Te
where KG the transferability coefficient with respect AGEC(H, (,
Proof of Lemma 11. Denote (H( be the p-cover of H and (p((p) be the size of p-cover (HH)..
Step 1: Bound the difference of discrepancy between the minimizer and P(f).
Consider fixed tuple (i, [T] x H. x 9 and define auxiliary function as
(f.) = 1|,, (f. - (f..
Let Ft be the filtration induced by {81, (1,.01..... St, 0²) and note that fI,-.., St fixed under the filtration, then have
(f, = (1. Bu1ll:/0....611l31110000000
EG, (i) Ee, +)0 [|F
where the equation generalized completeness (see Lemma 9). Similarly, obtain that the second moment of the auxiliary function is bounded by
E B < (0 (p())) [R
By Freedman's 's inequality in Lemma 18, with probability greater than 8
(f.)
Σ | (f..
(1
0 [0g(1/0) 1og(1/0))
[C([)/))-p(V))) sp(V+)² Σ
Bg (t.... ()) log(1/6)
Define Ç sp(V*) log(T (p)/0), by taking union bound over p-covering of hypothesis set
H. x G. with probability greater than 1 - 6. for all (t, p) [ x V, x (G) it holds
X (b)
Σ
Eg. (, 3. 3..
( 5. spp(V)) Σ
EG [hr vb 10
(1))))))))) +
(D.11)
where < sp(V*) log( (Tg ( Note that |Be Mr (0, wh G0]] is non-negative, then it holds that E X () s O()) for all E [T]. Based on (D.11) and the p-approximation, have
(f.g) s (0(f)..)()(((+))))
Vt e
23

---

Published as a conference paper at ICLR 2024
for any (f.9) H. x G. Recall that 3 = clog clog(TNN for a [T] we have
(o.(f.P((f)) inf CD. (fr. geg
Σ (L.
inf gEg
Σ 11,, Gi)l
Σ (...(f {c( ()))t)) s
(D.12)
Combine (D.12), and the fact that is defined as the local minimizer among auxiliary class & and P(f+) E G, then for all E (T) we have the difference of discrepancy bounded by
0 s CD. (Se, (f.)
inf LD. (Se:g) S B.
(D.13)
.EG
Step 2: Bound the out-sample training error between updates.
Consider an update is executed at step t++ it directly implies that LD. (ft, fi)-infges (f.. 43, while the latest update step Tr ensures that CD.,-1 (fr,, fr.) ) inf LD. LD_ (fr..)) S 3, where is the pointer of the lastest update. Combined the results above with (D.13), we have
LD. (Je, ft)
LD. (Je, P(J+)) 33, CD.,- (T., LD..-I P(S+)) S 3. (D.14)
It indicates that the of squared empirical discrepancy between two adjacent updates follows
ft. CD (fr. ft) LD
> 23,
(D.15)
where denote Dret De/Dr, Based on the similar concentration arguments as Lemma 10, we have the out-sample training error between updates is bounded by Σi=,. [|,,, (F,, G:)lB B.
Step 3: Bound the switching cost under the transferability constraint.
Denote b ......, byrr), bx((T)+1 be the sequence of updated steps such that 7, E {b,} for all f [2]. and we fix the recorder b = and by(T)+11 = + 1. Note that based on (D.15), the sum of out-sample training error shall have lower bound such that
N(T) but1-1 Σ
Σ (f
(f N(T) B.
(D.16)
Besides, note that the in-sample training error Σ RRg (1y Sr. G) S (B) for all e [T] and based on the definition of transferability coefficient KG (see Definition 3), we have
T
Σ |E I (fe, fi, G:)11 < O (NG 3 log T sp(V*)² min(Ka, T} + TT²)
(D.17)
Combine (D.16) and (D.17), it holds M(T) S (RG log 7 3- T(2) and finish the proof.
E PROOF OF RESULTS ABOUT COMPLEXITY MEASURES
In this section, we provide the proof of results about the complexity metrics in Section 3. We remark that the proof highly relies on Lemma 13 and Lemma 14, which are natural extentions to original results in Jin et al. (2020); Zhong et al. (2022) and proofs are provided in Section G.I.
E.1 PROOF OF LEMMA
Proof of Lemma Recall that the eluder dimension is defined over the function class following
Xx (x,,r(s, a) (rs + Vy) f. E H}.
and for model-based problems, the discrepancy function is chosen as
1r(5g. G) (r, -, Pr r(s.. ax) - (8(+1)).
24

---

Published as a conference paper at ICLR 2024
Step 1: Bound over transferability coefficient.
Start with the transferability coefficient, the condition be equivalently written as
[r, + +, -r-- + Py- Py-Va.)( (s.))))))))))))))
Σ -X (st, < 3, 1I E [T].
(E.1)
Let Lu = f E xx,,,
the generalized pigeon-hole principle (see Lemma 13) indicates that if we take = -D,, Ø: = =X,, - -X Φ = Xn, || S sp(V*) + 2, then it holds that
|1 1. (fi. fú. Gi11 Σ (X - X (st, as),
dimpe (xx, Pa,e). 3 logt + (sp(V*) (o((*)++ + 2)² min(dimpe (2x, Pa, t) + te? dime(AX, c) Blogt + (sp(V") )- + 2)² min lein(dimg ddmm c), te?
(E.2)
given condition that (E.1) holds for all t E [T], where the last equation uses dimpe (x,, D3,E) =
di e). Denote dg dime e), then we have Rig S dg based (E.2).
Step 2: Bound over dominance coefficient.
Based Lemma 14 and {(fr)(s;,a)) Ec, (Ee St) based on definition, it holds that
E
(X X ($t, a:)]
1/2
<
2dDE log
[( -X xx, (oth as))
+ (sp(V*) + min(d T} + Te
t=1 t=1
1/2
=
2dg log? T
Σ
E (f,, fe, (e Gill
+ (sp(V*) + min, T Tc, (E.3)
1=1 1=1
by taking r -D. Xto.f - X + l1eeloo I sp((V))+2 +2, and 1 1 log s 2 T.
E.2 PROOF OF LEMMA
Proof of Lemma 2. Consider the Bellman discrepancy function, defined as ( G.) (y a:) r(st. a4) - Vy($+11 + Jg,
and the expectation is taken over 8:41 from PP(-,,,, az) such that Eg (r, 4:) E(())ss)))
Step 1: Bound over transferability coefficient.
First, we'ne we're going to demonstrate the transferability, Note that the generalized pigeon-hol hole principle (see Lemma 13) directly indicates that, given
(-
Σ
[18()))(8; az)l3 = 1=1
Σ 1=1
we take Φi E(ft), En and I = Da. then for all E [T] we have
Σ (((()))( a) dABE Blogt (sp(V*) 2)2 min(dABE, t) + tt?,
(E.4)
and thus upper bound KG dABE (H,
25

---

Published as a conference paper at ICLR 2024
Step 2: Bound over dominance coefficient.
Based on Lemma 14 and EE, Ur (Je, Sc, (e)l (s;,)) az).
holds that
T
T ΣΣ
1/2
E (s)) az) v 2dABE log T
(8()))(8) az)11 +(sp(V** + 2) min (dABE, T) + Te,
1= ==1
where we take or = E(ff), 1b = EH, Da, (1E S sp(())) + and 1+ log S 2 20ggoog T.O
F PROOF OF RESULTS FOR CONCRETE EXAMPLES
In this section, we provide detailed proof' of results for concrete examples in Appendix C.
F.1 PROOF OF PROPOSITION 5
Proof of Proposition 5. To show that linear FA has low AGEC, we first prove that is captured by ABE dimension dimAnE(H, c), and then apply Lemma 2 (low ABE dim C low AGEC). Suppose that there exists 2 c, (8er.e hemm) S Da. and (fihemm) S H with length m E N, such that
Σ [EU))s), sé, |&(I))()).))) > d', VI E [m]]
(F.1)
Based on Definitions 7-8, dimABE (H, e) the largest m. Following this, we provide detailed dis- cussion about linear AMDPs. AMDPs with linear Bellmen completion, and AMDPs with gener- alized linear completion (see Definition 11-13). Denote (s(s,a) a) 6(8, a) T we for (s, (s,a,1 t)
S x A x (m).
(i). Linear AMDPs. As defined in Definition 11, for any St H. it holds that
{(fe)ss; as) = o(si, a,) Tw=== - p(s;, a;) o(s;. az) / V((s)du(s) + Je ww (wr -w- 0+ S v((s)dp(() + J,e1)
= <b(s;,,,)
(F2)
(ii). AMDPs with linear Bellmen completion. As natural extension to the linear AMDPs, linear Bellmen completeness (see Definition 12) suggests that the Bellman error follows
(8)) a;) (8s; a - (88; a:) T(ur, J:) = ((8,, az) (wr T(wr, J.))
(R3)
(iii). AMDPs with generalized linear completion. Moreover, AMDPs with generalized linear completion further extends the standard linear FA by introducing link functions. Note that
(s)))ss a.) a ( a.) Tw,) a (d(ss,))) TaaaaTTTTTa T(w,, Jo)) and based on the a-bi-Lipschitz continuity condition in (C.3), it holds that
(F.4)
1 ((st, T (wi T(w,, J.)) s ((fi)(s,, a:) o(s), a (wr T(we Jo).
(F.S)
Based on the Lemma 15 and arguments in (i), (ii) and(iii), we are ready to provide a unified proof for linear FA. By substituting the arguments (F22,, (F3) and (F.5) into (F.1), then
( T(w,, J.) s ad' (,(ss,,;)),4 T( JoM
Vt [m].
(F6)
Here, we take a 1 for standard linear FA, and let a be the Lipschitz constant for generalized
linear FA. Based on Lemma 15, if we take Φe ø(s,, az), 1. = -T(we, JJ), Bd = V2, B. =
Vp(V")Vd, c, C₁ = a, C2 a! then - ((dlog(sp(V"")// defined as the length of the longest sequence satisfying (F.6), thus
As the ABE dimension
dimABE (H, < Odlog (sp(V")Vdee).
Based Lemma 2, de Odlog (sp(V*) vde-)) log T) and KG Odlog
26

---

Published as a conference paper at ICLR 2024
F.2 PROOF OF PROPOSITION 6
Proof of Proposition 6. For all Jr. E H. the Bellman error can be written as
(s))) a;) ) = Φ(8i, (1)) Wi - E(p((4+1) ]] 0, + Jr r(8;; a4) (((i,a))) az)) we B(((s++1)) [0 + J, (8) [[ -M)
o(s;, a4) [[+(+++1)]
(0 0 8,
(
Wi w²1
el eee
+ +J+ - Jn)
(F.7)
where the second equation results from Bellman optimality equation in (2.1). Following similar argument in the proof of Proposition 5, we can show that the linear Q" /V' AMDPs have a low ABE dimension with an (di + d22 da)-dimensional compound feature mapping equivalently based on (F.7). Based on Lemma and write dt = d1 + d2, then we have
dG S Odt log (sp(V*) log ni S Odd log (sp(V")VZ=="))
F.3 PROOF OF PROPOSITION 7
Proof of Proposition 7. Similar to linear FA, we will show that kernel FA is captured by by ABE dimension dimABE (H, c). and then apply Lemma 2 (low ABE dim S low AGEC). Suppose that there exists 2 6, (. hsemm C Da, and (Sike(m) S H with length m E N, such that
[() se, |8(f))s), > é, Vt [m].
(F.8)
Suppose the kernel function class has finite c-effective dimension concerning the feature mapping 6. The existence of Bellman error E(fe) is equivalent to the one of W E (W - W):
()f)(ss))) (Q,, (.. :) (d(:-).w, - wi)x (0( :), We),,
(F.9
where the second equation is based on the self-completeness assumption with kernel FA such that H. Denote X, o(st, ae), rewrite the condition in (F.8)
Σ E(TW)) [x. > d,
Vt [m].
(F.10)
Let E, E + sp(-))))((v) I, then |Welle, 22 and é' S |Welll, [Xe llx
for all / E [m]] based on Cauchy-Sware inequlity and ||wllx S sp(V")R. Thus, || 2 0.5
and
log (1+ [+11 =log
det Em++1 det E₁
4R2sp(V* log det I
Σ x.X,
(F.11)
e
based on the matrix determinant lemma. Therefore, (F.10) directly implies that
1 < log < llog
4R'spV"*)2 Σ X
log det I+
e22
and then we have m I dimea (X, c/ (2sp(V**)) Recall that the c-effective dimension is the min- imum positive integer satisfying the condition. As ABE dimension is defined the length of the longest sequence satisfying (F. thus it holds that
dimABE (7,,) dimea e e/2p(VV)))
Based Lemma 2, de dim (X,e/2sp(V*)) log T and Kg dim (2,e/2sp((V))
27

---

Published as a conference paper at ICLR 2024
F.4 PROOF OF PROPOSITION 8
Proof of Proposition 8. Note that expected discrepancy function follows: for any E [T]
(e - 0, (b()))a)) + / ai,
- r(s,,as)) - Ex, (8++1))
= - (s)s,,a)+ + 1 ai (s))'')
(F.12)
Let W;- = 0g - 8" X, = (ss; az) + Is Φ(si, as ('' and Σg = c EE X,X, Note
1/2
1/2
[all.,
cel0r 0-1 + Σ (fe.
22VE+
Σ E. (c.
(F.13)
where we use |0011| S 1. Based on the elliptical potential lemma (see Lemma 17), we have
Σ Xt 1s, Al s Σ 2d log
1
1 Σ [xx.lla)
[1+ (V*()/2) T (vil) = d(c),
S 2d log
(F.14)
where the last inequality results from 11012,,00 S Vd, 1 vd and |1V I }sp(V=).
Combine (F.13) and 1 (IIx, - 2 1) ||Xe||z,2 1, holds that
T
T
Σ
1 (1x 21) -
X x A1 Alc)
(F.15)
Step 1: Bound over dominance coefficient.
Note the sum of Bellman errors follows that
(()))())) Σ (Tr + (P.V)) (rr- + +pp-Vss (8): ar))
T
Σ (0. -0) (T)((((()))))) (V((())())))) az) + 0(80, ar, s'V (s' )ds)
W.T x, (1 (1xille; $1) + 11 > 1)) Σ
t=1
W,T X, (1xt1lzf 1) + (sp(V*) + 2) min miindd()), T)
Σ [Wil (1xills 1) + (sp(V*)+ +2) min(d))), T},
(F.16)
where the first inequality results from (F.15) and the last inequality arises from the Cauchy- -wwrtz inequality. Combine (F.13) and (F.14), we have
T
Wellx, (1xxal>z- A1)
Σ
2Ve+
+
(s Se.
Gi)1
(IXx) (ل 11)
1=1
T
1/2
1/2
1/2
T
1/2
4e
||xe|
A
Σ
Xx D Al
1/2
< 22 Te <2VTe. meindi(l()) T)
d(c)
Σ Σ
[ St.
(F.17)
1=1
28

---

Published as a conference paper at ICLR 2024
where the second inequality results from Cauchy-Swarte inequality and the last inequality follows (F.14). Plugging the result back into the (F.16), we conclude that
t-1 |E (fe. fc.
1/2
{(fi((;) & d(e) ΣΣ
2 Te min()(()) + (sp( ) + 2) min(d(e),
1/2
<
+ (sp(V*) + min(d(e), + Te,
(F.18)
where the last inequality follows AM-GM inequality. Thus, de ((ddlo((D((V*)))\ee)))
Step 2: Bound over transferability coefficient.
Given condition that E
|ااا (fr, fr, cilllB 3 for all E [T], we have
T [E Se, G)11
(0, 8¹) (vbse, at) + olss, a' (' (o)))=))) (VVa())as') ]
2
Σ
T
(W,Tx) x,)2 1 (1x0112 1 + (sp(V*) + 2)² minfd(e),
T
Σ (B 4c) (ixi1 A 11) + (sp(V") + 2) 2)" min
$ d(e) log T + (sp(V*)2 + 4sp((") min((()),, 2T's
(F.19)
where we use variant of (F.14) and (F.15), following that
Σ (I
Σ |
A S
X. 2,
A1 d(e),
1=1
1=1
and the last inequality results from a similar proof as (F.17) and (F.18) using Cauchy-Swartz and AM-GM inequality. Thus, we have Kg S (ovllllssVVV)//VAA
F,5 DISCUSSION ABOUT PERFORMANCE ON CONCRETE EXAMPLES
In this subsection, we show performance of LOOP for specific problems. LoOP achieves an ((VT) regret, which is nearly minimax optimal in T, in linear AMDP and linear mixture AMDP.
Linear AMDP Recall that linear function class is defined as H. = (Q, Q(--) = w o(;))) ) ||wl|a < {spp(V") e Jn.. Consider the p-covering number, note that [Q(s. a) Q' (s. a)l S ((w - w')T ((s a)l S v2 || -
Based on the Lemma 20, combine the fact that [Jxl S 2 and its p-covering number (Nxx is at most 2p we can get the log covering number of the hypotheses class H is upper bounded by
logAn(()) S log (sp(V*)2 p
(F.20)
by taking a = w, p= B = sp Recall that Proposition 5 indicates that do < (d <op(V*>Vdp"> Iog KG S O(d (sp(v")Vdp=") Combine (F:20), (F.11) and the regret guarantee in Theorem get Reg(T) 0 spV))) max/da, kG) / log (1/T))(1
(F.21)
< (
For linear AMDPs, our method achieves ((sp(V VT) regret for both linear and generalized linear AMDPs. In comparison, the Fopo algorithm (Wei et al., 2021) achieves the best-known
Ö(sp(V*) d VT) regret. Our method incurs additional constant sp( sp(V*) in the regret bound.
29

---

Published as a conference paper at ICLR 2024
Linear mixture Recall that the Proposition 8 posits that AGEC of the linear mixture probelm satisfies that max dd, No) I Oddv/log T). Note that the hypotheses class is defined as
H {(P,r) r) IP- a) = 0 o(s, a, ), r(s, a) = 0 vas a) | S 1}.
Consider the covering number note that both transition function and reward be written
(i). (I' P') a)l (0 o'
a s'I (ii). [[ - ( 10 TT (ss a)l S vd. 110 - 0'1l
vd 110 0'11,
Based the Lemma 20, the log covering number of HIm is upper bounded by
logNN(()) S 2d log pt)
by taking a = 0, P= d, = 1. Combine results above and Theorem 3, we get Reg(T) S (sp((VV) max nc) Tlog (1/))((//)
S (sp((V))) 3d vT).
At our best knowledge, the UCRL2-VTR (Wu al., 2022) achieves the best ((Ddv regret for linear mixture AMDP, where is the diameter under communicating AMDP assumption and is provable that sp(V*) D (Wang al., 2022). We remark that the two algorithms are incomparable under different assumptions and both achieve minimax optimal regret ((
G TECHNICAL LEMMAS
In this section, we provide useful technical lemmas used in later theoretical analysis. Most are directly borrowed from existing works and proof of modified lemmas provided in Section G.I.
Lemma 12. Given function class & defined on X, and family of probability measures I over X. Suppose sequence { and { )
I satisfy that for all [K]. Σ [0,,( s
B. Then, for all & E [K], we have
Σ I (1eul
(
f 2
+
dimpE (1,11,))))
Proof. See Lemma 43 of Jin et al. (2021) for detailed proof.
Lemma 13 (Pigeon-hole principle). Given function class + defined on X' with [ø(x]] I C for all
E & and æ X, and family of probability measure over X. Suppose sequence {Øx k C
and 1K {u C P satisfy that for all & E [K]. it holds ~k=1 ( [ox])² s B. Let dpE =
dimpa I,e) be the DE dimension, then for all k E [K] and > O. we have
lor] < 2 dDE + minfk, d)C + ke,
and
E,, [oi]]] dog k + min(k, djC² + ke?.
Proof. See Section G.I.I.
Lemma 14. Given function class & defined on X' with [d(x) S C for all & E and x E X, and a family of probability measure over X. Let dpE dimpe ④ r,e) )) be the DE dimension, then for all k E [K] and e > O, we have
K R
1/2
Eyn [cba] S
dDE (1 + log K)
Eyg [dx)))
+ mim k.C + ke.
30

---

Published as a conference paper at ICLR 2024
Proof. See Section G.1.2.
Lemma 15 (d-upper bound). Let & and y be sets of d-dimensional vectors and |012 S Ba. l S By for any & E and E V. If there exists set (.I,..., @m) and (1/1,... t'm )such that for all
t E [m]] V V (or, ) v e and (dr, she) > c2é, where 2 0 is constant and >> 0, then the number of elements in set is bounded by m S log (BgB
Proof. See Section G.1.3.
Lemma 16. For any sequence of positive reals Fi,..., Tma holds that
E Ri V ix
S v1 + log n.
Proof. See Lemma 6 in Dann et al. (2021) for detailed proof.
Lemma 17. Let farh be a sequence of vectors defined over Hilbert space A. Let Ao be positive definite matrix and A, Ao Σ zx It holds that
| 1 A < log ( det (detAA++)) det Ao
Proof. See Elliptical Potential Lemma (EPL) in Dani al. (2008) for a detailed proof.
Lemma 18 (Freedman's 's inequality). Let Xi,..., Xx be a real-valued martingale difference se- quence adapted to filtration {.8,) Assume for all t E [T] X₂ I R. then for any 17 E (0, 1/R), with probability greater than 1-
T
T
log(1/6)
Σ x, 50
x
Proof. See Lemma 7 in Agarwal al. (2014) for detailed proof.
Lemma 19 (Scaling lemma). Let S x A + Rdd be d-dimensional feature mapping, there exists an invertible linear transformation A E Raxd such that for any bounded function f S x A + IR
and Id defined by
f(s, a) = ((8. z,
have |Ao(s, a)ll and ||A-12|| sups,al sup.aalflve flvd for all (s, Exx
Proof. See Lemma 8 in Wei et al. (2021) for detailed proof.
In Theorem 3, the proved regret contains the logarithmic term of the 1/T-covering number of the function classes (1/T)) which can be regarded surrogate cardinality of the function class H. Here, we provide a formal definition of p-covering and the upper bound of p-covering number.
Definition 17 (p-covering). The p-covering number of a function class F is the minimum integer t satisfying that there exists subset J C F with IF' such that for any f E F we find correspondence f' E F' that it holds f' P.
Lemma 20 (p-covering number). Let F be a function defined over A' that can be parametrized by (0) (.......ap)) I with |asl B for all i [P]. Suppose that for any f. f E F it holds that sup) -f $ Llla a'll, and let Nx(p) be the p-covering number of F, then
2BLP
[=(p) < Pog
P
Proof. See Lemma 12 in Wei et al. (2021) for detailed proof.
G.1 PROOF OF TECHNICAL LEMMAS
In this subsection, present the proofs of technical auxiliary lemmas with modifications.
31

---

Published as a conference paper at ICLR 2024
G.1.1 PROOF OF LEMMA 13
Proof of Lemma 13. The first statement is directly from Lemma 41 in Jin al. (2021), and the second statement follows similar procedure as below. Note that Lemma 12 suggests that
_ I1( (B > 2) ( + + ( (.,
Σ E=
and note that the sum of squared expectation can decomposed as
k
Eng [di]]
En, [ole]] 2 [0o,]
> e²) + Ex [oo]] Bm,
(1 [oe]] S e²
=
Ep,, [oo1] 2 [Øo]] > 2) + kc?
(G.1)
Assume sequence [kn [01]] ..... B [ox]]* are sorted in the decreasing order and consider e [k] such that [R,, [obe]]
2 > 2, there exists a constant a E (c2, [En, [ot]]] satisfying
1 ([Em. > >a)
_ +11) ++1ddimpe ( Va - (2+1)
+1) (impee(0I,,,
where the last inequality is based on the fact that the DE dimension is monotonically decreasing in terms of as proposed in Jin al. (2021). Denote dDE LimpE((9. (,,,, and the inequality above implies that S Ant33/t d. Thus, we have [R [ < dpp. d. Beside, based on the definition we also have [mp [oe]] < C2 and thus [0o]] < min(dDe3// d, C2), then
dDE dnoF
Σ Eu [or] [ (1 [or]2 > =e) min kj
Σ
(
t=d+1
< min k) k2c doE 1/"
p
jall
I min (dDE, k)C² 2 dpe B Blog k.
(G.2)
Combine (G.1) and (G.2), then finishes the proof.
G.1.2 PROOF LEMMA 14
We remark that the proof provided in this subsection follows the almost same procedure as Lemma 3.16 in Zhong al. (2022) with adjustment, and preserve it for comprehension.
Proof of Lemma 14. Denote dpg dimpE (b, I, e). ε [, [ox] and c1 ē (εr, > e) for t, k E [K]. Pt E I and dR E The proof follows the procedure below. Consider empty buckets Bo, Bg- as initialization, and we examine 6A,A one by one for all h: E [K] as below:
Case 1 C 0, i.e., ZR,b S 6, then discard it. Case 2 If c > 0, i.c., ē > e, at bucket j we add & into By if Etsk- 1.EB, (EL,)) s (E,,))
otherwise we continue with the next bucket Bj+1-
Denote by by the index of bucket that at step le the non nonz 6k.b falls in, ie. & E Bbg Based on the rule above, it holds that
K
K
Σ Σ
Σ
(<),)) 2
Σ
by (CK.))
k=1
k= 0=105JJbt
by 15kB,
k=1
where the first inequality arises from {t E B, t k 1, 1, < S by - 1, be 2 c 1] due to the discarding of the bhth bucket, and the second equality directly follows the allocation rule
32

---

Published as a conference paper at ICLR 2024
such that LiSK-LAEB, (ct,t)² (ck,&) for any I bk 1. Recall that based the definition of distributional eluder (DE) dimension, is suggested the size [y] no larger than dDE- Then,
K
K-1
by (c(,)))))
Σ
Σ
(ct,))
(re-summation)
R=1
j=1
BBB,
Σ ExR (EB,
(B3l S dDE)
Erit
Byl
dDE
IBB
2
K-1
2 (dDE (1 log l))
Σ
Σ LE
= (dDE (1 + log K))
61, , (G.3)
J=1
[E[K] Be
where the second inequality follows Lemma 16. Combine the (G.1.2) and (G.3) above, we have
K
k
Σ
Ck.k
Ck.k + Ke
C., + min(dDe, KY ol + Ke
k=1
1=1
*E(K]]
K k-1
1/2
dDE (1 + log K)
Σ
(c
+ min KJC + Ke
R=
t=1
K k-1
1/2
don (1 + log K)
ΣΣ
(2,,))
+ min KJC + Ke.
Substitute the definition εr,x = [R, [ox]]
back into the inequality, then finishes the proof.
G.1.3 PROOF OF LEMMA 15
Proof of Lemma 15. For notation simplicity, denote A, E deer + 2² I. then for all t [m]] B3
have || S v | vx) 1oo.1 V I based on the given condition. Using
the Cauchy-Swartz inequality and results above, then it holds I| 2 Ké 1/)l/
c2/ V +1 On one hand, the matrix determinant lemma ensures that
m-1
2
det. Am det Ao
II (1+ 11+1)))))))) 2
(G.4)
1 c
B
On the other hand, according to the definition of A,, we have
82 d
det Am S (Tr(Am)
12 (m 1m
(G.5)
B
B
Combine (G.4) and (G.5), if we take logarithms at both sides, then we have
B B3B (m
//10g log
c
m < 1 + log
1
de
1 1+
After simple calculations, we can obtain that m is upper bounded by Od BB
H SUPPLEMENTARY DISCUSSIONS
H.1 PROOF SKETCH OF MLE-BASED RESULTS
In this subsection, we provide the proof sketch Theorem 4. We first introduce several useful lem- mas, which is the variant of ones in Appendix D for MLE-based problems, and most have been fully researched Liu et al. (2022: 2023a); Xiong et al. (2023). As there's 's no significant technical gap between episodic and average-reward for model-based problems, only provide proof sketch.
33

---

Published as a conference paper at ICLR 2024
Lemma 21 (Akin to Lemma 9). Under Assumptions 1-2, MLE-LOOP is optimistic algorithm such that it ensures Jj 2 J for all E [T'] with probability greater than 1.
Proof Sketch of Lemma 21. See Proposition 13 Liu et (2022) with slight modifications. Lemma 22 (Akin Lemma 10). For fixed p > 0 and a pre-determined optimistic parameter 3
c(log (TBx(p)/0 + Tp) where constant c >> 0, it holds that
E
(E - E (1ss, a:)) S (()31))
(H.1)
for E (7) with probability greater than 6.
Proof Sketch of Lemma 22. See Proposition 14 in Liu et al. (2022) with slight modifications.
Lemma 23 (Akin to Lemma 11). Let ((T) be the switching cost with time horizon T, given fixed covering coefficient > 0 and pre-determined optimistic parameter / = e(log (TBx(P)/0) + Tp)
where a large enough constant, with probability greater than 25 we have
N(T) S O poly(log T) + 1--g--- "TTTe))
where Kg the transferability coefficient with respect to MLE-AGEC( (c)).c).
Proof Sketch of Lemma 23. The proof is almost the same Lemma 11.
Step 1: Bound the difference of discrepancy between the minimizer and f*
As proposed in Proposition 14, Liu et al. (2022), 0 S Ei= (V as), P (-1s,, az)) < B holds with high probability if the update happens at 1-th step. Based on the AM-GM inequlaity, have
(1s5)-(11s,,)) az). Ps. (115;, az)) S St.
(H.2)
Step 2:
Bound the expected discrepancy between updates.
Note that for all + E [T). the update happens only if
(t) (-1s;, ai)) > 3v Bt.
(H.3)
Combine the (H.2) and (H.3) above, and apply the triangle inequality, we have
(1P,, (-Iss, a:))
as). Po, (+13;, (1)), (o. 2 2 2VBL. 31.
and the construction of confidence ensures that Σ TV ((s S BB with high probability (Liu et al., 2022, Proposition 14). Recall the definition of MLE-transeerabilit coefficient, then the switching cost can be bounded following the same argument Lemma O
Proof Sketch of Theorem 4. Recall that
Reg(T) (s) +
East (eann) Vi(st)).
(H.4)
Bellman error
Realization error
where the inequality follows the optimism Lemma 21. Combine Lemma 22, Lemma 23 and the definition of MLE-AGEC (see Definition 9), then finish the proof.
34

---

Published as a conference paper at ICLR 2024
Algorithm 3 Extended Value lteration (EVI)
Input: hypothesis ry), desired accuracy level c. Initialize: (s) for all S, j(o) and counter i 0.
1: repeat
2: for E S and E A do
3: Set (s) a) f (s, + (oa)) [s)) - -J(0
4: Update ((+ + max (5, a)
5: Update counter i + -+++1
6:
until maxxes (V(++)(s) (s) (s)) min (V(++)) - (8) Se
H.2 EXTENDED VALUE ITERATION (EVI) FOR MODEL-BASED HYPOTHESES
In model-based problems, the discrepancy function sometimes relies on the optimal state bias func- tion Vy and optimal average-reward Jj (see linear mixture model in Section C). In this section, provide algorithm, extended value iteration (EVI) proposed in Auer et al. (2008), to output the optimal function and average-reward under given a model-based hypothesis f = Ty). See Algorithm 3 for complete pseudocode. The convergence of EVI is guaranteed by the theorem below.
Theorem 24. UnderAssumption 1, there exists a unique centralized solution pair (Q". to the Bellman optimality equation for any AMDP M, characterized by hypothesis f E H. Then, the extended value iteration (EVI) is stopped under the condition that
max (s) (()())) #ES
min (++ (s) (() Se, sES
then the achieved greedy policy (0) is e-optimal such that JMH 2 JM, te.
Proof Sketch: See Theorem 12 in Auer et al. (2008).
35


Reviews:
[{"review_id": "uKAA4Vfdm5", "reviewer": "Reviewer_pAvA", "summary": "This paper explores the infinite-horizon average-reward Markov Decision Process (MDP) setting and introduces a comprehensive function approximation framework, accompanied by a corresponding complexity measure (AGEC) and an algorithm (FLOP). When compared with other work addressing AMDPs, the proposed framework covers the widest range of settings including both model-based and value-based, in addition, the theoretical analysis is based on the Bellman optimality assumption and the sample complexity is dependent on finite span, which is weaker compared with previous work (compared with communicating AMDP assumption and finite diameter dependence).", "questions": "- In this paper, the authors directly assume the transferability of the discrepancy function, a concept closely related to Lemma 41 in Jin et al. (2021). Could the authors elaborate on the primary technical challenges they encountered while deriving their theoretical results, when adapt the GEC in Zhong et al. (2022b) to the infinite-horizon average-reward setting, with a constrained algorithm, which seems to be a generalization of the framework established by Jin et al. (2021)?\n\n- Can the authors elaborate the optimality of the regret in Theorem 3, when restricted to each specific instances? i.e. linear mixture AMDP, linear AMDP, etc.", "limitations": "", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "- This paper proposes a general framework for AMDP, encompassing both model-based and value-based. \n\n- The authors propose a new complexity measure that is larger than the Eluder dimension.\n\n- The authors propose a new algorithm that matches the state-of-the art sample complexity results.", "weaknesses": "- The sample complexity is based on GEC and is not entirely novel. Specifically, Definition 3 (Bellman Dominance) in this paper is of the same form with Definition 3.4 of Zhong et al. (2022b), where $d$ is defined such that the sum of the Bellman error being less than the in-sample training error plus the burn-in cost.\n\n- The authors introduce the discrepancy function in the definition of AGEC, and shows a simple example of discrepancy function being the Bellman error for the value-based case, and $(r_g+P_g V_{f'})(s_t, a_t)-r(s_t, a_t)+V_{f'}(s_{t+1})$ for the model-based case.  However, there seems a lack of discussion regarding alternative choices for the discrepancy function, such as the Hellinger distance-based discrepancy in Zhong et al. (2022b).\n\n- The algorithm is based on upper confidence bound, which the confidence region chosen based on the discrepancy function. This approach is closely related to Algorithm 1 in Chen et al. (2022b) and Algorithm 1 in Jin et al. (2021).\n\n- The proposed algorithm is usually impractical to implement, since it involves solving a global constrained optimization.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "kW7CquvnfM", "reviewer": "Reviewer_SbWP", "summary": "This paper studies infinite-horizon average-reward MDPs (AMDPs) with general function approximation. It extends the generalized eluder coefficient to average-reward generalized eluder coefficient (AGEC) under infinite-horizon MDPs. After showing that the low AGEC captures most existing structured MDPs, the paper develops an algorithm called FLOP to solve AMDPs with sublinear regret $O(\\sqrt{T})$.", "questions": "Can authors provide a brief comparison between this work and existing works in terms of the regret results?", "limitations": "", "rating": 8, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "1. The paper provides a more general complexity measure AGEC that captures a large class of MDPs.\n2. The design of confidence set is new, and the lazy update of policy is a good feature of algorithm design, which might be helpful for real implementations.", "weaknesses": "1. While the paper states that method covers most existing works, the detailed comparisons in terms of the regret performance are missed.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "lQNpYbZEZb", "reviewer": "Reviewer_q11B", "summary": "The paper considers reinforcement learning for infinite-horizon average-reward MDPs under function approximation, and (i) generalizes the concept of eluder dimension to average-reward MDPs as a complexity measure, and (ii) proposes a new algorithm named FLOP to solve average-reward MDPs with low complexity in the sense of the generalized eluder dimension defined in the paper.", "questions": "In addition to the clarification of the definition of AGEC, I have the following questions:\n- The function approximation error can be critical in RL, as its multiplying factor usually depends on the exploration performance in various forms. If we remove the realizability assumption, how does the additional term depend on the complexity measure defined in this paper?\n- In Equation 2.1, what is $V^*(s,a)$? Should it be $Q^*$?\n- In the abstract and in multiple places in the paper, $sp(v^*)$ appears with $v^*$. Should it be $sp(V^*)$? In the paper, it is assumed that $sp(V^*)$ is known. Is this knowledge necessary?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "The problem addresses the challenging problem of infinite-horizon, average-reward MDPs in the function approximation setting. The idea of extending eluder dimension to this class of MDPs is a good idea. Also, the proposed algorithm that achieves sublinear regret seems to be a promising extension of the fitted Q-iteration algorithm, which takes lazy policy change into account.", "weaknesses": "The definition of AGEC (Definition 3), which is the central object and contribution in this paper, lacks clarity:\n- Big-O notation is used in the definition, where the defined quantities $d_G$ and $\\kappa_G$ (which also appear in $\\mathcal{O}$) are smallest numbers that satisfy the inequalities that involve $\\mathcal{O}$. This does not make much sense as a mathematical definition, with $\\mathcal{O}$ being asymptotic.\n- The set of discrepancy functions $\\{l_f\\}_f$ abruptly appears in Definition 3 without any proper definition. In later sections, we observe that it is an important quantity.\nI would suggest a clear, mathematical definition of the complexity measure that constitutes one of the major contributions of this paper.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "DOTUMXrkKw", "reviewer": "Reviewer_jdKK", "summary": "This paper studies sample efficiency in infinite-horizon averaged MDP setting with general function approximation.\nThe authors propose average-reward generalized eluder coefficient to characterize the exploration difficulty in learning, and contribute an algorithm called Fixed-Point Local Optimization and establish sublinear regret with polynomial dependence on AGEC coefficient and span of optimal state bias, etc.", "questions": "* What are the novelties in technical or algorithmic level in this paper? What are the new challenges for exploration in infinite horizon averaged reward setting?\n\n* Is the \"lazy policy update\" really necessary? Although the authors explain the motivation for low policy switching is because of the additional cost in regret analysis. I'm curious whether it can be avoidable or it reveals some fundamental difficulty.\n\n* In Theorem 3, the definition of $\\beta$, is $sp(v^*)$ inside or outside of the log?\n\n* Why the algorithm is called \"Fixed-Point ...\"? I'm not very understand why Eq. 4.1 is a fixed-point optimization problem.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The paper writing is clear. The notations, definitions are clearly stated. Comparison with previous works are also clearly summarized in Table 1.", "weaknesses": "1. It seems to me the main contribution of this paper is to transfer and generalize some existing techniques and results (especially in finite horizon setting) to infinite horizon averaged return setting. The definition of AGEC Complexity Measure, FLOP algorithm and the techniques for analyzing lazy update rules seem share much similarity with previous literature like [1], [2]. I didn't find much novelty in algorithm design or technique analysis.\n\n2. There is no conclusion section. I would suggest the authors at least have a few works to summarize the paper and discuss the future works. \n\n\n[1] Zhong et. al., Gec: A unified framework for interactive decision making in mdp, pomdp, and beyond\n\n[2] Xiong et. al., A general framework for sequential decision- making under adaptivity constraints\n\n\n## Post Rebuttal \n\nThanks for the detailed reply. I think my main concerns are addressed, and I'm willing to increase my score.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (poster)