Unified Algorithms for RL with Decision-Estimation Coefficients: No-Regret, PAC, and Reward-Free Learning
Authors: Fan Chen
Song Mei
Yu Bai
Venue: Submitted to ICLR 2023 (2023)
Keywords: reinforcement learning theory
decision-estimation coefficient
function approximation

Abstract: Finding unified complexity measures and algorithms for sample-efficient learning is a central topic of research in reinforcement learning (RL). The Decision-Estimation Coefficient (DEC) is recently proposed by Foster et al. (2021) as a necessary and sufficient complexity measure for sample-efficient no-regret RL. This paper makes progress towards a unified theory for RL with the DEC framework. First, we propose two new DEC-type complexity measures: Explorative DEC (EDEC), and Reward-Free DEC (RFDEC). We show that they are necessary and sufficient for sample-efficient PAC learning and reward-free learning, thereby extending the original DEC which only captures no-regret learning. Next, we design new unified sample-efficient algorithms for all three learning goals. Our algorithms instantiate variants of the Estimation-To-Decisions (E2D) meta-algorithm with a strong and general model estimation subroutine. Even in the no-regret setting, our algorithm \textsc{E2D-TA} improves upon the algorithms of Foster et al. (2021) which require either bounding a variant of the DEC which may be prohibitively large, or designing problem-specific estimation subroutines. As applications, we recover existing and obtain new sample-efficient learning results for a wide range of tractable RL problems using essentially a single algorithm. Finally, as a connection, we re-analyze two existing optimistic model-based algorithms based on Posterior Sampling or Maximum Likelihood Estimation, showing that they enjoy similar regret bounds as \textsc{E2D-TA} under similar structural conditions as the DEC.

Under review as a conference paper at ICLR 2023
UNIFIED ALGORITHMS FOR RL WITH DECISION- ESTIMATION COEFFICIENTS: NO-REGRET, PAC, AND REWARD-FREE LEARNING
Anonymous authors Paper under double-bling review
ABSTRACT
Finding unified complexity measures and algorithms for sample-efficient learn- ing is a central topic of research in reinforcement learning (RL). The Decision- Estimation Coefficient (DEC) is recently proposed by Foster et al. (2021) a governing complexity measure for sample-efficient no-regret RL. This paper makes progress towards unified theory for RL with the DEC framework. First, we propose two new DEC-type complexity measures: Explorative DEC (EDEC), and Reward-Free DEC (RFDEC). We show that they necessary and sufficient for sample-efficient PAC learning and reward-free learning, thereby extending the original DEC which only captures no-regret learning. Next, we design new unified sample-efficies algorithms for all three learning goals. Our algorithms instantiate variants of the Estimation To-Decisions (E2D) meta- veta-algorithm with strong and general model estimation subroutine. Even in the no-regret setting, our algorithm E2D-TA improves upon the algorithms of Foster et al. (2021) which require ei- ther bounding variant of the DEC which may be prohibitively large, or designing problem- speenn--peiffcceeeee estimation subroutines. As applications, we recover existing and obtain sample-efficient learning results for wide range of tractable RL prob- lems using essentially a single algorithm. Finally, as a connection, we re-analyze existing optimistic model-based algorithms based Posterior Sampling Maximum Likelihood Estimation, showing that they enjoy similar regret bounds E2D-TA under similar structural conditions the DEC.
INTRODUCTION
Reinforcement Learning (RL) has achieved immense success in modern artificial intelligence. As RL agents typically require an enormous number of samples to train in practice (Mnih et al., 2015; Silver et al., 2016), sample-eficiency has been an important question in RL research. This question has been studied extensively many concrete RL problems starting with tabular Markov Decision Processes (MDPs) (Brafman & Tennenholtz, 2002; Azar et al., 2017; Agrawal & Jia, 2017; Jin al., 2018; Dann al., 2019; Zhang et al., 2020b), and later MDPs with various types of linear structures (Yang & Wang, 2019; Jin et al., 2020b; Zanette et al., 2020b; Ayoub al., 2020; Zhou al., 2021: Wang al., 2021).
theory, with provably
algorithms established for
more unifying theory, recent line of work seeks general structural conditions and uni- fied algorithms that encompass many possible known sample-efficient RL problems. Many such structural conditions have been identified, such as Bellman rank (Jiang et al., 2017), Witness rank (Sun al., 2019), Eluder dimension (Russo & Van Roy, 2013; Wang et al., 2020b). Bilinear Class (Du et al., 2019), and Bellman-Elude dimension (Jin et al., 2021). The recent work of Fos- Coefficient (DEC) as a quantitative complexity
Towards a
ter et al. (2021) proposes the measure that governs the statistical complexity of model-based RL with model class. Roughly speaking, the DEC measures the optimal trade-eff-achieeed by any policy-between exploration (gaining information) and exploitation (being near-optimal policy itself) when the true model could be any model within the model class. Foster et al. (2021) ) establish regret lower bounds for online RL in terms of the DEC, and upper bounds in terms of (a variant of) the DEC and model class capacity, showing that the DEC is necessary and (in the above sense) sufficient for online RL with low regret. This constitutes significant step towards unified understanding of sample-efficient RL.

---

Under review as a conference paper at ICLR 2023
Despite this progress, several important questions remain open within the DEC framework. First, in Foster et al. (2021), regret upper bounds for low-DEC problems are achieved by the Estimation- To-Decisions (E2D) meeta-agoorihm, which requires subroutine for online model estimation given past observations. However, their instantiations of this algorithm either (1) use a general improper' estimation subroutine that works black-box for any model class, but results in regret bound that scales with a (potentially significantly) larger variant of the DEC that does not admit known polyno- mial bounds, or (2) require a proper estimation subroutine, which typically requires problem-specifie designs and unclear how to construct for general model classes. These additional bottlenecks pre- vent their instantiations from being unified sample-efficient algorithm for any low-DEC problem. Second, while the DEC captures the complexity of no-regret learning, there are alternative learn- ing goals that are widely studied in the RL. literature such as PAC learning (Dann et al., 2017) and reward-free learning (Jin et al., 2020a), and it is unclear whether they can be characterized using a similar framework. Finally, several other optimistic model- basee algorithms such as Optimistic Posterior Sampling (Zhang, 2022; Agarwal & Zhang, 2022a) or Optimistic Maximum Likelihood Estimation (Mete et al., 2021; Liu et al., 2022a;b) have been proposed in recent work, whereas the optimism in its algorithm design. It is unclear whether E2D
E2D algorithm does not explicitly actually bears any similarities or connections to the aformentioned optimistic algorithms.
In this paper, resolve the above open questions positively by developing new complexity mea- sures and unified algorithms for RL. with Fesisiion Coefficients. Our contributions can be summarized as follows.
We design E2D-TA, the first unified algorithm that achieves low regret for any problem with bounded DEC and low-capacity model class (Section 3). E2D-TA instantiates the E2D meta- algorithm with Tempered Aggregation, a general improper online estimation subroutine that achieves stronger guarantees than variants used in existing work.
We establish connections between E2D-TA and two existing model-based algorithms: Opti- mistic Model-Basee Posterior Sampling, and Optimistic Mokimum--Likllhoon Estimation. We show that these two algorithms enjoy similar regret bounds as E2D-TA under similar structural conditions the DEC (Appendix E).
We extend the DEC framework to two new learning goals: PAC learning and reward-free learn- ing. We define variants of the DEC, which we term as Explorative DEC (EDEC) and Reward- Free DEC (RFDEC), and show that they give upper and lower bounds for sample-efficiee learning in the two settings respectively (Section 4).
We instantiate our results give sample complexity guarantees for the broad problem class of RL with low-complexity Bellman representations. Our results recover many existing and yield new guarantees when specialized to concrete RL problems (Section 5).
Our work is closely related to the long lines of work on sample-efficient RL (both no-regret/PAC and reward-free), and problems/algorithms in general interactive decision making. We review these related work in Appendix A due to the space limit.
Related work
2 PRELIMINARIES
RL as Decision Making with Structured Observations We adopt the general framework of De- cision Making with Structured Observations (DMSO) (Foster al., 2021), which captures broad classes of problems such as bandits and reinforcement learning.
In DMSO, the environment is described by model M (PM, RM), where PM specifies the distribution of the observation o E O, and a² specifies the conditional means? of the reward vector r re [0, 1j where H is the horizon length. The learner interacts with a model using policy II. Upon executing ı in M, they observe an (observation, reward) tuple (o, M(T) as follows:
1. The learner first observes an observation o PM (T) (also denoted as P.M E A(O)).
2. Then, the learner receives (random) reward vector r (rx) with conditional mean RM (o)) ( [0, 1] and independent entries conditioned a.
Which outputs in general a distribution of models within class rather than a single model.
Note that RM (and thus M) only specifies the conditional mean rewards instead of the reward distributions.
2

---

Under review as a conference paper at ICLR 2023
Let fM (T) MM
2 ra] denote the value (expected cumulative reward) of under M, and let TM arg max f (TT) and fM (TM) denote the optimal policy and optimal value for M, respectively.
In this paper, we focus RL in episodic Markov Decision Processes (MDPs) using the DMSO framework. An MDP M = (H, S, A, PM, ,rM) can be cast as a DMSO problem as follows. The observation = ($1, 01..........................00.. ... SH aH) is the full state-action trajectory (so that the observation space is O = (S x A) Upon executing policy π { S - A(A) he in M, the learner observes (51, 15,,1... ..... SH, aH) P. (x)) which sequentially samples s (+), On. ( and 8h+1 Ph. (-18h, (,) for all E [H]. The learner then receives a reward vector r = (Tr (re)ee[m) [0,1] where Th = (s ) is the (possibly random) instantaneous reward for the h-th step with conditional mean [M[ro = R =: R (sn, ax)) depending only on (8), a4)). We assume that Σ R (sh, an) [0, 1] for all M and all o O.
Learning goals We consider the online learning setting, where the learner interacts with a fixed (unknown) ground truth model M for T episodes. Let n' E II denote the policy executed within the f-th episode. In general, x' may be sampled by the learner from distribution p' e A A(II) before the f-th episode starts, One main learning goal in this paper is minimize the standard notion of regret that measures the cumulative suboptimality of { retr:
T RegDM Σ
Ept (MT-)) - (x'} (x))
To achieve low regret, this paper focuses on model-based approaches, where we are given a model class M. and we assume realizability: M E M. Additionally, throughout the majority of the paper. we assume that the model class is finite: [M] do (or (P] < 3o for the reward-fre tweerd-fee set- ting in Section 4.2) for simplicity of the presentation; both can be relaxed using standard covering arguments (see e.g. Appendix D.2), which we do when we instantiate our results to concrete RI. problems in Example 13-15.
2.1 DEC WITH RANDOMIZED REFERENCE MODELS
The Dacision-Estimattin Coefficient (DEC) is proposed by Foster et al. (2021) as key quantity characterizing the statistical complexity of sequential decision making. We consider the following definition of DEC with randomized reference models (henceforth "DEC"":
Definition (DEC with randomized reference models). The DEC of M with respect to distribution E ((M) (with policy class II and parameter 7 > 0) is defined as
dec.((M..)) : inf sup Ex-PEM-LI [ (TM) fMl (T) (M(()
pEA(II) MEM
Further define (M) SUPpEA(M) doc, (M. Above, Drr. is the following squared diver- gence function
Da (M()), M M(T)) D (P. (T)) MM (x)) Par (x) [I - (2))))
(1)
where (IP, := S(V dP/du < dd) dy denotes the standard Hellinger distance between probability distributions P, Q.
Definition instantiates the general definition of DECs in Foster et al. (2021, Section 4.3) with divergence function chosen as DR The quantity (M,, measures the optimal trade-off of policy distribution p A(II) between two terms: low suboptimality fM (TT) - f (Tr) and high information gain Pu..(M (MT)), M(T)) with respect to the randomized reference model M ~ n.
The main feature of Di is that it treats the estimation of observations and rewards separately: It requires the observation distribution to be estimated accurately in Hellinger distance between the full distributions, but the reward only accurately in the squared Le error between the conditional means. Such a treatment is particularly suitable for RL problems, where estimating mean rewards is easier than estimating full reward distributions and is also sufficient in most scenarios.
Foster al. (2021) mostly use the standard Hellinger distance (in the tuple r), in their definition of the DEC, which cares about full reward distributions (ef. Appendix C. 1.1 for detailed discussions).
3

---

Under review as a conference paper at ICLR 2023
Algorithm E2D-TA: ESTIMATTIN-TT-DEEIIIII WITH TEMPERED AGGREGATION
Input: Parameter y 0: Learning rate 7/p E (0, (), n 0.
Initialize n² < Un)
2: for .,... do
3: Set arg min ((1I)) = (4 (p), where Vu is defined in (2).
4: Sample x' p². Execute n² and observe r²).
5: Update randomized model estimator by Tempered Aggregation:
(M) a.M (M) exp (1p log Tog (o') 1 pelr'- R - (o))))
E2D WITH TEMPERED AGGREGATION
We begin by presenting algorithm Estimationntt-Deccisi with Tempered Aggregation (E2D- TA; Algorithm 1), a unified sample-efficient algorithm for any problem with bounded DEC.
each episode Algorithm maintains randomized model estimator μ² (MM), and uses it to obtain distribution of policies p² E AIII by minimizing the following risk function (cf. Line 3):
Algorithm description
Vi (p) sup
(M) (M)
MEM
This risk function instantiates the E2D meta-algorithm with randomized estimators (Foster et al., 2021, Algorithm 3) with divergence DRL The algorithm then samples policy x" ~ p', executes r',and and observes (o',r") from the environment (Line 4).
Core to our algorithm is the subroutine for updating our randomized model estimator μ²: Inspired by Agarwal & Zhang (2022a), we use a Tempered Aggregation subroutine that performs expo- nential weights update on μ² (M) using linear combination of the log logeliiel log IP M,' (o') for the observation, and the negative squared L2 loss - |r' - M (o')l for the reward (cf. Line 5). -R.
An important feature of this subroutine is the learning rate "hp & 1/2, which is smaller compared e.g. Vovk's aggregating algorithm (Vovk, 1995) which uses Vp 1. As will shortly, this difference is crucial and allows a stronger estimation guarantee that is suitable for our purpose.
with 7pp & 1/2 equivalent to computing the tempered posterior a Bayesian setting (Bhattacharya et al., 2019; Alquier & Ridgway, 2020) (hence our name "tempered"), whereas 1/p 1 computes the exact posterior (see Appendix C.2 a derivation).
As an intuition, exponential weights with ехр(пp log P.M,** (o')) = (PM,."
We are now ready to present the main theoretical guarantee for Algorithm 1.
Theorem (E2D with Tempered Aggregation). Choosing Tpp = 1 = 1/3, Algorithm achieves the following with probability at least -- 8:
RegDM Tdec, 10y log(lM))/8)
By choosing the optimal 7 >> O, we get RegDM = infyso [Tdec, + log)) which scales log if the model class satisfies dec,(M) d/r for complexity mea- sure d. To our best knowledge, this the first unified sample-efficien algorithm for general prob- lems with low DEC, and resolves subtle but important technical challenge in Foster al. (2021) which prevented them from obtaining such a unified algorithm.
Concretely, Foster al. (2021, Theorem 3.3 & 4.1) show that E2D with Vovk's aggregating algo- rithm as the estimation subroutine achieves the following regret bound with high probability:
sUPMeco(M) dec,, 8 + O(y log((()))))))
where 85z denotes point mass at M, and co(M) denotes the set all possible mixtures of models in M. Unfortunately, this mixture causes SUPTeco((M) dec, (M; 857) to be potentially intractable for
4

---

Under review as a conference paper at ICLR 2023
most RL problems Even when MM=(tabular MDPs), known bounds of the form poly(H, S, A, 1/7). Our Theorem 2 removes this bottleneck and only scales with (Mc,, which is much milder and admits tractable bounds for most known tractable RI. problems (Section 5); For example, dec,(M) & A// for tabular MDPs (Appendix K.3.1). See Appendix C.I for additional details on the comparison between these two DECs.
(ec; does not admit
Proof overview The proof of Theorem 2 (deferred to Appendix D.2) builds upon the analysis of E2D meta-algorithms (Foster et al., 2021). The main new ingredient in the proof is the following online estimation guarantee for the Tempered Aggregation subroutine (proof in Appendix D.1).
Lemma 3 (Online estimation guarantee for Tempered Aggregation), Subroutine (3) with 4mp + 7)
2 achieves the following bound with probability at least
EstRI. := Σ
Ent E -pt -p² (T') & &C. C. log(l-M)/8),
(4)
[=1
where C depends only on (7pp; Specifically, we can choose 1pp 7/- 1/3 and C 10.
Bound (4) is stronger than the estimation bound for Vovk's aggregating algorithm (e.g. Foster et al. (2021, Lemma A.1 adapted to Dh which only achieves
T
Σ
Byt wp Dea (M"("'), E E mnd (+)))) & C. (log((MMM/)),
(5)
where 1p
M (T') denotes the mixture model of M(')) where M7 n². Note that (4) is
stronger than (5) by convexity of DR. in the second argument and Jensen's 's inequality. Therefore, while both algorithms yield randomized model estimates, the guarantee of Tempered Aggregation is stronger, which in turn allows our regret bound in Theorem scale with a smaller DEC.
Connections to other optimistic algorithms In Appendix E, we re-analyze two existing opti- mistic algorithms: Model-based Optimistic Posterior Sampling (MOPS), and Optimistic Maximum Likelihood Estimation (OMLE). These algorithms are similar to E2D-TA due to their use of poste- riors/iikelhoods, and we show that they achieve regret bounds similar as E2D-TA under structural conditions similar the DEC, thereby establishing a connection between these three algorithms.
4 PAC LEARNING AND REWARD-FREE LEARNING
We now extend the DEC framework to two alternative learning goals in RL beyond no-regret: PAC learning, and reward-free learning. We propose new generalized definitions of the DEC and show that they upper and lower bound the sample complexity in both settings.
4.1 PAC LEARNING VIA EXPLORATIVE DEC
In PAC learning, we only require the learner to output a near-optimal policy after T episodes are finished, and does not require the executed policies ( (the "exploration policies") to be high- standard result that any no-regret algorithm can be converted into PAC algorithm by the online-to-boee
T
quality. to-teecttthhhhhhhheee conversion (e.g. Jin et al. (2018)), so that the DEC (and the corresponding
E2D-TA algorithm) gives upper bounds for PAC learning as well. However, for certain problems, there may exist PAC algorithms that are better than converted no-regret algorithms, for which the DEC would not tightly capture the complexity of PAC learning.
To better capture PAC learning, we define the following Explorative DEC (EDEC); Definition 4 (Explorative DEC). The Explorative Decision--stimatiin Coefficient (EDEC) of model-class M with respect to Jı ((M) and parameter y > 0 is defined as
edec, (M,
inf sup Em-ponn [f - fM (x)) - 7E x~ Peep M- Dh. (()))
Peop (A(M) MEM P
Further, define edec (M) sUPReA(M)) edec, n.)
5

---

Under review as a conference paper at ICLR 2023
The main difference between the EDEC and the DEC (Definition 1) is that the inf is taken two different policy distributions Pexp and Pout, where Pexp (the "exploration policy distribution") appears in the information gain term, and Pout (the "output policy distribution") appears in the suboptimality term. In comparison, the DEC restricts the policy distribution to be the same both terms. This accurately reflects the difference between PAC learning and no-regret learning, where in PAC learning the exploration policies are not required to be the same as the final output policy.
Algorithm and theoretical guarantee The EDEC naturally leads to the following EXPLORATIVE E2D algorithm for PAC learning, Define risk function Vu pac,y
A(II) A(II)
E.
V.l pac,y (Pexps Pout) == sup Eg Pame [MM((M)) - fM (=)] -yB ppopp. Mi MeM
(M
(6)
Our algorithm (full description in Algorithm 7) is similar as E2D-TA (Algorithm 1), except that in each iteration, find (Poep Pont) that jointly minimizes p (---) (Line 3), execute x' peep to >.T collect data, and return Pout T 2 Pout as the output policy after T episodes.
Theorem 5 (PAC learning with EXPLORATIVE E2D). Choosing 1pp T) 1/3, Algorithu achieves the following PAC guarantee with probability at least 1 - ò:
log(LM)/0)
SubOpt :- fM (TTM-) - E [fat (T)) & edec,(M) 10
T
The proof can be found in Appendix H.1. For problems with edec, (M) x (d/7), Theorem 5
achieves SubOpt & Ö (Vdlog MM/T] (by tuning 7), which implies an Ô (dlog M /e²) sam- ple complexity for learning an e near-optimal policy.
In the literature, PAC RL algorithms with exploration policies different from output policies have been designed for various problems, e.g. Jiang et al. (2017); Du et al. (2021); Liu et al. (2022a). These algorithms typically design their exploration policies manually (e.g. concatenating the output policy with a uniform policy over time step fi) using prior knowledge about the problem. By contrast, EXPLORATIVE E2D does not require such knowledge and automatically learns the best exploration policy Pexp E (II) by minimizing (6), thus substantially simplifying the algorithm design.
Lower bound We show that suitably localized version of the EDEC gives information- theoretic lower bound for PAC learning. The form of this lower bound is similar as the regret lower bound in terms of the (localized) DEC (Foster al., 2021). For any model class M and M M, define shorthand edec, (M, M) := edec,, 8M)) where 6 denotes the point mass at M. Proposition 6 (Lower bound for PAC learning: Informal version of Proposition H.2). For any model class M, T E Eol, and any algorithm 2, there exists M E -M such that
E M" A SubOpt]
> max sup cdc,, (M), 7>0 MEM
where co > 0 is an absolute constant, and M (M) denotes a certain localized subset of M around M with radius E = 7/T (formal definition in (45)).
The upper and lower bounds in Theorem 5 and Proposition 6 together show that the EDEC governs the complexity of PAC learning, similar as the DEC for no-regret learning (Foster et al., 2021).
Proposition 6 can be used to establish PAC lower bounds for concrete problems: For example, for tabular MDPs, we show in Proposition H.3 that supMEM edec,(M (M), M) ス min HSA// as long as ~ H HA/4%, which when plugged into Proposition 6 recovers the known 22( HSA/T) PAC lower bound for tabular MDPs with Σn T E [O, 1] (Domingues et al., 2021). This implies (and is slightly stronger than) the Q(v (HS) regret lower bound for the same problem implied by the DEC (Foster et al., 2021, Section 5.2.4), no-regret is at least hard PAC learning.
Relationship between DEC and EDEC As the definition of EDEC takes the infimum over a larger set than the DEC, we directly have edec, ( & dMc, 7 for any M and şz A(M). The following shows that the converse also holds in an approximate sense (proof in Appendix H.3).

---

Under review as a conference paper at ICLR 2023
Proposition 7 (Relationship between DEC and EDEC). For any (a,7) E (0, Rsu and p A(M), we have dec, (M, [i) $ a (1 - a)
Pi). and thus
(M) dec
inf (a + (1 -a a>0
Bound (i) asserts that, any problem with bounded DEC enjoys the same bound on the EDEC, on which EXPLORATIVE E2D achieves sample complexity no worse than that of E2D-TA (Theorem & Theorem 2). On the other hand, the converse bound (ii) is in general lossy conversion- For class with low EDEC, the implied DEC bound yields slightly worse rate, similar the standard explore-then-oomme conversion from PAC to no-regret (cf. Appendix H.3.1 for detailed discus- sions). Indeed, there exist problems for which the current best sample complexity through no-regret learning and bounding the DEC Ö (1/e²): whereas PAC learning through bounding the EDEC gives tighter Ô (1/6²) (ef. Proposition 12 and the discussions thereafter).
4.2 REWARD-FREE LEARNING VIA REWARD-FREE DEC
In reward-free RL (Jin et al., 2020a), the goal is to optimally explore the environment without ob- serving reward information, so that after the exploration phase, a near-optimal policy any given reward can be computed using the collected trajectory data alone without further interacting with the environment.
We define the following Reward-Free DEC (RFDEC) to capture the complexity of reward free learn- ing. Let R. denote a set of mean reward functions, P denote a set of transition dynamics, and M := P x R denote the class of all possible models specified by M RP P R. We assume the true transition dynamics P* E P.
Coefficient (RFDEC) of model class M = P x R with respect to p (PP) and parameter ny > O) is defined as
Definition 8 (Reward-Free DEC). The Reward-Free
rfdec,(,, =
inf sup inf sup (TT) RER Pou ((T) PEP
Ex- [sP.R(TP.R) (P.
BBe E [P(()
Further, define (Mde,,,MM suppea(P) (M.
The RFDEC can be viewed as modification of the EDEC, where we further insert SuPSER to reflect that we care about the complexity of learning any reward R E R, and use D (P(T). P(T)) as the divergence reflect that we observe the state-action trajectories of only and the reward.
Algorithm and theoretical guarantee Our algorithm REWARD-FREE E2D (full description in Algorithm 8) is an adaptation EXPLORATIVE E2D to the reward-free setting, and works two phases. In the exploration phase, we find pixp A(II) minimizing the sup-risk supReR Vil, (, R) in the i-th episode, where
Du 1f, 1f,,y (Pexp: R) := inf sup E. Ex- (P, (P. E. Peap Epr-ppe PP(
Pour PEP
Then, in the planning phase, for any given reward R' E R, we compute P'm (R*) as the argmin of the inf inf in Vi,, (P'sps R²), and output the average policy (omr(R") + ΣT (Rt). Theorem (Reward- Free E2D). Algorithm achieves the following with probability at least - 5:
SubOpt,r == sup { [P"". (TTP*RR)) - EE -En-Rone(tt) p (m) (P'.,((m)))
< rfdec,(M) +
3 log (P] / T
RE
The proof can be found in Appendix 1.2. For problems with rfdec, (M) Ô (d/7), by tuning 7 > Theorem achieves SubOpt, & E within Ō (dlog (P|/=?) episodes play. The only known such general guarantee for reward-free RI. is the recently proposed RFOlive algorithm of Chen et al.
7

---

Under review as a conference paper at ICLR 2023
(2022) which achieves sample complexity Ö (poly(H) dHrr log(( in the model-free setting" Theorem can be seen generalization of this result to the model-based setting, with more general form of structural condition (RFDEC). Further, our guarantee does not further depend on the statistical complexity (e.g. log-cardinality) of R once we assume bounded RFDEC.
Lower bound Similar as EDEC for PAC learning, the RFEC also gives the following lower bound P, define shorthand r.dec,,M,, P) :=
for reward-free learning. For any M = P x RR and rfdec,, 6p) where Öp denotes the point mass at P.
Proposition 10 (Reward-free lower bound; Informal version of Proposition 1.2). For any model class M = P x R, T Z3,,, and any algorithm 2, there exists a P* e P such that
TEP". (SubOpt,r] > co max sup rfue,, (M 20 (P), 7=0 PeP
where co is absolute constant, and M (M) denotes certain localized subset of M around M with radius Ex T/T (formal definition in (50)).
5 INSTANTIATION: RL WITH BELLMAN REPRESENTABILITY
In this section, we instantiate our theories to bound the three DEC variants and give unified sample- efficient algorithms for a broad class of problems RL with low-complexity Bellman Representa- tions (Foster et al., 2021). Consequently, our algorithms recover existing and obtain new sample complexity results on wide range of concrete RL problems.
Definition 11 (Bellman Representation). The Bellman representation of (M, M) is collection of
function classes (9 := {9h M.M :M - [-1, 1))) such that:
(a) For all M M, MMN (2 (sh, an)
M. h+1
(sn+1)
< 9h MMMM
M-M (M)
(b) There exists a family of estimation policies (Tr MeM, and a constant L 3 1 such that (MD) & L DRL (M M M((m()))
for all M,M' M' e .M, M
MM
9h.
We say M satisfies Bellman representability with Bellman representation G := (g MEM.helH if
(M, M) admits Bellman representation (g )hefzn) for all M MM.
is shown Foster al. (2021) that problems admitting a low-complexity Bellman representation G (e.g. linear or low Eluder dimension) include tractable subclasses such as (model-based versions of) Bilinear classes (Du et al., 2021) and Bellman-Eluder dimension (Jin al., 2021). We show that Bellman representability with low complexity G implies bounded DEC/EDEC/RFDEC, which in turn leads to concrete rates using our E2D algorithms in Section and
Proposition 12 (Rates for RL with low-complexity Bellman representationss. Suppose . admits Bellman representation G with low complexity: min A), s A) & Ö (d) for all (h, M) [H] M, where is the Eluder dimension, is the star number (Definition K.3 & K.4), > 0 and Ö (-) contains possibly polylog(1/ A) factors. Then we have
(1) (No-regret learning) If MMM = TM for all M M (the on-policy case), then dec, & δ Ld1)) and Algorithm E2D-TA achieves RegDM & Õ(HLL / d' log log]M).
(2) (PAC learning) For any general ( M we have odec,(MM & xÖ (2H) and Algorithm EXPLORATIVE E2D achieves SubOpt within Ö (dI log M /8²) episodes of play.
(3) (Reward-free learning) If G is a Bellman representation in a stronger sense (ef. Defini- tion K.8), then rideo, (M) Ö (dHH2 and Algorithm REWARD-FREE E2D achieves SubOpt, & E within Ö 2 log (Pl episodes of play.
'Where F denotes the value class, and R denotes the reward class, and dBg denotes the Fallden-Flludr dimension certain class of reward-free Bellman errors induced by F.
8

---

Under review as a conference paper at ICLR 2023
The proof can be found in Appendix K.2. To our best knowledge, results (2)() above are the first such results with DEC-type structural assumptions. In particular, when the estimation policies are general, the θ (1/e²) PAC sample complexity in (2) through bounded EDEC improves over Foster al. (2021, Theorem 7.1 & F.2) which uses the conversion to DEC and results in an Ô (1/e2) sample complexity. The no-regret result in (1) also improves over the result of Foster et al. (2021) as a unified algorithm without requiring proper online estimation oracles which is often problem- specific. We remark that a similar bound as (1) also holds for psc. (c.f. Definition E.1), and for
mlec., (c.f. Definition E.4) assuming bounded Eluder dimension e( A) & (de), and thus MOPS and OMLE algorithms achieve similar regret bounds as E2D-TA (cf. Appendix K.1).
Examples Proposition 12 can be specialized to a wide range of concrete RL problems, for which give a few illustrating examples here (problem definitions and proofs in Appendix K.3). We em- phasize that, except for feeding the different model class M's into the Tempered Aggregation sub- routines, the rates below (for each learning goal) are obtained through a single unified algorithm without further problem-dependent designs.
Example 13. For tabular MDPs, E2D-TA achieves regret RegDM & Ô (VS3ARHTT) and
REWARD- FREE E2D achieves reward-fres free guarantee SubOpt,r & Ō (VS 0
Both rates are worse then the optimal HSAT) regret bound (Azar al., 2017)$ and Ö(v (oly(HH)s reward-free bound (Jin et al., 2020a). However, our rates are obtained through unified algorithms that is completely agnostic to the tabular structure.
Example 14. For linear mixture MDPs (Ayoub et al., 2020) with a d-dimensional feature map, E2D-TA achieves regret RegDM & Ö (VdHH*)) and REWARD-FREE E2D achieves reward-
free guarantee SubOpter Ö (VT-H1IT).
The later result implies a sample complexity of Ô (d2 for E-near optimal reward-free learn- ing in linear mixture MDPs, which only has an additional H² factor over the current best sample complexity Ô (d&H/e²) of Chen et al. (2021)².
Example 15. For low-rank MDPs with unknown d-dimensional features (d), 1b) E $ x V (i.e. the FLAMBE setting (Agarwal et al., 2020)), A actions, and rewards R E R. EXPLORATIVE E2D achieves PAC guarantee SubOpt & Ō (ddAH= log( $ | [R])/T and E2D-RF achieves
reward-free guarantee SubOpt,r < Ö @OVVAHH log( + W)/T). +
Our PAC result matches the best known sample complexity achieved by e.g. the V-Type Golf Al- gorithm of Jin et al. (2021). For reward-free learning, our linear in d dependence improves over the current best d2 dependence achieved by the RFOlive algorithm (Chen al., 2022), and we do not require linearity or low complexity assumptions on the class of reward functions R made in existing work (Wang al., 2020a; Chen et al., 2022). However, we remark that they handle a slightly more general setting where only the & class is known, due to their model-free approach.
An important subclass of low-rank MDPs is Block MDPs (Du et al., 2019). In (stationary- transition) Block MDPs with O states, A actions, and S latent states, REWARD-FREE E2D achieves SubOpt,, & δ (V(SOA+ + A²22) which improves over the result of Jedra et al. (2022) in the S dependence, and does require a certain reachability assumption made in their result.
6 CONCLUSION
This paper proposes unified sample-efficient algorithms for no-regret, PAC, and reward-free rein- forcement learning, by developing new complexity measures and stronger algorithms within the DEC framework. We believe our work opens up many important questions, such as developing model-free analogs of this framework, extending to other learning goals (such multi-agent RL), and computational efficiency of our algorithms.
Rescaled to total reward within [0, 1].

---

Under review as a conference paper at ICLR 2023
REFERENCES
Yasin Abbasi- Yadkori and Gergely Neu. Online learning in mdps with side information. arXiv preprint arXiv: (eoe::406..1111 6812, 2014.
Alckh Agarwal and Tong Zhang. Model-based rl with optimistic posterior sampling: Structural conditions and sample complexity. arXiv preprint arXiv:2206.00 220,022006.06659, 2022a.
Alekh Agarwal and Tong Zhang. Non-linear reinforcement learning in large action spaces: Struc- tural conditions and sample-effciiency of posterior sampling. arXiv preprint arXiv:2203.08245 2022b.
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.
Alckh Agarwal, Sham Kakade, Akshay Krishnamurthy, and Wen Sun. Flambe: Structural com- plexity and representation learning of low rank mdps. Advances in neural information processing systems, 33:20095-22222 20107,, 2020.
Shipra Agrawal and Randy Jia. Optimistic posterior sampling for reinforcement learning: worst- case regret bounds. Advances in Neural Information Processing Systems, 30, 2017.
Pierre Alquier and James Ridgway. Concentration of tempered posteriors and of their variational approximations. The Annals of Statistics, 48(3):1475-149,, 2020.
Peter Auer, Nicolo Cesa-Bianchi, Yoav Freund, and Robert E Schapire. The nonstochastic multi- armed bandit problem. SIAM journal on computing, 32(1):48-77, 2002.
Peter Auer, Ronald Ortner, and Csaba Szepesvári. Improved rates for the stochastic continuum- armed bandit problem. In International Conference on Computational Learning Theory, pp- 454-468. Springer, 2007.
Alex Ayoub, Zeyu Jia, 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.
Mohammad Gheshlaghi Azar, Ian Oshand, and Rémi Munos. Minimax regret bounds for reinforce- ment learning. In International Conference Machine Learning, pp. 263-272. PMLR, 2017.
Alina Beygelzimer, John Langford, Lihong Li, Lev Reyzin, and Robert Schapire. Contextual bandit algorithms with supervised learning guarantees. In Proceedings the Fourteenth International Conference on Artificial Intelligence and Statistics, pp. 19-26. JMLR Workshop and Conference Proceedings, 2011.
Anirban Bhattacharya, Debdeep Pati, and Yun Yang. Bayesian fractional posteriors. The Annals of Statistics, 47(1):39-66 66, 2019.
Ronen Brafman and Moshe Tennenholtz. R-max-a general polynomial time algorithm for near- optimal reinforeement learning. Journal of Machine Learning Research, 31022332 2002.
Sébastien Bubeck and Ronen Eldan. Multi-scale exploration of convex functions and bandit convex optimization. In Conference Learning Theory, pp. 583-589. PMLR, 2016.
Sébastien Bubeck, Ofer Dekel, Tomer Koren, and Yuval Peres. Bandit convex optimization sqrrt regret in one dimension. In Conference on Learning Theory, pp. 266-278, PMLR, 2015.
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.
Jinglin Chen, Aditya Modi, Akshay Krishnamurthy, Nan Jiang, and Alekh Agarwal. On the sta- tistical efficiency of reward-free -rree exploration in non-linear rl. arXiv preprint arXiv:2206.1077 2022.
10

---

Under review as a conference paper at ICLR 2023
Xiaoyu Chen, Jiachen Hu, Lin F Yang, and Liwei Wang. Near-optimal reward-free exploration for linear mixture mdps with plug-in solver. arXiv preprint arXiv:2110003244, 2021.
Wei Chu, Lihong Li, Lev Reyzin, and Robert Schapire. Contextual bandits with linear payoff func- tions. In Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics, pp. 208-2144 214. JMLR Workshop and Conference Proceedings, 2011.
Christoph Dann and Emma Brunskill. Sample complexity of episodic fixed-horizon reinforcement learning. Advances Neural Information Processing Systems, 28, 2015.
Christoph Dann, Tor Lattimore, and Emma Brunskill. Unifying pac and regret: Uniform pac bounds for episodic reinforcement learning. Advances in Neural Information Processing Systems, 30, 2017.
Christoph Dann, Lihong Li, Wei Wei, and Emma Brunskill. Policy certificates: Towards account- able reinforcement learning. In International Conference on Machine Learning, pp. 1507-1516. PMLR, 2019.
Omar Darwiche Domingues, Pierre Ménard, Emilie Kaufmann, and Michal Valko. Episodic rein- forcement learning in finite mdps: Minimax lower bounds revisited. Algorithmic Learning Theory, pp. 598. PMLR, 2021.
David I. Donoho and Richard Liu. Geometrizing rates of convergence. Annals of. 1987.
David I. Donoho and Richard C Liu. Geometrizing rates of convergence, ii. The Anmals of Statistics, pp. 633-667, 1991a.
David L Donoho and Richard Liu. Geometrizing rates of convergence, iii. The Annals of Statistics, pp. 668-701, 1991b.
Simon Du, Akshay Krishnamurthy, Nan Jiang, Alekh Agarwal, Miroslav Dudik, and John Langford. Provably efficient rl with rich observations via latent state decoding. In International Conference Machine Learning, pp. 1665-1674. PMLR, 2019.
Simon Du, Sham Kakade, Jason Lee, Shachar Lovett, Gaurav Mahajan, Wen Sun, and Ruosong Wang. Bilinear classes: A structural framework for provable generalization in rl. In International Conference on Machine Learning, pp. 2826-2836. PMLR, 2021.
Simon S. Du, Sham M. Kakade, Ruosong Wang, and Lin F. Yang. Is good representation suf- ficient for sample efficient reinforcement learning? In International Conference on Learning Representations, 2020. URL https:
ptatt:s:///perrvviii http///ppwweeeeeeeeeeeee net www.mmii--iieeeeeeeeeerrrrreeeee ren.vvkK.............m
Dylan Foster and Alexander Rakhlin. Beyond ucb: Optimal and efficient contextual bandits with regression oracles. In International Conference on Machine Learning, pp. 3199-3210. PMLR, 2020.
Dylan Foster, Alexander Rakhlin, David Simchi-Levi, and Yunzong Xu. Instance-dependent complexity of contextual bandits and reinforcement learning: A disagreement-basee perspective. arXiv preprini urXiv:2010.03104, 2020.
Dylan J Foster, Sham M Kakade, Jian Qian, and Alexander Rakhlin. The statistical complexity of interactive decision making. arXiv preprint 12. 13487, 2021.
Dylan J Foster, Alexander Rakhlin, Ayush Sekhari, and Karthik Sridharan. On the complexity of adversarial decision making. arXiv preprint arXiv:2206.13063 2022.
Thomas Jaksch, Ronald Ortner, and Peter Auer. Near-optimal regret bounds for reinforcement learning. Journal of Machine Learning Research, 116$1):1533-1600, 2010. URL http:// jmlr. warrr.org/pppee wttg/papers//eee v1 http///v1/aajsat///e jaaksch1 0a html.
Yassir Jedra, Junghyun Lee, Alexandre Proutière, and Se- Le-Young Yun. Nearly optimal latent state decoding in block mdps arXiv preprint arXiv:2208. 08488, 2022.

---

Under review as a conference paper at ICLR 2023
Nan Jiang, Akshay Krishnamurthy, Alekh Agarwal, John Langford, and Robert E Schapire. Con- textual decision processes with low bellman rank are pac-leamable. International Conference on Machine Learning. pp. 1704-1713. PMLR, 2017.
Chi Jin, Zeyuan Allen-Zhu, Sebastien Bubeck, and Michael Jordan. Is q-learning provably effi- cient? Advances in neural information processing systems, 31, 2018.
Chi Jin, Akshay Krishnamurthy, Max Simchowitz, and Tiancheng Yu. Reward-free exploration for reinforcement learning. In International Conference on Machine Learning, pp. 4870-4879.
PMLR, 2020a.
Chi Jin, Zhuoran Yang, Zhaoran Wang, and Michael Jordan. Provably efficient reinforcement learning with linear function approximation. In Conference on Learning Theory, pp. 2137-2143. PMLR, 2020b.
Chi Jin, Qinghua Liu, and Sobhan Miryoosefi. Bellman eluder dimension: New rich classes of problems, and sample-efficient algorithms. Advances in neural information processing systems, 34:13406-13418, 2021.
Emilie Kaufmann, Pierre Ménard, Omar Darwiche Domingues, Anders Jonsson, Edouard Leurent, and Michal Valko. Adaptive reward-free exploration. In Algorithmic Learning Theory, pp. 865- 891. PMLR, 2021.
Michael Kearns and Satinder Singh. Near-optimal reinforcement learning in polynomial time. Ma- chine learning, 49(2):209-233 2002.
Robert Kleinberg. Nearly tight bounds for the continuum-armed bandit problem. Advances in Neural Information Processing Systems, 17, 2004.
Robert Kleinberg, Aleksandrs Slivkins, and Eli Upfal. Bandits and experts in metric spaces. arXiv preprint arXiv: 1277, 2013.
John Langford and Tong Zhang. The epoch-greedy algorithm for multi-armed bandits with side information. Advances in neural information processing systems, 20, 2007.
Tor Lattimore. Improved regret for zeroth-order adversarial bandit convex optimisation. Mathemat- ical Statistics and Learning, 2(3):311-3) 2020.
Tor Lattimore and Andras Gyorgy. Mirror descent and the information ratio. In Conference on Learning Theory, pp. 2965-2992. PMLR, 2021.
Tor Lattimore and Csaba Szepesvári. Exploration by optimisation in partial monitoring. In Confer- ence on Learning Theory, pp. 2488-2515. PMLR, 2020.
Tor Lattimore, Csaba Szepesvari, and Gellert Weisz. Learning with good feature representations in bandits and in rl with generative model. In International Conference Machine Learning, pp- 5662-5670. PMLR, 2020.
Qinghua Liu, Tiancheng Yu, Yu Bai, and Chi Jin. A sharp analysis of model-based reinforce- ment learning with self-play. In International Conference on Machine Learning, pp. 7001-7010. PMLR, 2021.
Qinghua Liu, Alan Chung, Csaba Szepesvári, and Chi Jin. When is partially observable reinforce- ment learning not scary? arXiv preprint Xix::2204.08867, 2022a.
Qinghua Liu, Csaba Szepesvári, and Chi Jin. Sample-efficient reinforcement learning of partially observable markov games. arXiv preprint arXiv:2206.00 vrXiv:2206.01315, 2022b.
Pierre Ménard, Omar Darwiche Domingues, Anders Jonsson, Emilie Kaufmann, Edouard Leurent, and Michal Valko. Fast active learning for pure exploration in reinforcement learning. In Inter- national Conference on Machine Learning, pp. 7599-7608. PMLR, 2021.
Akshay Mete, Rahul Singh, Xi Liu, and PR Kumar. Reward biased maximum likelihood estimation for reinforcement leamnng. In Learning for Dynamics and Control, pp. 815-827. PMLR, 2021.
12

---

Under review as a conference paper at ICLR 2023
Dipendra Misra, Mikael Henaff, Akshay Krishnamurthy, and John Langford. Kinematic state ab- straction and provably efficient rich-observation reinforeement learning. In International confer- on machine learning, pp. 1961-6971, PMLR, 2020.
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A Rusu, Joel Veness, Mare Belle- mare, Alex Graves, Martin Riedmiller, Andreas K Fidjeland, Georg Ostrovski, et al. Human-level control through deep reinforcement learning. natwre, 51 8187544):559-533 2015.
Aditya Modi and Ambuj Tewari. No-regret exploration in contextual reinforcement learning. In Conference on Uncertainty in Artificial Intelligence, pp. 829-838. PMLR, 2020.
Aditya Modi, Nan Jiang, Satinder Singh, and Ambuj Tewari. Markov decision processes with tinuous side information. In Algorithmic Learning Theory, pp. 597-618. PMLR, 2018.
Aditya Modi, Nan Jiang, Ambuj Tewari, and Satinder Singh. Sample complexity of reinforcement learning using linearly combined model ensembles. In International Conference on Artificial Intelligence and Statisties, pp. 20102200000 2020. PMLR, 2020.
Aditya Modi, Jinglin Chen, Akshay Krishnamurthy, Nan Jiang, and Alekh Agarwal. Model-free representation learning and exploration in low-rank mdps. arXiv preprint arXiv:2102.07035, 2021.
Shuang Qiu, Jieping Ye, Zhaoran Wang, and Zhuoran Yang. On reward-free with kernel and neural function approximations: Single-agent mdp and markov game. In International Conference Machine Learning, pp. 8737-8747. PMLR, 2021.
Daniel Russo. Worst-case regret bounds for exploration via randomized value functions. Advances in Neural Information Processing Systems, 32, 2019.
Daniel Russo and Benjamin Van Roy. Eluder dimension and the sample complexity of optimistic exploration. Advances in Neural Information Processing Systems, 26, 2013.
Daniel Russo and Benjamin Van Roy. An informatiin-tthooretee analysis of thompson sampling. The Journal of Machine Learning Research, (((1)::442-24711) 2016.
Daniel Russo and Benjamin Van Roy. Learning to optimize via information-direectd sampling. Operations Research, 66(1):230-252, 2018.
David Silver, Aja Huang, Chris Maddison, Arthur Guez, Laurent Sifre, George Van Den Driessche, Julian Schrittwieser, Ioannis Antonoglou, Veda Panneershelvam, Marc Lanctot, et al. Mastering the game of go with deep neural networks and tree search. nature, 529(7587):484-48) 2016.
Wen Sun, Nan Jiang, Akshay Krishnamurthy, Alekh Agarwal, and John Langford. Model-based in contextual decision processes: Pac bounds and exponential improvements over model-free approaches. In Conference on learning theory, pp. 0998-2933, PMLR, 2019.
William R Thompson. On the likelihood that one unknown probability exceeds another in view of the evidence of two samples. Biometrika, 25(3-4):285-294 1933.
Masatoshi Uehara, Xuezhou Zhang, and Wen Sun. Representation learning for online and offline in low-rank mdps. arXiv preprini arXiv:21 10.04652, 2021.
VG Vovk. game prediction with expert advice. In Proceedings of the eighth annual conference on Computational learning theory, pp. 51-60, 1995.
Andrew Wagenmaker, Yifang Chen, Max Simchowitz, Simon Du, and Kevin Jamieson. Reward- free rl is harder than reward-aware rl in linear markov decision processes. In International Conference on Machine Learning, pp. 22430-222222 22456. PMLR, 2022.
Ruosong Wang. Simon S Du, Lin Yang, and Russ R Salakhutdinov. On reward-free reinforcement learning with linear function approximation. Advances in neural information processing systems, 33:17816-1777 2020a.
13

---

Under review as a conference paper at ICLR 2023
Ruosong Wang, Russ R Salakhutdinov, 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, 2020b.
Yining Wang, Ruosong Wang, Simon Shaolei Du, and Akshay Krishnamurthy. Optimism in re- inforcement learning with generalized linear function approximation. In International Confer- ence on Learning Representations, 2021. URL https: https:// /ttps/////ppeeeeeieeeeee net forum?id= CRmJwzneppz.
Lin Yang and Mengdi Wang. Sample-optimal parametric parametttii q-learning using linearly additive features. In International Conference on Machine Learning, pp. 6995-7004. PMLR, 2019.
Andrea Zanette and Emma Brunskill. Tighter problem-depentee regret bounds in reinforcement learning without domain knowledge using value function bounds. In International Conference on Machine Learning, pp. 7304-7312. PMLR, 2019.
Andrea Zanette, David Brandfonbrener, Emma Brunskill, Matteo Pirotta, and Alessandro Lazaric. Frequentist regret bounds for randomized least-squares value iteration. In International Confer- ence on Artificial Intelligence and Statistics, pp. 1954-1964. PMLR, 2020a.
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, 2020b.
Andrea Zanette, Alessandro Lazaric, Mykel J Kochenderfer, and Emma Brunskill. Provably ef- ficient reward-agnostic navigation with linear value iteration. Advances in Neural Information Processing Systems, 1S::11756-1176 2020c.
Tong Zhang. Feel- thompson sampling for contextual bandits and reinforcement learning. SIAM Journal on Mathematics of Data Science, 4(2):834 857, 2022.
Weitong Zhang, Dongruo Zhou, and Quanquan Gu. Reward-free model-based reinforcement learn- ing with linear function approximation. Advances in Neural Information Processing Systems, 34: 1582 1593, 2021a.
Xuezhou Zhang, Yuzhe Ma, and Adish Singla. Task-agnostic exploration in reinforcement learning. Advances in Neural Information Processing Systems, 33:1 1734-11743, 2020a.
Zihan Zhang, Yuan Zhou, and Xiangyang Ji. Almost optimal model-free reinforcement learningvia reference-advanteee decomposition. Advances in Neural Information Processing Systems, 33: 15208- 2020h.
Zihan Zhang, Simon Du, and Xiangyang Ji. Near optimal reward-frre reinforcement learning. In International Conference on Machine Learning, pp. 12402-12411 PMLR, 2021b.
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, 2021.
A RELATED WORK
Sample-efficient reinforcement learning Sample-efficient RL has been extensively studied the basic model of tabular MDPs (Kears & Singh. 2002; Brafman & Tennenholtz, 2002; Jaksch et al., 2010; Dann Brunskill, 2015; Azar et al., 2017: Agrawal & Jia, 2017: Jín et al., 2018; Russo, 2019; Dann et al., 2019; Zanette & Brunskill, 2019; Zhang et al., 2020b; Domingues et al., 2021). The minimax sample complexity for finite-horizon tabular MDPs has been achieved by both model- based and model-free approaches (Azar et al., 2017: Zhang et al., 2020b). When there is function RL has been studied under concrete assumptions about the
approximation, the sample-efficienee function class and/or the MDP, such as (various forms of) linear or low-rank MDPs (Yang & Wang, 2019; Du et al., 2020; Jin et al., 2020b; Zanette et al., 2020b; Cai et al., 2020; Lattimore et al., 2020; Agarwal et al., 2020; Ayoub et al., 2020; Modi al., 2020; Zhou al., 2021). generalized linear
14

---

Under review as a conference paper at ICLR 2023
function approximation (Wang al., 2021), Block MDPs (Du et al., 2019; Misra et al., 2020), and so on. More general structural conditions and algorithms has been studied (Russo & Van Roy, 2013; Jiang al., 2017; Sun al., 2019; Wang et al., 2020b) and later unified by frameworks such as Bilinear Class (Du et al., 2021) and Bellman-Eluder dimension (Jin et al., 2021).
Foster al. (2021) propose the DEC complexity measure for interactive decision making prob- lems, and develop the E2D meta-algorithm as a general model-based algorithm for problems within their DMSO framework (which covers bandits and RL). The DEC framework is further generalized in (Foster et al., 2022) to capture adversarial decision making problems. The DEC has close con- nections to the modulus of continuity (Donoho & Liu, 1987: 1991a;b), information ratio (Russo & by-opiimization (Lattimore & Szepesvári, 2020). Our work builds on and extends the DEC framework: We propose the E2D- TA algorithm as general and strong instantiation of the E2D meta-algorithm, and generalize the DEC to capture PAC and reward-free learning.
Van Roy, 2016; 2018; Lattimore & Gyorgy, 2021), and
Other general algorithms Posterior sampling (or Thompson Sampling) is another general pur- pose algorithm for interactive decision making (Thompson, 1933; Russo, 2019; Agrawal & Jia, 2017: Zanette et al., 2020a; Zhang, 2022; Agarwal & Zhang, 2022a;b). Frequentist regret bounds for posterior sampling are established in tabular MDPs (Agrawal & Jia, 2017; Russo, 2019) and linear MDPs (Russo, 2019; Zanette et al., 2020a). Zhang (2022) proves regret bounds of a pos- terior sampling algorithm for RL with general function approximation, which is then generalized in Agarwal & Zhang (2022a:b). Our Appendix E. discusses the connection between the MOPS algorithm of Agarwal & Zhang (2022a) and E2D-TA. The OMLE (Optimistic Maximum Likeli- hood Estimation) algorithm is studied in (Liu et al., 2022a;b) for Partially Observable Markov De- cision Process; however, the algorithm itself is general and can be used for any problem within the DMSO framework; We provide such a generalization and discuss the connections in Appendix E.2. Maximum-likelihood based algorithms for RL are also studied in (Mete et al., 2021; Agarwal al., 2020; Uehara et al., 2021).
Reward-free RL The reward-free learning framework is proposed by (Jin et al., 2020a) and well- studied in both tabular and function approximation settings (Jin al., 2020a; Zhang al., 2020a; Kaufmann et al., 2021; Ménard et al., 2021; Wang et al., 2020a; Zanette et al., 2020c; Agarwal et al., 2020; Liu et al., 2021; Modi et al., 2021; Zhang et al., 202 l0;;;;;; Qiu et al., 2021; Wagenmaker et al., 2022). The recent work of Chen et al. (2022) proposes a general algorithm for problems with low (reward-free version of) Bellman- Eluder dimension. Our Reward-Free DEC framework generalizes many of these results by offering unified structural condition and algorithm for reward- ffree-freeeeeee RL with a model class.
Other problems covered by DMSO Besides multi- bandits and RL, the DMSO framework of (Foster al., 2021) (and thus all our theories well) handle other problems such con- textual bandits (Auer et al., 2002; Langford & Zhang. 2007; Chu et al., 2011; Beygelzimer et al., 2011: Agarwal et al., 2014; Foster & Rakhlin, 2020: Foster et al., 2020), contextual reinforcement learning (Abbasi- Yadkori & Neu, 2014; Modi et al., 2018; Dann et al., 2019; Modi & Tewari, 2020), online convex bandits (Kleinberg, 2004; Bubeck al., 2015; Bubeck & Eldan, 2016; Lattimore, 2020), and non- parammeretric bandits (Kleinberg, 2004; Auer et al., 2007; Kleinberg et al., 2013). In- stantiating our theories to these settings would an interesting direction for future work.
B TECHNICAL TOOLS
B.1
STRONG DUALITY
The following strong duality result for variational forms of bilinear functions is standard, e.g. ex- tracted from the proof of Foster et al. (2021, Proposition 4.2).
Theorem B.1 (Strong duality). Suppose that X, y are two topological spaces, such that X is Hausdorff and y is finite (with discrete topology). Then for a bi-continuous function f X Xx R
Thhe Hausdorff space requirement of X is only needed ensure that A(X) contains all finitely supported distributions on X.
15

---

Under review as a conference paper at ICLR 2023
that is uniformly bounded, it holds that
sup inf Eg Ex EeyyyElfffllaa = inf sup Ex Ef v) XeA(x) YEλ())
YEA()) xEa(x)
In this paper: for most applications of Theorem B.I, we take X' sume that IT is finite, which is natural assumption. For example, in tabular MDPs, it is enough consider deterministic Markov policies and there are only finitely many of them. Also, the finite- ness assumption Theorem B.1 can be relaxed- -Te strong duality holds long as both X is Hausdorff, and the function class (x. y - R] nE has finite p-covering for all p > 0. Such relaxed assumption is always satisfied in our applications.
M and y = IT. We will as-
B.2 CONCENTRATION INEQUALITIES
We will use the following standard concentration inequality in the paper.
Lemma B.2 (Foster et al. (2021, Lemma A.4)). For any sequence of real-valued random variables
(Xi adapted to filtration (Fi) it holds that with probability at least 6, for all t T,
log E (x,p(xX))) Fa-1l & Σ X, log (8-1)
B.3 PROPERTIES OF THE HELLINGER DISTANCE
Recall that for two distributions P, Q that are absolutely continuous with respect to J4, their squared Hellinger distance is defined
(P. Q = - [(VaF/dp VdQ/dp)) du.
We will use the following properties of the Hellinger distance.
Lemma B.3 (Foster et al. (2021, Lemma A.11, A.12)). For distributions IP, Q defined on X' and function h : X - [0, R). we have
[x]] Ba[n(X]] [[[{)[](()] + Ex[h(X)]) (P, Q).
Therefore, Ep(h( < 3TE [1 X)] 2 (P, Q) Also,for function h X' - [-R, RJ., we have
[e[h(x)] [x]](X)] [(()) + Ee[In(X)I)) (P.
Lemma B.4. For any pair of random variable (X, Y), it holds that
Ex-Px DD (Prix: Qylx)] 2D (Pxx,, Qx,x).
Conversely, it holds that
2 [D (Pyix, Qyix)] Da (x..),Q.yy)ee 3D (Px 21xxxx
Proof. Throughout the proof, we slightly abuse notations and write distribution P and its density dP /dp interchangeably. By the definition of the Hellinger distance, we have
Dir (Px, Qxy) = VPx.V
2
VFX2xx Prix Drix
1
Px Qx
2 v /Prix//ar Qryx
> 1
Px + Qx / /
Exapy DD (Prix, Qr(x)) + Ex (D (Prix, Qr
16

---

Under review as a conference paper at ICLR 2023
Similarly,
1
Di (xx,,Qxx,1 =1 [ |Pxxee+ f VPXxee(1 - (PIIXDrIx)
2
& < Dz (Px +
[x+
D (Prix- Orix),
2 2
and hence
_xxex [D (Pyix Qyxx)]
1
Di (Pxx,,xx)))) <Di (xx, Qxx
2
Exxxx DDA (Pyix, Qy + 2
<3Di (Pxx Qx) + 2Fx DR (Frix (rpx)]
where the last inequality is due to Lemma B.3 and D4 [0.
Next, recall the divergence Dtr. defined in (1):
R R (0) [01
D& (M(T), M(T)) (PM (T), PM (m)) Eo)P
Proposition B.5. Recall that (o,r) ~ ((T) is the observation and reward vectors as described RM (-1o). Suppose that [0, almost surely and
in Section 2, with o PM (T) and
M (o)13 x for all o E O. Then it holds that R M (0) R
Dir M(x)) & 5Dj (M()),
where D2 (M)... M(x)) the standard squared Hellinger distance berween RM & (M) and RM @ PM (T).
Proof. To prove this proposition, we need to bound (RM(() - R M (o)1 in terms of DH RM (o), (o)). We denote by RM (o) the distribution of rh- Then by independence, we have
1 Di (RM (o), (o), = I[1
Di (R (o). RM). (0)
1
2
- Drv (R (0), (o), R,N (o)
2
RM (0) -R (o)
2
1
R M (0) - RR (R((0) 2)
<exp
2
1
R (M) R M (0) (o0l
<1 - 7
where the last inequality use the fact that
= & 1 x/2 for all I [0,1]. Then by Lemma B.4,
(n) R (o) EM)PM
R R0( <2 DH(RMM() (o), RM (0))²
<DDi (M(z),
Combining the above estimation with the fact that D (PM()) p. (TT) & D (M()),
(data- pootesproessing inequality) completes the proof.
The following lemma shows that, although Diu is not symmetric with respect to its two arguments (due to the expectation over o ~ PM()) in the second term), it is almost symmetric within a constant multiplicative factor:
17

---

Under review as a conference paper at ICLR 2023
Lemma B.6. For any nwo models M, M and any policy n, we have
Diu [M ( M(r) & M(())
Proof. For any function h: O - [0. by Lemma B.3 we have
E px < 3 (xx) [[)]]] + 4D (PM (T), (T)). Therefore, we can take h as h(o) == R M (o) R M (o) and the bound above gives
(HM(MM()) (TT), PM (T)) + E (mT [h(o)] [n) (T)) Pi (T))
$ 5D (P (T), PM (x)) (m)
5D (M())
which is the desired result.
Lemma B.7. For any two models M, M and any policy n, we have
5 - (z) < &VH+ (RT(
Proof. We have
pM -T) (T)) (x) R.M pT)
RT (0)
E Bo-par (+)
RD (0) -RM (0) (E)PA((T RdM (0)
1t p..pN(())
M (0)
H R (o) - RR (0) + DH((M((T), (T(T))
Boupir (T)
(i)
[RM R JM ( [1] (PM (T), pJt (TT(T))
(H + 1)
(OOPM())
=VH+1 (RL( M(T)..
Above, (i) uses the fact that R. (o) E [0, 1] almost surely, and the bound
E Pa) (m)
R (o)
E (T)
R (0) & Drv(p (Tt), PM (=)) & Dn(P (T));
(m)
(ii) uses the Cauchy inequality / Ha b & /(H (a B2) and the fact that the squared mean is upper bounded by the second moment.
C DISCUSSIONS ABOUT DEC DEFINITIONS AND AGGREGATION ALGORITHMS
C.I DEC DEFINITIONS
Here we discuss the differences between the DEC definitions used within our E2D-TA and within the E2D algorithm of Foster et al. (2021, Section 4.1) which uses Vovk's aggregating algorithm as the subroutine (henceforth E2D-VA). Recall that the regret bound E2D-TA scales with d.c.(M) defined in Definition (cf. Theorem 2).
We first remark that all the following DECs considered Foster et al. (2021) are defined in terms of the squared Hellinger distance (M),, (TT) between the full distribution of (o, r, induced by models M and M under т, instead of our Dir, which is defined in terms of squared Hellinger distance in o and squared L2 loss in (the mean of) r. However, all these results hold for D1u as well with the DEC definition and algorithms changed correspondingly. For clarity, we state their results terms of Di.,, which will not affect the essence of the comparisons.
Foster et al. (2021, Theorem 3.3 & 4.1) show that E2D-VA achieves the following regret bound with probability at least
Regpm & ( suPpeco(M)
+ lo)((-))6))).
18

---

Under review as a conference paper at ICLR 2023
where
(M) dec, (M;dū)
sup inf sup E Expp (TM) - (M)) - -Dii (M(T) E2 M- M M
( (II( MEM
(x) denotes the mixture distribution of (x) for M Tt and co(M) denotes the set of all mixtures of models in .M (which can be also identified with A(M), the set of all probability distributions over M).
where EE [
Compared with doc,, Eq. (8) is different only in the place where the expectation ΣNTz is taken. As Pi convex in the second argument (by convexity of the squared Hellinger distance and linearity of E EM Bo- pM (x)
R (o) - R RM(()) (0) in (t), by Jensen's inequality, we have
sup dec, (M; > (ec)
peco(M)
Unfortunately, bounding (Eco(c)) (e; 6p) requires handling the information gain with spect to the mixture model 1- M - (T)]. which is in general much harder than bounding the (MV) which only requires handling the expected information gain with respect a proper model (T) over M μ. For general RL problems with
1, it unclear whether (M)) dec, (M; 5z) admit bounds of the form d/1 where d is some complexity measure (Fos- ter et al., 2021, Section 7.1.3). By contrast, our (ec, can be bounded for broad classes of problems (e.g. Section 5).
We also remark that an alternative approach considered in Foster et al. (2021, Theorem 4.1) depends on the following definition of DEC with respect to deterministic reference models:
dec,, M) == inf sup Ex~p (FM( (M) - (M
pEA(M) MEM
and the DEC of the model class M is simply (M) := supMEM dec, (M, As M (viewed as the set of all point masses) is subset of co(M), by definition we have
dec,(M) & dec,(M)
therefore (Mc) can be bounded as long as (M)) can. However, that approach requires the
online model estimation subroutine output proper estimator M M with bounded Hellinger error, which-unlit Tempered Aggregation (for the improper case)-requires problem-specific de- signs using prior knowledge about M and is unclear how to construct for general M.
C.2 AGGREGATION ALGORITHMS AS POSTERIOR COMPUTATIONS
We illustrate that Tempered Aggregation is equivalent computing the tempered posterior (or Ridgway, 2020) in the following vanilla
power posterior) (Bhattacarya et al., 2019; Alquier
Bayesian setting.
Consider a model class M associated with a prior j e ((M), and each model specifies a distri- bution p. (+) (OO) of observations e O. Suppose receive observations of ..... 0² ,... in sequential fashion. In this setting, the Tempered Aggregation updates
p. (M) ocss 1² (M) exp (1pp log Mp (o') = (M(M) (PM()'')
Therefore, for all t 1,
[ P (00) (19))))))
(M) aM (M)
If 7 in Vovk's aggregating algorithm (Vovk, 1995), by Bayes' rule, the above y²+1 is exactly the posterior M Mo As we chose 7p & 1/2 < 1 in Tempered Aggregation, μ gives the tempered posterior, which is a slower variant of the posterior where data likelihoods are weighed less than in the exact posterior.
19

---

Under review as a conference paper at ICLR 2023
Algorithm 2 TEMPERED AGGREGATION
Input: Learning rate 7p E (0. 5), n7 0.
Initialize 1 Uni
2: for t ....... -.. do
3: Receive ( d'r
4: Update randomized model estimator:
(M) aM (M) exp (Tp log 1oogpMMs0 (d'1 ||r" R (o)))
(10)
D PROOFS FOR SECTION 3
D.1 TEMPERED AGGREGATION
In this section, we analyze the Tempered Aggregation algorithm for finite model classes. For the sake of both generality and simplicity, we state our results in the following general setup of online model estimation. Lemma 3 (restated in Corollary D.2) then follows as a direct corollary.
Setup: Online model estimation In an online model estimation problem, the learner is given model set M, context space II, observation space O, family of conditional distributions (PM (1))) II - A(O)) a family of vector-valued mean reward functions (R. A O
[0,1] MEM. The environment fix ground truth model M M; for shorthand, let F
p.M R RM For simplicity (in a measure-theoretic sense) we assume that O is finite..
At each step t E [T], the learner first determines randomized model estimator (i.e. a distribution over models) μt A(M).. Then, the environment reveals the context x' II (that is in general ran- dom and possibly depends on jl' and history information), generates the observation o² IP* (()) and finally generates the reward r' e I&d (which a random vector) such that E. [rrr]] = R (o'). The information (x', o', r') may then be used by the learner to obtain the updated estimator jt +!
For any M E M, we consider the following estimation error model with respect to the true model, at step t:
Erryy = E.
Da [D (('''),, + RM R (o'))
where E, is taken with respect to all randomness after prediction μ² is made in particular it takes the expectation over (m', o'). Note that Errhs- by definition.
Algorithm and theoretical guarantee The Tempered Aggregation Algorithm presented in Al- gorithm 2. Here we present the case with finite model class (IM) < oo); In Appendix D.3 we treat the more general case of infinite model classes using covering arguments.
Theorem D.1 (Tempered Aggregation). Suppose [M] < 0c, the reward vector r' is -u-sub- Gaussian conditioned on of, and R Ad (o") R' (o')ll, & D almost surely for all E [T]. Then, Algorithmm 2 with any learning rale Vpp T)r > such that 2np + 20 h < achieves the following with probability at least 1 d:
T
Σ
E Es [Err[g] & C'log((MM/6),
Up [1 2 ). d' == (1- (1- stants depending (?p² Tr. 0² D) only. Furthermore, it also achieves the following in-expectation
where C max
and c == nr/(1 2np) are con-
We use MM (o) and Mp (ol=T) interchangeably in the following.
"To extend continuous setting, only slight modifications are needed, see e.g. Foster et al. (2021, Section 3.2.3). In other words, F, the conditional expectation on F. ap
20

---

Under review as a conference paper at ICLR 2023
guarantee:
T
E
Ba- Err M
Coo [M].
The proof of Theorem D.I can be found in Appendix D.I.I.
Lemma 3 now follows as direct corollary of Theorem D.1, which we restate and prove below. Corollary D.2 (Restatement of Lemma 3). The Tempered Aggregation subroutine (3) in Algorithm with 4mp + T achieves the following bound with probability at least 1-160 8:
EStaL := Σ
(T),, Eri St up (TT)) MT & C. log((l)
1=1
where C depends only (7p= Wr). Specifically, can choose T/p- 1/- 1/3 and C 10. Furthermore, when Tpp EH (0, 2 1/ = O. (3) achieves
T EstR Σ En
D pM (x²), p.i (+4) & - -log[[|MM/
37 up
with probability at least 1
Proof. Note that subroutine (3) in Algorithm exactly an instantiation of the Tempered Aggrega-
tion algorithm (Algorithm 2) with context x' sampled from distribution p' (which depends on μ²), observation o², and reward r'. Therefore, we can apply Theorem D.I, where we further note that Ex Err Ms corresponds exactly to
Erra,
E Eg up Epi
Dii(PM (T²), (M' (MM(((') + Eo- (x') RM (0) - -R- RRM M7 (o)
2
E M up Eut
(M' M (T'))
Notice that we can pick o² 1/4 and D 22, each individual reward rh [0, 1] almost surely (so is 1/4-sub-Gausiian by Hoeffding's ' Lemma), and
H
R RM(0) (0) - -R (0) [0) Σ
M (o)
RM (o)
Σ
R (o) Ri (0)
R (0)
R (0) 2.
for any two models M, M' and any E Therefore, Theorem D.1 yields that, as long as 4np + 1/c 2, we have with probability at least 1 - that
EstaL
Σ 1-1
En op E ~ -m (f & C' log(IM)/66)
M'
1 [T- 3mp ). (1 -1- and 1/:( 27p)) Choosing 7p 1p
where C' max
?r 1/3, we have 1, c/ (1-6-1) and max (3.3/c] by numerical calculations.
This is the desired result. The case 7)- = 0 follows similarly.
D.1.1 PROOF OF THEOREM D.I
For all [T'] define the random variable
exp ?pp log Tp (o' + 515 ).
MM (o'( (o'(
= log EM
21

---

Under review as a conference paper at ICLR 2023
where
8/1 : [r'
R R²(o')
R (o')l
(1I)
Recall that E, is taken with respect all randomness after prediction p² is made. Then
(o'(T=))) (o + n: ]]
exxexp (-A')
Eg
EM-
exp
Mp log
pM (M'('= + n:O5x ]
= = EE
exp
Thp log
MEM
p.M (o'l=T))
< Σ (M)
21/p exp
2
log
PT (o*
+ (1 2np) exp
11 21/p
8/s
(12)
MEM
PM (o|
=m
Σ
(M
V p)
MEM
(1 2mp)
Σ
(M)), exp
21pp 53
MEM
For the first term, by definition
PM (o)
Ba-P (17)
(o(()
= 2
Di (I''(')>)))
(11x"), (-Ix)))
(13)
To bound the second term, we abbreviate c:== can be found in Appendix D.1.2.
Tre 1-2np
and invoke the following lemma. The proof
Lemma D.3. Suppose that r Rdd is a o² -ubb-Gauusia and f E Rd is any fixed vector. Then the random variable
Gaussian random vector, E[r] the mean of r,
5 ||
F12
||r
f 2:
satisfies Elexp(Ad)] & exp (-X(1-20*) | R13) for any X R.
Therefore,
E2 exp (c]
&R exp
(c(1 202c) - (o))))))))
< < <'E, (R')-'((
(14)
where the second inequality is due the fact that for all [0, D2J. it holds that e ec(1-200 & - c'x, which is ensured by our choice of e [0, 2/0²) and é' := (1 e -DDce(1-20' DDD 0. Therefore, by flipping (12) and adding one on both sides, and plugging in (13) and (14), get
1- EE, [exp (-A9] 11 E Ex F. [
+
21pp oe E Eas E, | M (o') (0') R (o))
R
Thus, by martingale concentration (Lemma B.2), we have with probability at least 1 5 that
A + log(1/0) >
- log E. exp (-D9]
1 - E, [exp (-D9)
E EMa Ey (PM((+=T') IP* (+(7)()))]
3/p
(15)
1=1
T
+ (1 - 2mp)c
Σ
E B (o') (o'))
[-]
3 min {np (1 - )cp EM-yy Errhy]
22

---

Under review as a conference paper at ICLR 2023
It remains upper bound Σ A. Note that the update rule of Algorithm 2 can be written in the following Follow-Thh The--hh-RRee Beeee-Reguaaee-LLaaee Leaderr form:
(M) exp (Eogi-1 Up log PPM (o"1=²) + n.55))
(M) Emren 1 (M)) exp (Exst- Up log PM (o* (-0) + 17. m/.
where we have used that 8/ = - -1r R constant that does not depend on M for all t e [T]. Therefore we have
(o') R
+ || - R* in which |r - R² R2(o')
P. (o'(") (=
exp(-A") = EM-
exp
1pp log
+ .n.6%s)
P.M (o'(TT) p. (o'(==))
Σ (M) exp 1p log
n:0's
MeM
n= (M) exp (E Up log PM (0 (T+) 1/.
PM (o'|T²)
Σ
exp
7pp log
1 (o'(TT) + n
EMEMM (M1) exp (- 1pp log paM (o*l (0*1==)) m.07rr)
MEM
EMEM 1² (M) exp EESe Up log (((o-))))
pM (o"(=" + 17,0
EMEM 1e (M) exp
EE Mp log (=(1(x"))
pat (or)=") + n1:03M
(16)
where the last equality used again the fact that -Mp log F (o*lTT) is constant that does depend on M for all s E [t].
Taking log on both sides above and summing over
[T], we have by telescoping that
T Σs
T Σ
PM (o'(aT) (o + m1
log
M'M) exp
1p
log
(17)
MeM
By realizabiliity M e M. we have
log (M") log MM
Plugging this bound into (15) gives the desired high-probability statement. The in-expectation state- ment follows similarly by further noticing that (15), taking the expectation ΣT A' gives the same right-hand side, but without the additional log(1/8) term on the left-hand side.
1.2 PROOF OF LEMMA D.3
By definition,
8 2 - r, - -I 1f- r1/2
and therefore,
Elexp (A6)] exp (-A Blexp
( -F()) (2X
F>)]
(20²>² f F A -F1
<exp
(-X(1 11:1-22-20 |r +1
exp
where the inequality is due the definition of σ² ...sss--aaussse Gaussian random vector: For 22(F
R
a² [ 2
E[exp ((r, & exp
23

---

Under review as a conference paper at ICLR 2023
Algorithm 3 E2D Meta-Algorithm with Randomized Model Estimators
Input: Parameter y 0: Online estimation subroutine Algest Prior distribution p E A(M).
1: for = ,,...,, do
2: Set arg ((T)) 17 (p), where D is defined in (2).
3: Sample x² p². Execute n² and observe (o',r") r²).
4: Update randomized model estimator by online estimation subroutine:
1t < AlgÉst (1(7',0", ,r)))()))))))
D.2 GENERAL E2D & PROOF OF THEOREM 2
We first prove guarantee for the following E2D meta-algorithm that allows any (randomized) online estimation subroutine, which includes Algorithm I as special case by instantiating Alg as the Tempered Aggregation subroutine (for finite model classes) and thus proving Theorem 2.
The following theorem is instantiation of Foster al. (2021, Theorem 4.3) by choosing the divergence function to DRL. For completeness, we provide a proof in Appendix D.4. Let
EstaL = Σ Exi Exinpi B srenut (M')
(18)
denote the online estimation error of { 1 in D divergence (achieved by Algest)-
Theorem D.4 (E2D Meta-Algorithm (Foster et al., 2021)). Algorithm achieves
RegDM & T dec, (M) + + EstaL.
We are now ready to prove the main theorem (finite M).
Proof of Theorem Note that Algorithm is an instantiation of Algorithm with Algest chosen as Tempered Aggregation. By Lemma 3, choosing Tpp = = 1/3, the Tempered Aggrega- tion subroutine achieves
EstaL & 10 10
with probability at least On this event, by Theorem D.4 we have that
RegDM & T (M)) + + EstRı & T (M) + 10ylog(( [0g[| MM))).
This is the desired result.
D.3 E2D-TA WITH COVERING
In many scenarios, have to work with infinite model class M instead of finite In the following, we define a covering number suitable for divergence DRL. and provide the analysis of the Tempered Aggregation subroutine (as well the corresponding E2D-TA algorithm) with such coverings.
We consider the following definition of optimistic covering.
Definition D.5 (Optimistic covering). Given p E [0, 1]. an optimistic p-cover of M is a tuple Mo), where Mo is finite subset of M, and each Mo MM is assigned with an optimistic likelihood function TiMo such that the following holds:
(1) For Mo E Mo.for each n, [Mao+(.) specifies a un-normalized distribution over O, and it holds that (.). - [MMoo=()) E.
24

---

Under review as a conference paper at ICLR 2023
(2) For any M E M. there exists Mo Mo that covers M: for all II, O, it holds [.Mo.( (o) i (PMM.(())) and RRM (o) R. R.Mo(()), & p.
The optimistic covering number ((M,)) is defined as the minimal cardinality of Mu such that there exists P such that (P, is an optimistic p-cover of M.
With the definition of optimistic covering hand, the Tempered Aggregation algorithm can be directly generalized to infinite model classes by performing the updates on an optimistic cover (Algorithm 4).
Proposition D.6 (Tempered Aggregation with covering for RL). For any model class M and an associated optimistic p-cover Mo), the Tempered Aggregation subroutine
n!*1 (M) XM n¹ (M) -exp (Np log TeM.. - (
(19)
with xt Uni and Mp 1/ 1/3 achieves the following bound with probability at least 1-6: 6:
EsTRL. & 10 [log MMo + 27 2lgg2266))
E2D-TA with covering
Define
est(M, K) == inf (log p) Kp)
(20)
P30
which measures the estimation complexity of M for K-step interaction.
Proposition D.6 implies that, based on the model class M, we can suitably design the optimistic likelihood function IP and the prior jr', so that Algorithm 3 with Algest chosen (19) achieves ESTRL Ô (T), Therefore, by Theorem D.4 directly have the following guarantee. Theorem D.7 (E2D-TA with covering). Algorithm 3 with Algest chosen as TEMPERED AGGRE- GATION WITH COVERING (19) and optimally chosen y achieves
RegDM < C inf
+ (est(,,,)) (M) 7>0
log(1/)))
with probability at least 1 8, where is universal constant.
D.3.1 DISCUSSIONS ABOUT OPTIMISTIC COVERING
We make a few remarks regarding our definition of the optimistic covering. Examples of optimistic covers concrete model classes be found in e.g. Exammle K.13, Proposition 15; see also (Liu et al., 2022a, Appendix B).
more relaxed definition
We first remark that Definition D.5(2) can actually be relaxed to
(2') For any M E -M, there exists Mo E MM. such that max,so | M (o) R (o & and
(olm)
Bg- (+1=)
<1+ P. VI.
For the simplicity of presentation, we state all the results in terms of Definition D.5. But the proof of Theorem D.8 can be directly adapted to (f); see Remark D.9.
Relation to Foster et al. (2021, Definition 3.2) We comment the relationship between optimistic covering and the covering introduced in Foster et al. (2021, Definition 3.2) (which is also used in their algorithms handle infinite model classes). First, the covering in Foster et al. (2021) needs to cover the distribution of reward, while ours only need to cover the mean reward function. More importantly, Foster et al. (2021, Lemma A.1 explicitly introduces factor log B, where
10 important observation is that, along with (I). this requirement implies Drv (pM+((), PM: (-)) (-,,pMo:" (for proof, see e.g. (33)). Therefore, p-optimistic covering be -p" -coverng in TV distance.
p²
25

---

Under review as a conference paper at ICLR 2023
Algorithm 4 TEMPERED AGGREGATION WITH COVERING
Input: Learning rate 7/p E (0.2),
()), m > 0, number of steps T, p-optimistic cover (F,, (o).
1: Initialize μ < Unif(MMo).
2: for L...., do
3: Receive o'r))
4: Update randomized model estimator:
(M) aas (M) exp 1/p log (o') 7t 1|r (0))))
(almr with being certain base distribution. Actually, with such a B, we B > Me [[o[s]
can show that
NMM, & p2
where Nrv the covering number in the TV sense, and A" is the optimistic covering number with respect to (t).
Relation to other notions of covering numbers Ignoring the reward component, our optimistic covering number essentially equivalent to the bracketing number. We further remark that opti- mistic covering can be slightly weaker than the covering in x²-distance sense: given p²-covering Mo in the latter sense, take TP (1 p²) to obtain p-optimistic covering defined by (t).
D.4 PROOF OF THEOREM D.4
We have by definition of RegDM that
RegDM = Ext (M((TTN) (TTM-) - /M (T7)
Eyta we pM (TT (x*) 7.B
D (T7)
T Y
Ey Sp Bi (M (T')) (T'), (x')) (x²))
+
T
sup Ex [ (M - M(=))) + 7 EstRL
T
(di)
Dit (x')
+7 ESTRI.
pe ((1) V. (n)
dec, (M,, + ESTRI. & T dec, (M) y. EsTRI.-
Above, (i) follows by the realizability assumption M -M; (ii) follows by definition of the risk Oy (ef. (2)) as well as the fact that p' minimizes Ve (-) in Algorithm 3; (iii) follows by definition of dec, (M,x)). This completes the proof.
D.5 PROOF OF PROPOSITION D.6
We first restates the TEMPERED AGGREGATION WITH COVERING subroutine (19) in the general setup of online model estimation in Algorithm 4.
Theorem D.8 (empered Aggregation over covering). For any M that is not necessarily finite, but otherwise under the same setling Theorem D.I, Algorithm 4 with 2np 202n, achieves with
26

---

Under review as a conference paper at ICLR 2023
probability at least 8 that
Σ
BM- [Errys]
C'loo Mool + 1og 2T + +7p]
where C' is defined same in Theorem D.I.
Plugging Theorem D.8 into the RL setting, picking (7p- m,) and performing numerical calculations, directly have the Proposition D.6. The proof follows the same arguments Corollary D.2 and hence omitted. Similarly, when 77p = E (0, 5). = 0, the proof of Theorem D.8 implies that (19) with n
Uno achieves the following bound with probability at least - 6:
Σ E Bp E Mi-wu Di (p (x'), pi
(=9)
! 7
[log Moo + 2n/p 2 log (2/))] (21)
Proof of Theorem D.8
The proof is similar to that of Theorem D.I. Consider the random variable
P. (o'(
n- )
A
log EMs exp
"p log (o'(=')
for all e [T]. where is defined in (11). Then by (12) and (14), we have
(o
Eg exp (-A')] 2m Be
| (+'
+ (1 - 2mpp (1 - EE E. - (o))
where c' is the same as in Theorem D.1. To bound the first term, we notice that for all II, and Tpa (-|xT), we have
pM (T) (P((T)
pp (o|x))
P. (o/T) V PM (o/T))
Bo-Pr(-M (-1x7)
EENPt( 1 (o(())
(P*(T)
[ PA (o(T)
1
11 2
(1() (((m) (
(-17),
P*(o)(T)
T - PPM
<1
Di(M (-1T), P'())) + (OwP'(
2
(P((T(T))
Di (-1T), (-IT)) + -11m))PPM111)
2
2 (1M (-1T), PM (-Im) P:
(22)
where the last inequality is due to the fact that IM (-|T)) PM (-1m) = (22) directly implies
that
PMM (ot (rt) 1 (o mx)
E,
[
E, D
(I (IMM(- (-1x'),
",""",''" F (-(++'))) + p.
(23)
Therefore, by Lemma B.2, with probability at least 8/2, holds that
T
A log(2/5)
log E, exp (-49) > Σ 1 - E, exp (-A1)
27

---

Under review as a conference paper at ICLR 2023
7/pp
M pp Ee
[D] (-17*), (-(T'))) 2I'
T
+ (1 2np c
2
Ey
R R=
In the following, we complete the proof by showing that with probability at least 1 5/2.
T A
log |ool
- tog 12g(2/)).
By telescoping argument same as (17), we have
T Σ
P& (o'1T²)
Σ A' = log Σ (M)
exp
Up log
P (=(o'(ntt) + 17 n:
(24)
MeMo
By the definition of MM and the realizabiliity M M, there exists M e MM such that M is covered by M (i.e. R (o)
(o)o < p and PM (-IT) e Pd (-|m) for all σ). Then
(o'(TT))
17, 1r0'/ )}
I
exp
Σ S
Mo E exp
Mp log
(25)
Now
T
P (o'(
PP' (o'(==))
9r
E
exp
Upp
log
E
expl 1op(-nnit -1
Tpm ( x)
PM (ot (TT)
t=1
E
exp(-17,ár)
E
exp(-nn,ár) E
(enr))eE((pppp-ee [[exp(=n) o or]
(26)
1=1
T-
exp (2pm), }
exp( -
exp pm:),
where the first inequality is due to pp > P., the second inequality is because for all [T].
1opp--n:5% o'] & exp (1((1 + 20
202m)) me)
R MMMMMO3 (o') - R² & exp(2pnc).
which
is
due to
Lemma
D.3 and (ot) R (o'))
R M (ot) R M (o') (o))l
(o)ol
& p. Applying Chernoff's bound completes the
proof.
Remark D.9, From the proof above, clear that Theorem D.8 also holds for for the alternative definition of covering number in (f): Under that definition, proceed in (26) by using the fact
E, (m)m)
(o(m)
< 1 + and the fact E [cxp(-n.,%h)) o'1 exp(2pn.) alternately.
pa (alm)
E CONNECTIONS TO OPTIMISTIC ALGORITHMS
Motivated by the close connection between E2D-TA and posterions/liklihhods,, in this section, we re-analyze two existing optimistic algorithms: Model-based Optimistic Posterior Sampling (MOPS). and Optimistic Maximum Likelihood Estimation (OMLE), in parallel fashion to E2D- TA. We show that these two algorithms- in addition to algorithmic similarity to E2D-TA- TED-TA-WO work under general structural conditions related to the DEC, for which establish formal relationships.
28

---

Under review as a conference paper at ICLR 2023
E. MODEL-BASED OPTIMISTIC POSTERIOR SAMPLING (MOPS)
We consider the following version of the MOPS algorithm of Agarwal & Zhang (2022a)". Similar E2D-TA, MOPS also maintains a posterior μ² A(M) over models, initialized suitable prior μ². The policy in the 1-th episode is directly obtained by posterior sampling: T² TM where M p². After executing x' and observing (o', r²), the algorithm updates the posterior as
(M) cMM p¹ (M) exp (7-1 (~'1SM(TTA) (TTM) + Tpp log pM,'' (o') - Th - M (d))
(27)
This update is similar as Tempered Aggregation (3), and differs in the additional optimism term y f (FM)) which favors models with higher optimal values. (Full algorithm in Algorithm 5.)
We now state the structural condition and theoretical guarantee for the MOPS algorithm. Definition E.1 (Posterior sampling coefficient). The Posterior Sampling Coefficient (PSC) of model class M with respect to reference model M M and parameter
0 is defined as
pSc, (M, M) := sup Eas-BEr-p [M (TTM) - 5 wED(M)
(0 (TM) - -r... (M(M.))))M) M(TMr))
Theorem E.2 (Regret bound for MOPS). Choosing "h = 1/6, m = 0.6 and the uniform prior k² (M), Algorithm 5 achieves the following with probability at least ó:
RegDM & T psc PPpps.ooMM M²) + 2/7] + 4y log( (Mg()
Theorem E.2 (proof in Appendix F.1) is similar Agarwal & Zhang (2022a, Theorem 1) and is slightly more general in the assumed structural condition, as the PSC is bounded whenever the "Hellinger decoupling coefficient" used in their theorem is bounded (Proposition F.5).
Relationship between DEC and PSC The definition the PSC resembles that of the DEC. We show that the DEC can indeed be upper bounded by the PSC modulo (lower-order) additive stant; in other words, low PSC implies low DEC. The proof can be found in Appendix F.4. Proposition E.3 (Bounding DEC by PSC). Suppose IT is finite, then have for any y 0 that
(Mc) sup /MM, M) + 2(11 + 1)/7-
MEM
E.2 OPTIMISTIC MAXIMUM LIKELHHOOD ESTIMATION (OMLE)
Standard versions of the OMLE algorithm (e.g. Liu al. (2022a)) use the log- likelihoodd of all observed data as the risk function. Here we consider the following risk function involving the log-likes likelihoood of the observations and the negative L2 loss of the rewards, to be parallel with E2D- 'A and MOPS:
(MM E log P. (0*M) (r+)- RM (000 [o
(28)
In the t-th iteration, the OMLE algorithm plays the greedy policy of the most optimistic model within a 3-superlevel set the above risk (Full algorithm in Algorithm 6):
(M' x²)==
arg max
p. (T) such that L.(M) > max Le(M') - 3.
(29)
(M.))EMXII
M8
We now state the structural condition and theoretical guarantee for the OMLE algorithm. Definition E.4 (Maximum likelihood estimation coefficient). The maximum likelihood estimation coefficient (MLEC) of model class M with respect to reference model M M, parameter > 0,
and length K Zzz1 is defined as
K
mlec, . (M,M))
sup (M+)eM
JaM (TTM)
gd (TTM)))
K
max Σ D (MTM)) M M (TTN)) kE[K] rsk-1
Our version is equivalent to Agarwal & Zhang (2022a, Algorithm 1) except that we look the full obser- vation and reward vector (of all layers), whereas they only look random layer h² Unif([H]).
29

---

Under review as a conference paper at ICLR 2023
Algorithm 5 MOPS (Agarwal & Zhang, 2022a)
1: Input: Parameters 7, > 0; prior distribution j E (MM); optimistic likelihood function
2: for 1,..., do
3: Sample M ~ (-) and set n' = =T= TMC.
4: Execute n' and observe (o',r").
5: Update posterior of models by Optimistic Posterior Sampling (OPS):
1²*1 (M) OCM p² (M) exp (7'S (TT) + 1/p log M,, (o') 7/ ||r" R. -R)(o (30)
Theorem E.5 (Regret bound for OMLE). Choosing 3log(IM188) > 1, with probability at inf (T- (M,c,, M*) 12y log((-M/00))
least 1 - 8, Algorithm 6 achieves
RegDM
720
Existing sample-efficiency guarantees for OMLE-type algorithms only established on specific RL problems through case-by-case analyses (Mete et al., 2021; Uehara et al., 2021; Liu et al., 2022a;b). By contrast, Theorem E.5 shows that OMLE works any problem with bounded MLEC, thereby offering a more unified understanding. The proof of Theorem E.5 is deferred to Ap- pendix G.2.
We remark that the MLEC is also closely related to the PSC, in that bounded MLEC (under slightly modified definition) implies bounded PSC (Proposition G.4 & Appendix G.3).
F PROOFS FOR SECTION E.1
F.1 ALGORITHM MOPS
Here we present more general version of the MOPS algorithm where we allow M to be a pos- sibly infinite model class, and require prior je' A(M) and optimistic likelihood function (cf. Definition D.5) as inputs. The algorithm stated Appendix E. is special case of Algorithm with |M| < oc, P P, and p² Uni.
We state the theoretical guarantee for Algorithm 5 as follows.
Theorem F.1 (MOPS). Given p-optimistic cover (IP, Mo). Algorithm 5 with fp 1/6, 7/- 0.6
and μ (o)) achieves the following with probability at least - 5:
< T psc (M,, + 2] + >llog Mal + 3TT + log(2/))
RegDM
Choosing the optimal achieves
0, with probability at least 6, suitable implementation of Algorithm 5
& 12 inf T (M, + T >[est( + log(1/8)
RegDM
7>0
When M is finite, clearly (P, itself is 0-optimistic covering, and hence Theorem F.l implies Theorem E.2 directly.
is worth noting that Agarwal & Zhang (2022a) state the guarantee of MOPS in terms of general prior, with the regret depending on certain "prior around true model" like quantity. The proof of Theorem F2 can be directly adapted to work in their setting; however, we remark that, obtaining an explicit upper bound on their "prior around true model" in a concrete problem likely requires constructing an explicit covering, similar as in Theorem F.1.
Proof of Theorem F.1
By definition,
Regpm
Σ EM-pp (Pf((TTM) fM (TM))
30

---

Under review as a conference paper at ICLR 2023
-M fal (TM. (M (TMS) + 2 6 En-pt fPi (T)
Bounded by Corollary F.3
T
EM gMl (TTA)) fdd (T
2 Exap' Dit.. (T))
6
Bounded by psc
27 + T pSc p
<yllog |Mol + +TTp+ 2log(2/6))
F.2 OPTIMISTIC POSTERIOR SAMPLING
In this section, we analyze the following Optimistic Posterior Sampling algorithm under a more general setting. The problem setting and notation are the same the online model estimation problem introduced in Appendix D.1. Additionally, we assume that each M E .M is assigned with a scalar VM [0. 1]; in our application. VM going to be optimal value of model M.
Theorem F2 (Analysis of posterior in OPS). Fix a p > and a p-optimistic covering (Po of M. Under the assumption of Theorem D. I, the following update rule
1²*1 (M) dss μ¹ (M) exp (7- -VM + 17p log (M (o'(=²) mr Ir (r
(31)
with 27pp + 40 < 1 and p² = Unif(Mo) achieves with probability at least 1 - 5 that
T
T
Easapi [V. Vas + ouy Err'rl < 87(1 - 211p
20² + y log Mul
+ -T 2mp + nr) + 2 llo(2/6))
where V. Va and co min(Tp- 40 e- -D* ) as long as there exists M E Mo such that M is covered by M (cf. Definition D.5) and VMr 2 V. 2p.
The proof of Theorem F.2 can be found Appendix F.2.1.
As direct corollary of Theorem F.2, the posterior j² maintained in the MOPS algorithm (Algo- rithm 5) achieves the following guarantee.
Corollary E.3. Given a p-optimistic covering (P, MM), subroutine (30) within Algorithm 5 with
Up 1/6, n 0,6,7 ž and uniform prior jr Unif(Mo) achieves with probability at least
1 - 5 that
T
Σ
E EMaa w² pMM (TT..) - M (MTMM + 2 Exxp [DR
2T
+ +>/oo MMol 3Tp + 2log(2/6)))
Proof. Note that subroutine (30) in Algorithm 5 is exactly an instantiation of (31) with context n' sampled from distribution of (which depends on μd)), observation o', reward r², and VM fM (TTr). Furthermore, EM- [Eriy]] corresponds to E Eng (cf. Corollary D.2).
-p Ex D (T',
Therefore, in order to apply Theorem F.2, we have to verify: as long as M Mo covers the ground truth model M (i.e.
|R Mo (o) RR(()), & p and P. (-Im)) 2 I (-I for all T), it holds that
VM 2 V. - 2p. We note that V. > f (TM)), thus
V. VM & sup
(T) yM (T) & sup Drv (-I() PM (-IT)) +
(32)
31

---

Under review as a conference paper at ICLR 2023
by definition. An important observation is that, for e II,
Drv (F" (-IT), IPM (-1T)) = Σ (o/=) - pM (o[T)]
T.M (o|T) (oN) & p². (33)
OEO
OEO
Therefore, V.-VV. VM E 5 0² Σ 2p. Now we can apply Theorem F.2 and plug 0² 1/4, D2 as in Corollary D.2. Choosing 1/p = 1/6, 1/2 0.6, and 7 > 1, we have 41, + 7 + 1/p < 3.
8(1 20pp 17:) > 1/2, and co 1/6. This completes the proof.
F.2.1 PROOF OF THEOREM F.2
For all e [T] define the random variable
exp ( - V.) + 7pp log
F. (o'1TT)
+ nr0's )
A log E E
P (=
where S/ is defined as in (11).
Similar as the proof of Theorem D.I, we begin by noticing that
(M'
log E, exp (-A')] = log E M Eg exp y 'Vas - V.) + np log
P (o'((( + n:000
Vy V.
<(1 1 27pp - 40 40²n)) log Exapat
exp
7(1
24p - -022)))
PM (o
+ 2np log EM
exp
log
(o'
+ 40
2 7/ log EM Eg
exp
SMM
(34)
4
which is due to Jensen's 's inequality. For the first term, abbreviate no 1 27p- 40 and consider ass == (V. VMs)/YTo- Then by the boundedness of as and Hoeffding's Lemma,
EM (oxpp-(exp(-oo (app--a))] & exp EM-nel [Var] - V/ -V exp
(35)
8-2218 no
7900
The second term can be bounded as in (22):
1 (M'(''TT)
log SM E, exp log
log Eas
B. [B
(1 + p
(of(=')
E EM E. Di (IM (-17"), (*(+)()) + P.
(36)
2
and the third term can be bounded by Lemma D.3 (similar to (14)):
1
1
R (0')- - R((O)1
log EM -
E,
exp
402 6/1
log EM E,
exp
80²
$ log pp E,
[ - (1
-
D²
R M (o')
(O') -Ro))R(((0)) (o)))
(37)
<-(1- D2 1802 D² E.
(od))
R¹
Plugging (35), (36), and (37) into (34) gives
V. E EM [Vr]
1
log E, [exp (-A9)]
8
+ 27p
EM E, (P MP (-1x") F (-1x'))) -p
2
(38)
+ 202 7) (1-c-1 -D2/100))) DD² Es u E, |R M (0') (o')-R'S
R RR*(o')1 (ot)11]]
1
> EMM~ne [y -V, - -VM) + co Errir]
8y210 20
32

---

Under review as a conference paper at ICLR 2023
On the other hand, by Lemma B.2, we have with probability at least 6/2 that
A + 1og(2/6) log E, exp (-A')].
(39)
remains bound Di= A. By the update rule (31) and telescoping argument similar to (16), we have
PM (o'( -V V.) + Mp log (of + nr
Σ A
log EM x² exp
Σ
The following argument is almost the same as the argument we make to bound (24). Fix M Ma that covers M¹* and VM V. 2p. We bound the following moment generating function
1
E
exp
A²
E 7 (V - V.) 7p log Par(o'(xT)) + 1/:5%1 (-(o-(ar))
BM- exp
T
P (M
Mo exp
(VM - V.) + 7p log
+ 11,
p. (o'
T
<xxp (2T |Mol
exp (
<exp (2T p+ T pm:) |Mol
where the first inequality is because μ (M) = 1/ Mol. the second inequality is due to i.M > F and the last inequality follows from the same argument as (26): by Lemma D.3 we have E ( o'] & exp(π)P) and applying this inequality recursively yields the desired result.
Therefore, with least with probability 8/2.
Σ
< log Mol + T2 + 21t.) + 1og((/))..
(40)
Summing (38) over / E [T]. then taking union of (40) and (39) establish the theorem.
F.3 BOUNDING PSC BY HELLINGER DECOUPLING COEFFICIENT
The Hellinger decoupling coefficient is introduced by Agarwal & Zhang (2022a) as a structural condition for the sample efficiency of the MOPS algorithm.
Definition F44 (Hellinger decoupling coefficient). Given E (0, 1), > 0, the coefficient dep" 8.a (M, M,, is the smallest positive number dh > O such that for all μ A(M),
EM~ E M.nM [QM (sp, an) Th V.M.. ($n+1)
nh R. M. D (P-M ((8hhaa), P (-18h an)) RM (s) R. (sk. and (1) + c.
The Hellinger decoupling coefficient dep is defined as
(1-0)/a
H
(M, ==
dep k. (M, MMMM
H
We remark that the main difference between the PSC and the Hellinger decoupling coefficient is that, the Hellinger decoupling coefficient is defined in terms of Bellman errors and Hellinger distances within each layer e [H] separately, whereas the PSC defined in terms of the overall value function and Hellinger distances of the entire observable (o, r).
33

---

Under review as a conference paper at ICLR 2023
The following result shows that the PSC can be upper bounded by the Hellinger decoupling coeffi- cient, and thus is slightly more general definition ?
?
Proposition F.5 (Bounding PSC by Hellinger decoupling coefficient). For any (0, 1), we have
o/(1-o)
(1 (1-a)
22HH dep (M, (M,M.E) M.E)
psc, (M, H inf e=0
+ +
Proof. Fix M, M M, and (0, 1). Consider
Ah, (M, == D [P (-1s); an), Ph (-1sh: an) Rij (sh, and - Rih (sh, an)
By the definition of DRL and Lemma B.4, we have for any f E [H] that
E M aad [Ansnnan (M, M) & 2D (M(T.), M(Tre))
Fix s e 0 and and write d¹ = dep h. (M, M,).. For any μ A(M), we have
Exsa pM (M (TM) - PM (TTA))
H
E EM Ma O (sh, an) - -Th - Vitt (snt1)
ch EM B. Ahionia (M, (M) + HE
(c*) (2EM, DiL
+ He
< <yEM, DRL (M(TM)) M(TMM))] ((Tre)) (1-a) (11-)) 2all
a/(1-a)
Σ
(d)aiil-a) + He
7
h-1
2a (M,, a/(1-a)
=YMEM M DiL (M(TMr) + a1-a)/1
Hs,
where the last inequality is due the fact that for x, y 2 a (0, 1),
7 + (1-10) - a) (ally a/(1-a)
all a/(1-a) /f/llaa)
2a aH
7
+ a) H
by weighted AM-GM inequality.
F.4 PROOF OF PROPOSITION E.3
Our overall argument is to bound the DEC by strong duality and the probability matching argument (similar as Foster et al. (2021, Section 4.2)), after which we show that the resulting quantity is related nicely to the PSC.
In the following, we denote psc, (M) := supTTem (M, M). By definition, it suffices to bound (MM, μi) for any fixed ji E A (M). We have
dec( dec(M.
inf sup Bar (TM) ( (MM PEA(II) MeM
We remark that Agarwal & Zhang (2022a) defines the Hellinger decoupling coefficient in terms of general function Tgen (h, μ1) that maps follows sample from μ4, i.c. Tgea p)) FM, M μ.. For the general case that Tgen (h, p1) 1 M.h. M the corresponding Hellinger decoupling coefficient can he bounded by ese (Definition K.23), by same argument.
((M)
E (TT), and we only present the version that Tgen (hi, ())
34

---

Under review as a conference paper at ICLR 2023
Algorithm 6 OMLE
1: Input: Parameter 3 > 0.
2: Initialize confidence set M = M.
3: for (== 1,..., do
4: Compute (M' x²) arg ME. mell {M((T) (T).
5: Execute x' and observe r' (d',r') r').
6: Update confidence set with (28):
M
MeM: L++1(M) x max (M4 -8}.
inf (IA( (M)(M)
sup E BM M. I (TM) (T) ( ((). (x))
sup inf MM [ (TM) PM (T) 7 (M M()).
MEA(M) (EA(II)
where the last equality follows by strong duality (Theorem B.1).
Now, fix any E A(M), we pick E (lII) by probability matching: π ~ p is equal in distribution ग TM where M' a an independent copy of M. For this choice of p, the quantity inside the sup-inf above is
EM E M
[ pd (TM) - (TM) - Di (M M (TM())]
57 D (M((M)))))) M(TT)))
= -EM~p BT -TJ
f (TN)) - -3M((TT))
6
+ EM M
(TT) - -jad -fa (TT.)
7
(M ( ((TM))
6
5y
EM ET
PM (TTs)) - (TM)
Du M(Tw)))
EM u E TT
f (TTS.) - (TTM
7
Di (M(())))))) M, M(TM)))
6
(8))
E EM-H, M Mu M~
(M (TM) TM (TM)
? (M ( M(TM)))
6
<B E. po (M, (pM
EM EM-
H 1D (M(L))
2 (M(()) ", (M())
(181
psc psc (M)) + 2(H 1)
Above, (i) uses the fact that f (x is equal in distribution to ff (TT) (since M ~ 1a and M' μ4:; (ii) uses Lemma B.7 and the fact that 5Dr, (M (TMr), M(TM)) > Dia, (M (T ((TM))) that is due to Lemma B.6; (iii) uses the inequality /H + Ix & Z + 3(#+1) for any R. Finally, 27
by the arbitrariness of Іr E AlI)), we have shown that dec, & p (M) M)+ 2(H + 1)/7. This the desired result.
G PROOFS FOR SECTION E.2
G.1 ALGORITHM OMLE
In this section, we present the Algorithm OMLE (Algorithm 6), and then state the basic guarantees of its confidence sets, follows.
35

---

Under review as a conference paper at ICLR 2023
Theorem G.1 (Guarantee of MLE). By choosing 3 > 3 2T) + 3lg(11/8). Algorithm achieves the following with probability at least - 6: for all t E [T]. M E M', and it holds that
Σ (MT)
23 + (est(M, 6 (1/0) 43,
M M'.
Proof of Theorem G.1
The proof of Theorem G.1 is mainly based on the following lemma.
Lemma G.2. Fix p > With probability at least 6, it holds that for all E [T] and M e M.
Σ Dir (M*) M(*")) 2(C((M)) (.(M)) + 6 6log ((M, + 8Tp.
Now, we can take p that attains est(M. 2T) and apply Lemma G.2. Conditional on the success of Lemma G.2, it holds that for all E [T] and M M.
(M( (MM)) & ( 27) + + log((16).
Therefore, our choice of 3 is enough to ensure that M e M Then, for M e M we have
(
M'EM L((M') 3 > Lx(M*) - B.
max
Applying Lemma G.2 again completes the proof.
The proof of Lemma G.2 is mostly direct adaption of the proof of Theorem D.I and Theorem D.8. Proof of Lemma G.2 For simplicity, we denote (o)o))) = PM,, (o) and (o) = (o).).
We pick p-optimistic covering (P, Mo) of M such that |Mal p) Recall that the MLE functional defined as
C(M) =
log M.M.x P.M."((')) (0") (o')-rr' (F)))--RM((0))
For M E MM, we consider
P. (o'lx')))
C, log (=
84 == |r' - R 2
- (
where the definition of agrees with (11). We first show that with probability at least 6, for all M MM and E [T].
E1-E, E.
V
PM (T*)
Pa (o m)
[[ - ( Σ Ei 3 3log
-
Mul
(41)
This is because by Lemma B.2, it holds that with probability at least 1 for all t [T] and M Mo.
1 ]
Σ
Ev + log((MMl/8) >
log E,
cxp
s 3
3
sct
Further,
1
2
1
pom (o*l
}
1
log Eg
exp
3
log E.
exp
2
log
p. ()*
log E. [x[exp (81))
1
PoM ((=|
1
E,
R R (o*) R M (09)
3
36

---

Under review as a conference paper at ICLR 2023
where the second inequality is due to the fact that log and Lemma D.3 (with o² 1/4).
Hence (41) is proven.
Mo. Fix M E M, there is Mo Mo such that M is covered by Mo (i.e. R (o) R (o)]| p and PMo PM for all x).
Now condition the success of (41) for all Mo
Notice that Eoeo (olx)) & + p², and therefore term in (41) (plug Mo) can be lower bounded
[MMo 1PM (-1m), p² Then first
P.o (+*) PP (* 1T)
E.
2 [. (1'T",,
by (22). For the second term, by the fact that R E [0, 1] and R (o R (0)] & we have
E. [R'('") R RR"(0") (0)) > E. R (o") - RM (R'(((0')) (0')]2] 2p.
Similarly, 80. 7 8is - 2p, and hence - Exet Eoo & (M') (MM 2Tp, which completes the proof.
G.2 PROOF OF THEOREM E.5
In the following, we show the following general result. Theorem G.3 (Full version of Theorem E.5). Choosing 3 > 3est(M, + llo((16)) 1. with probability at least 8, Algoritlum 6 achieves
RegDM & inf (T 720
4y
Especially, when M finite, we can take 8 3 llg{[MM]/8 (because est(M, 27) < log MM), and Theorem G.3 implies Theorem E.5 directly.
Proof of Theorem G.3 Condition on the success of Theorem G.I. Then, fort E [T]. it holds that M E M Therefore, by the choice of (M', it holds that fM (T') > fM (TT-). Then,
T
RegDM
M (TM-)) - - (77)
x
M (7t))
pa (
T
MM (T²') - MM -x²)(()))
7
max Σ (M M, ( v
T
T
[E[T"]
bounded by mleec,,
Σ
(M (M (MM.)))) M (TAS.)
+
max
EE|T
bounded by 4
T mlec,, (M, M² 4y.8.
Taking inf completes the proof.
G.3 RELATIONSHIP BETWEEN PSC AND MLEC
The MLEC resembles the PSC in that both control certain decoupling error between a family of models and their optimal policies. The main difference is that the MLEC concerns any sequence of models whereas the PSC concerns any distribution of models. Intuitively, the sequential nature of the MLEC makes it stronger requirement than the PSC.
37

---

Under review as a conference paper at ICLR 2023
Formally, show that low MLEC with slightly modified definition of MLEC (where the māX is replaced by the average; cf. (42)) indeed implies low PSC. Note that the modified MLEC defined in (42) is larger than the MLEC defined in Definition E.4; however, in most concrete applications they can be bounded by the same upper bounds. We present Definition E,4 as the main definition of MLEC in order capture generic classes of problems such RL with low Bellman- Eluder dimensions or (more generally) low-Eluder Eluder-dimension Bellman representations (Proposi- tion K.7).
Proposition G.4 (Bounding PSC by modified MLEC), Consider the following modified MLEC:
K
mle,,,,(M,MM.))) == sup JMM
pM (TTSe)) ( (T
K
(42)
K
7
Σ
Σ
Rr. (M( M (TAA.)))
K
bEc
Then holds that
mlec,,, [ (M, + (7 1)V
2 log [I| MM +
psc, (M,
E inf Kzl
K
Proof of Proposition G.4 Fix a K and μ A(M). We first prove the bound in terms
of [II]. The proof uses the probabilistic method to establish the desired deterministic bound. We
draw K i.id samples M ..... .M* from μ. and we write ğ Unif([ .M*)). Then with probability at least 1 - (|i1) + 1)o, the following holds simultancously:
2 log(118)
(EM-H- BM- [ (TM) 1. (TM))
K
log(1/8)
(EM-R - EM- DDL (M()), M()) V\
VT E II.
K
Therefore, with probability at least 1 (ITT) + 1)6 (over the randommess of (t), we have EM~DEM'~N (TTM) (M - DRu (M(TMM) M(TM))
2 l (1/(1/))
< EMM-BEMM~R (TT)) -x - -D. (.Mii..MMMMM (M(M)) (TT()) (1 (1+
K
K
K
pM (TTN) (M
7
Σ
D (M M
K2
R=1
2 2log(1/0)
V
K
2 2lg((188)
Emlo,, (M, M) + (1+ (1+7) V
K
In particular, for any 8 < [II), the above holds with positive probability, and thus there exists
one ğ such that the above holds. Taking t 1/(1 [III) on the right-hand side and supremum over E A(M) on the left-hand side, we get
log( III +1)
psc,, & mlec,, (M, M) (1+0)) V
K
The bound in term of M follows analogously, by noticing that with probability at least - (IM)+ + 1)6, the following holds simultaneously:
(EM~μ - EM [ 1 (TTM - MM (TTS)) -
2 llog(1/8)
&
K
2og((1/0) K
(BAr<p EM w Diu (M(T)) M(TM))) < and repeating the same argument as above.
38

---

Under review as a conference paper at ICLR 2023
Algorithm 7 Exploartive E2D with Tempered Aggregation (EXPLORATIVE E2D)
Input: Parameter 0; Learning rate 1/p E (0, 2)) 1 > O.
1: Initialize 1 - Uni
2: for = I'..., do
3: Set (Pexp, Pout) arg min (ea Vi pae,, (Pexps Pout), where V is defined in (6).
4: Sample nO' Peep: Execute x' and observe (o'; r.).
5: Update randomized model estimator by Tempered Aggregation:
(M) aM (MM exp 7pp log P.M.'' (o') - n |1' R - (0)))
(43)
Output: Policy Pout $ Er- Pout
H PROOFS FOR SECTION 4.1
We describe the full EXPLORATIVE E2D algorithm in Algorithm 7.
H.1 PROOF OF THEOREM 5
We first show that Algorithm achieves the following:
fM ( - Exr-pous | (T)) < (M) + +7 EStRL
(
(44)
where EstRI. denotes the following online estimation error (cf. (18)):
EstaL
Σ Bat-penn Plep Exie-pe (M (x'), M (z'))
We have
E pous
p (TT.-) ff (771)
E Ex-ptn Un((TT)) - [M((T)] BBer Ep (RL((M())
F Ex B (Mr)))
7.
Pimpin [fAr(TT)) fx((=)] - BBxrpiin E Ei (M))
sup MEM
Ext E B (m') (7
Die pac, (Wexp: Poue)
+y EstRI.
inf (Pexpp Pout (ea(1))
(152)
edec (1)) +7
EstRI. & T (Mec.(M) + + EsTRI.
Above, (i) follows by the realizability assumption M e M; (ii) follows by definition of the risk Pra"
pac.y (ef. (6)) as well as the fact that (Pesp= Pout) minimizes Vn pae,, (..)) in Algorithm 7; (iii) follows by definition of edec, (M, n²)). Dividing both sides by T proves (44).
39

---

Under review as a conference paper at ICLR 2023
Combining (44) with the online estimation guarantee of Tempered Aggregation (Corollary D.2) completes the proof.
Theorem 5 can be extended to the more general case with infinite model classes. Combining (44) with Proposition D.6, we can establish the following general guarantee of EXPLORATIVE E2D WITH COVERING.
Theorem H.1 (EXPLORATIVE E2D WITH COVERING). Suppose model class M admits a p- optimistic cover Mo)) Then, Algorithm 7 with the Tempered Aggregation subroutine (3) replaced by by (19) with 7pp n) 1/3 and μ Unif achieves the following with probability at least 6:
SubOpt & edec, (M) + 107
Dog MMol + Tp + 2 log(2/5))
T
By tuning > 0, with probability at least - 6, Algorithm 7 achieves
SubOpt < inf fedec, (M) + lest (M,T) + log( (o801/ 720
where C a universal constant.
H.2 PROOF OF PROPOSITION 6
We present the full version of Proposition 6 here, and then provide its proof, which is a generalization of Foster et al. (2021, Theorem 3.2).
Proposition H.2 (PAC lower bound). Consider model class M and T > 1 a fixed integer. Define pM (olm)
C(T) == 21 log(2T A ((M)) and E : ककगा Then we can assign each model M E M with a reward distribution (with E [-2, almost surely), such that for any algorithm 2, there exists a model M E M for which
V(M) == 3 M.PM, M sup (ala))
1 max sup edec, M),
E M SubOpt]
6 7=0 MEM
where we define g M (T) == fM (TM) - fM (x) and the localization
M = { ME M: (T) nMd (T))
& (T)
Vx II
(45)
Proof. First, we need to specify the reward distribution for each M M, given its mean reward function Rd O - [0, 1) conditional on the observation o, we let (r") be random vector, with each entry nh independently sampled from
IPM (MM (M--210)
3
(O)
PM
n5th
200)
1
R (o) +
4
2
4
2
Then a simple calculation gives Di
R (o). R (0)
<
R (0)
RR (o)
Therefore, by the
fact that (r²) are mutually independent conditional on O we have
D (RM(O) RM (0)) = II (1-2 2 Dj (R (0). R 2
RT0)) (0)) > II 1
1
R (o) - R (0)))
1
4
(- log( 4/3)
R M (0) R (o) (2) > 1 log(43333
M (0) 2 2
cxp
M (o)
R
where the second inequality is because - x/4 20 exp( - log(4/3)) for all x E [0. 1]. Therefore, by Lemma B.4,
D (M(T), M(T) & 3DR (M), (T)) + 21E p pMr (m)
D3 (R), [T)]
3Df (=), (T) + 3 (.)pPM())
R (0) R
(0)
2
$ 3Dg (M(x), M())
40

---

Under review as a conference paper at ICLR 2023
Next, suppose that algorithm a is given by rules p { peopl 11)) }-) U Poout 1.),, where Pexp (-13/(-11) (IT) is the rule of interaction 1-th step (given H( the history before t- th step), and Pout (-126000 E A(TI is the rule of the output policy. For M M, we define
(-1 ((
PMpxx = EMa
(t) Pexp
E AII),
PM,out = E. [Pout (-7?")] E A(II,,
T
where P.M. is the probability distribution induced by 2 when interacting with M. Notice that EM [SubOpt]] = Em- [g (T)]
Let us abbreviate edec == SuPMEM edocy (M)) M), and let e .M attains the supremum. Then
E Ex-P [ (TM) - P (MT) - Px DRL (M(T), > edec.
sup MeMy (M)
Let M M attain the supremum above. Then have
E Bn-Ps out [ 2 B.E cap
? -.B--s [D (M(T), M())) +edec. Di... (M(T), (M(T) todec 3 todec
3
Recall from the definition of MM (M) that و MM (T) ( & for all Hence, by Lemma B.3, it holds that
E Bn-PM
1M - (TT( BE-PP (MM(TT (
$ 1 88 (ERnpT ous gM + (gM(TT
+ Ex (T) (T)
D (pMaa (pM.a.pot..a)
< 4= (pM.)) + E E
(T)((T) + g (
En En (gM( + gDو (T) 1):
which implies
Eg- (x)] + Eggpp
(T)
P Psr [oM + P
Es (pM.a MM
g (T)
Ba-Pst
Pzr.ou
e
DH
Furthermore, by the subadditivity of the squared Hellinger distance (Foster al., 2021, Lemma A.13), we have
T CCr
Di (p..a p.M.a))
Σ
E M
D
CTT
E
D (M (T), M (=))]
where Cr : 28 (log(2I) 2T)) log (V())) as in the proof of Foster et al. (2021, Theorem 3.2). As long as 7s & 7, holds that
Ex-Py [g (T)] + E8, E g (T)
> edec.
This completes the proof.
H.3 PROOF OF PROPOSITION 7
Fix a j ((M), and we take
(Dexp Pout) :
arg
sup
E Err [ (M(SM)) - [T)(
(Pexp:Pout (EA(M) MEM
E Er Paesp ExAZ (M. M(T))
41

---

Under review as a conference paper at ICLR 2023
Then consider aPexp + (1 - Pout- By definition,
dcc(M,
& sup Ex- (TM( - (x)] -Bnr M-H (M)
(TM)
MEM
(a (aBx~Jon
- gM (M((1) (T)] - -a Taaop M - Diu (M) M())]
sup MeM
(1 (1-0) [-) [P (TM) - lMM (T)] - 7(1 - ( F Pon BM -p (M()), (M (+))] }
& sup {a +a+10 (1 - (1)a))Br-a a)) (MM(TT) - (M - a B ByBBr-Peny Pcp
MM [Rr (M), (T)))
MEM
=a + (1 a) edecas/(1-a)) (M
H.3.1 ADDITIONAL DISCUSSIONS ON BOUNDING DEC BY EDEC
Here argue that, for classes with low EDEC, obtaining PAC sample complexity through the implied DEC bound is in general worse than the bound obtained by the EDEC bound directly.
Consider any model class M with edec.(MM) & d/y, where is some dimension-like complexity measure. Using the EXPLORATIVE E2D algorithm, by Theorem 5, the suboptimality of the output policy scales as
pM (TM.) B [fM
edec, (M) 10 log((IM)/0) /8)
T
$ d + log(l $
dlog([MM/8) /6)
T
where the last inequality follows by choosing the optimal 7 > 0. This implies PAC sample complexity d d'log([M)) /0)/=² for finding an E near-optimal policy.
By contrast, suppose
algorithm designed for low DEC problems (such as E2D-TA). To first bound the DEC by the EDEC, by Proposition 7, we have
(a a + (1 (1- (1-a)² a)² d
(e) < inf {a + (1 ())dec < inf a>0
$
as0
ya
Then, using the E2D-TA algorithm, by Theorem and the online-to-batch conversion, the subopti- mality of the average policy scales as
Regdm T
Σ far (TT-) - -Eycap (x*))
T
< dec, (M) 10 2log([MM10)
T
d 7 log(LM]/0) \
(
[dlog([M] /8) 1/3
T
where the last inequality follows by choosing the optimal 7 > 0. This implies a PAC sample complexity d dloo([/M)/8 /8)/e" /e3 for finding an e near-optimal policy, which is 1/s factor worse than that obtained from the EDEC directly. Note that this 1/e3 rate is the same as obtained from the standard explore-then-comet them- conversion from PAC algorithms with sample complexity 1/e² to no-regret algorithms.
We remark that the same calculations above also hold in general for problems with odec..(M) x 1/78 (when only highlighting dependence on 7) for some / > O. In that case, the EDEC yields PAC sample complexity (1/e) whereas the implied DEC bound only yields a slightly worse d+2
(1/e) # sample complexity.
42

---

Under review as a conference paper at ICLR 2023
H.4 EXAMPLE: EDEC LOWER BOUND FOR TABULAR MDPS
In this section, we follow Domingues et al. (2021); Foster et al. (2021) to construct a class of tabular MDPs whose (localized) EDEC has a desired lower bound, and hence establish a Ω (HSA/=") lower bound of sample complexity for PAC learning in tabular MDPs, recovering the result of Domingues et al. (2021).
Proposition H.3 (EDEC lower bound for tabular MDPs), There exists M class of MDPs with > states, > actions, horizon > 2 (S) and the same reward function, such that
HSA
sup edec, (M (M), M) 2 er min MeM
for all 7. > such that E E c2HSA/n, where C1, C2 are two universal constants. As a corollary, applying the PAC lower bound in EDEC (Proposition H.2), we have that for any algorithm Q that interacts with the environment for T episodes,
sup E (SubOpt] > co min ( 1, T MEM
HSA
where is universal constant.
Proposition H.3 implies a sample complexity lower bound of 52 (HSA/s²² for learning e-optimal policy in tabular MDPs. This simple example illustrates the power of edec as a lower bound for PAC learning, analogously to the DEC for no-regret learning.
Moreover, notice that all models in M have the same reward function (denote it by R), hence for this class M holds that
edec, (M). & rfdec, (M (P),P)
(46)
for all M (P, M. Combining this fact with Proposition H.3 gives lower bound of RFDEC of M, and hence we can also obtain a sample complexity lower bound for reward free learning in tabular MDPs.
Proof. Without loss of generality, we assume that = 2 + and let S = 2". We also write A' A H' H H/2.
Fix a A E (0, 31. we consider M the class MDPs described as follows.
1. The state space S Stree L (8), where Stree a binary tree level n + (hence |Steel 2n+1 1), and sg, sg are auxiliary nodes. Let so the root of Street and S' be the set of leaves of Stree (hence |S"| = 2*).
2. Each episode has horizon H.
3. The reward function is fixed and known: arriving at se emits reward 1, and at all other states the reward is O.
4. For ht* E H' := [n+11 H3. e S', e [A'], the transition dynamic of M Ma is defined as follows:
The initial state is always 80-
At a node Stree such that is not leaf of Stree there are two available actions left and right, with left leads to the left children of s and right leads to the right children of s.
At leaf S', there are A actions: wait, 1.... A-1 1. The dynamic of M Ma E M at s is given by: PM (s|s, wait) = 1, and for a [A'] h e [H]
PM ( (,) = + 1 (h h s= s=='',a==')
P/ (sels,a)
43

---

Under review as a conference paper at ICLR 2023
The state sa always transits to sg, and Beg is the absorbing state (i.e. P(selss:)) 1, P(salse, 1).
Let M be the MDP model with the same transition dynamic and reward function as above, except that for all h [H], 8", a [A'] it holds PM (søls,a) PA (sgls,a) 2' Note that M does not depend on A. We then define
M = {M) U (MMaaaa (4, (, e H' S' [A]].
Before lower bounding (MM-, M), we make some preparations. Define
Vx (h, s, a) = p.M.T (sh. = 8, a, = a), V(h,s,a) E H' x S' x [A'].
Note that due to the structure of M, the events Ab,sa == (8h s, = a} are disjoint for (h, s. a) H' x S' x [A']; therefore,
Σ
NEW aE|A|
Furthermore, for M = Mh.s.a E _ we have
Di (MT)). = IpM (sn = s, on = a)Di (- a), PN PM (-1s,a)
because ((T and (()) only differs at the conditional probability of s1+1lsh 8, 0n = a. Therefore, due to the fact that DH (PM PP) 3, we have
DH (Bern(} + A), Bern()) &
D (M)),, & 32 a,
Now, that for Pexp: Pout (TT) and M E M', we have
Ea-pont [ (TTM
(M (T)] - TTE Poxp [Di (M(T), M(T))
1
+ A Eyr- Pout
+ APM. a²)
7IB DH (M(T),
2
2
> A1 - EETT Uh' - - A E s ,²))
Therefore, define
Ulpexp (1i, 8, = EgT Pescp [V (h, s, a)],
P/pon (h, 8, a) = EET= (v,
Then, for any fixed Pexp, Pout E A(II), by the fact that
Σ
{uranp (h,, a) + 3y pou (,) & 1 374
NE "ES",aEAA
we know that there exists (N', 8,, ( H'' x x [A'] such that
1 3^A H'S'A'
V/pup (h',
3y Poue (h' s'a' <
Then we can consider M' = MM a's and
E (MMM) (M (T)) - = D (M(T), (+))]
sup MEM'
E Pout pMll' (TTrr) - PPM ( - -.Ex [D] ((+))
A Pexp (0',8',a')) 37 Aum (K',8' s'a')
1 3
A A
H'S
By the arbitrariness of Pexp: Pout A(TI), we derive that
1 3yA H'S'A' A'
odec M
44

---

Under review as a conference paper at ICLR 2023
Algorithm 8 REWARD-FRRE E2D
Input:
Parameters 7) 1/3, y 0; prior distribution μ A(P).
2: // Exploration phase
for I,..., do
V 4: Set Poxp = arg min Pexp sup NER 1f,y (Pexp: R), where (cf. (7))
1f,7 (Pexp: R) = inf sup P Pous p (TP,R) - (P. - - pp (i(((()) Pout
5: Sample n² ~ Pixp Execute r' and observe o'.
6: Compute + E (PP) by Tempered Aggregation with observations only:
(P) (P) exp (1) log Pr (dd)
(47)
7: // Planning phuse
8: Input: R' E R
9: fort = I....,T do
10: Compute
Pout (R²) == arg min sup EST -pot
(TP, _p. (P)) - BBrrpin Epr (((P())
Pout (TT) PEP
11: Output: (ot) - Et= (R)).
Also, by definition, it holds that M (M) MAI3 V(M=)
-T-
Therefore, given
T > and algorithm 21, we set Co = 211, A = min {
H'S' 12CoT
7.7 COTA, then applying
V
Proposition H.2 to M gives a M M such that
1 3>
A
H'S'A A'
M.A >
A
3 Co min
1,
6
H'S'A
24
T
where the second inequality is due to the fact that tion, and op is a universal constant.
1+37A H'A
<
which follows from simple calcula-
On the other hand, we can similarly provide lower bound of edec(M, M) for the model class M
Usio MA: For any given > 0, we can take غ = A = min
H'S'A' d'
j. and then
3
127
(M), > edec, (MA, A A. 1 1+4
1 H'S
min
A'S'A
4
4
3
12y
I PROOFS FOR SECTION 4.2
I.1 ALGORITIM REWARD-FREE E2D
Algorithm presents a slightly more general version of the REWARD-FREE E2D algorithm where allow [P] to be possibly infinite. The algorithm described in Section 4.2 is special case of Al- gorithm 8 with [P] < oo and we pick the uniform prior 2 Uni
More generally, just Algorithm 7, Algorithm 8 can also apply the case when M only admits finite optimistic covering. Its guarantee in this setting is stated as follows.
Theorem I.1 (REWARD- FREE E2D). Given a p-optimistic cover (P, (P.Po) of P. we can replace the subroutine (47) Algorithm 8 with
(P) xcp μ exp (nlog (o'))
(48)
Here avoid confusion, the in the superscript (cf. (45)) the subseript.
45

---

Under review as a conference paper at ICLR 2023
and let 1 1/2, n² Unif(Po), then Algorithm 8 achieves the following with probability at least 1- 6:
SubOpt, & (M) + 27 T
[log (Pol Tp log(2/6))
By tuning y 0, with probability least 6, Algorithm 8 achieves the following:
SubOpt,r & inf (M) + 7 [est(P,7) + log(1))100000 (1/8)]
920
1.2 PROOF OF THEOREM 9 AND THEOREM 1.1
For R. E R, Pexp: Pout E A(II) we consider the function
V'(eep: R: Pout, P) Bor-pout {
(P. (T)] -Ppppppp Ex Pexep [P((((T))
Then the policy played by Algorithm 8 at step / is exactly
VuL Pexp arg min sup Hf,y (Pexps R) arg min sup inf A(II) RER
sup V (Pexp: R; Pouts P).
D(T)) RER Po PEP
Therefore, for any R' R. using the definition of the infs and sups in the risks, we have that
ridec, > rfdec,
sup VH' (Pexp: R) i VH (pexp: R*)
RER
inf sup (Pexpo Rt: :outt
POnEA(M)) PEP
i sup (''pepp Ri; pome (I))), > v' ('eepp R : (R²), (o'), P*).
PEP
Therefore, for any R and the associated M (P", R*), we have
Ex-pi (n))
fM (TM. fM (T)) < rfdec,, (M) + B E Pt [t)(
Taking average over E [I'l and taking supremum over Rº E R on the left-hand side, we get
{ p (TP. ET [PPt. (x) Ffdec,(M) + 7- Esta
sup ReR
(49)
where
T Σ
Esta
E P Ex-ppi
(T),
Note that (52) holds regardless of the subroutine ((47) or (48)) Therefore, it remains to bound Estn for (47) and (48).
When |P| oo, Corollary D.2 implies that subroutine (47) (agrees with (3) with n 0 and 7p 17)
achieves with probability at least 5 that
EstR & - log([P)//))
This proves Theorem 9.
Similarly, when a p-optimistic covering (P, Po) is given, Theorem D.8 implies that: subroutine (48)
(agrees with (19) with 77 and 7p 17) achieves with probability at least 8 that
EstR
[log (Pol Tp (loo((2())
17
This completes the proof of Theorem I.1.
46

---

Under review as a conference paper at ICLR 2023
1.3 PROOF OF PROPOSITION 10
We state and prove the formal version of Proposition 10 as follows.
Proposition I.2 (Reward-free lower bound). Consider model class M P x R and T 1 fixed integer. Define V (MM, C(T) and by as in Proposition H.2. Then for any algorithm 2 that
returns a mapping Pout R - (TT) after T episodes, there exists a model P E P for which [ [n]
E.P (SubOpt.r)
sup PPP RER
Begout (R)
maxsup rfdec,, (M (M) 720 PEP
(P),
where the localization is defined as (P) P (P) R, where
Pe (P) | p: ( g ((()))
E, VT V RE
(50)
and g (R) PP. (T)) ( for any (P, R x) Xx IT.
(T)
Proof. Suppose that algorithm is given by rules p = { pexpl 11) t=1 (Poutl (-1-), where (t)
Pexp (-1((tt)))) E A(II) is the rule of interaction at t-th step with H((+1) the history before t-th step, and Pour (-))(T))-)) R - (III) is the rule of outputting the policy given reward. Let Ip..a refers to the distribution (of H()) induced by the exploration phase of A under transition P.
For any PE E .M and R R. we define
Pexp P) = EP
Σ
(c) Pexp
(-176(-11) E A(II,, Pout (P, R) = EP.a
Pout (177 .R) A(I).
T
Notice that EP PP. (TP.
E Exou Powes (2) (P.RR
E E (P.R) ((T)..
Let us abbreviate rfdec = supper rfdoe, (M of (P), P), and let P e P attain the supremum. Plug
poop): in Pexp = Pexp P)) and by definition of rfdec,, (which considers inf pnmp ) we have
sup
inf RER Pout E (II)
sup Peppir((P)
E Ppmt [ (Tp.R) ff. (PP.R((T))) - -E xupop
D ((T)). rfdec.
Let R R attain the supremum above, and plug in Pout Pout (P, Rt and by definition of the above (which considers infp...) ) we have
E Ba (P.)) [ (mp.n) (P)) yIE Poup (P) T
D ((mm).((m)) > rfdec.
sup
PEP (P)
Let P E prour (P) attain the supremum above. Then we have
E
Exppon (P.R) R) | P. (T)) >7 7- E ID] (P((),,(( P(=))]
rfdec.
Similar to the proof of Proposition H.2, it holds that
[9 P. (T)] + E
g (
B (P.R)
Bx Pome (P,R)
3 3 xm Pone (P.) [ P.R (P(((T)]
+ E x~ Pone
(F,1)
(P(((T))
3 DD (pp.ot pp..).
and
Di (pP... pP.))
CTT STT..Er-eerf
[Di (P(T), P(T))
where we recall that ppP,3 refers to the distribution induced by the exploration phase of 2. Requiring 8C & gives
1
E (P. 1)) ( E Bx Pmmn (P,8)
rfdec,
which completes the proof.
47

---

Under review as a conference paper at ICLR 2023
1.4 TRACTABLE UPPER BOUND OF REDEC
In the following, we provide a more intuitive upper bound of rfdec useful for later proofs, which we call rrec:
[ (T)) - (P)
Irec, (M,Ti =
inf PEA(P) PEP, n
sup
Bp R
Proposition L.3, Suppose that II is finite. Then
(idec,(M,7) & 21rec
Proof. Fix any jı E A(P). By definition,
rfdeo, (M. (
inf
sup sup inf E Brrpon [fP.R(TP,.)) - -pp. [P)
PexpEA(II) RER yEa (MM(M) EA(II)
p.p [DT((((T)
inf
sup sup inf
Pp--
- Ex Ppna [P.
EA(T) RER (EA(P) PoIIE((T))
Ep- Bi Bp-n -
BBp-niB Pap B B
((T))
(8)
sup ((T) RER NEA(P)
inf
sup
Ep- Ep-plEp-p (P.R((TT.R) - (P.R(TT.R))
Ep- Epr Epp (P. (P.R( R)
>EE u Ba
P EET [D)(((()) P(T))
(Hi)
sup E(II) RER (P)
inf
sup
2E mm
supp
Ep- [PP.((z)) ( (x')
[t'ell
>1p 1ppp-il E Sp Er Peep [DA(P(T)) P(=))
inf sup REP
sup 7'el1
Ep-a (P, - ((
(IT) ((T)) Derp
F Br Br
((((())))((T))]
2
where is due to strong duality Theorem B. in (ii) we upper bound inf p.m. by letting Pout E AIII) be defined by Pout (T)) = p({P TP. T)), and in (iii) we upper bound
Ep-
f F. (TP,TT))) R)
< sup r'll
Ep-p
-
- -P)
EE'= (P.
pP..((TTr.))) - R)
Ep-p [PP.((TT)) (p.
< sup T'elT
Taking inf, over ji E A(P) gives the desired result.
J MODEL-ESTIMATION COEFFICIENT
Define
mnde((,.7
inf Al) PeP,
sup
Ep Mout
DTV (((T),
7B E P(r))
(51)
J.1 ALGORITHM MODEL-EST E2D
48

---

Under review as a conference paper at ICLR 2023
Algorithm 9 Model-EST E2D
Input: Parameters 1) 1/3, y 0; prior distribution je' A(P).
2: for t = 1,..., T, do
3: Set (Pexps Mome) = arg (Ma Je ATT me, y Mout); where
Vi' (Pexp: Hout) =
sup sup Ep- [Dv (P(T), - - - peop Pasp (p(P))) PEP #ell
(((P))))P'(T)))
4: Sample n² Vexp. Execute x' and observe of.
5: Compute 4 (P)) by Tempered Aggregation with observations only:
(P) dpp (P). exp (n log P (df)
6: Compute Hout + > Hout E A(P).
7: Output: P arg minper sup=en Ep Ep-pout Drv (P(T), P(T))
Theorem J.1. Given p-optimistic cover (P, Po) of choose 17 1/2, p² Uniff(Po, then Algorithm achieves the following with probability at least 1 1
D4y (P. max DTV (P(T), & 2mdee, + [og |Pol Tp+ 20-+2log log(2/)))
47
T
Rell
For P P P. E II, Pexp E A(II,, Hout E A(P), we consider the function
V (pexp: Mout; P. Bp- [Dry ((T), 7 -Pe- Epenat (((P)
Then, using the definition of the infs and sups in the risks, have that
mdee, > mMde,,(,,,3), = me, (Pexpp Pout) >
V'(eesp Mouti P, R)
sup PeP,
sup (P'xp Pont: p",
#ell
Pp Drv (P*(T), &E Epinne (T),
sup
#ell
Taking average over t E [T' gives
sup Ep- DrV (P) P(F))
Σ
sup E. #ell
Hom [Dv (P((),,
(52)
#ell
Esth
<mdec, + +
(53)
where
T Estu =
>
Ep E. Etpp [T)(PP(T),P()))
By definition, it holds that
sup E Te
Drv (f(#), <
[WV sup Ep- [Urv (P*(H),
netl
and therefore,
max Drv (P(7), P*(T) Rell
< sup æell
Bp Hout
Drv (P(#),
sup Bp- Drr (P*(
#ell
2 sup Ep Ep-you
(DrV (T), P(=))
mell
49

---

Under review as a conference paper at ICLR 2023
E 22ndee, (M) + 2y EstH
Note that Theorem D.8 implies that: subroutine (48) (agrees with (19) with tr and ?pp 17)
achieves with probability at least - 5 that
Estu & [log (Pol Tp+ 2 22g(2/
17
This completes the proof of Theorem J.1.
K PROOFS FOR SECTION 5
This section provides the proofs for Section 5 along with some additional discussions, organized follows. We begin by presenting some useful intermediate results in Appendix K.1 for prov- ing Proposition 12; The proof of Proposition 12 then follows by combining several statements therein (see Appendix K.2). The proofs of Example 13-15 are provided in Appendix K.3. Ap- pendix K.4 presents some discussions regarding the definition of Bellman representability (com- pared with (Foster et al., 2021)) along with some useful results regarding the complexities of general function classes. Finally, unless otherwise specified, the proofs of all new results in this section are presented in Appendix K.5.
K.1 INTERMEDIATE RESULTS ON BELLMAN REPRESENTABILITY
Complexity measures for general function classes We begin by introducing the concept of de- coupling coefficient for (general) function class, which acts as convenient interface for both bounding the DECs and proving the examples.
Definition K.1 (Decoupling coefficient). Given a function class F c (X RR,, the decoupling coefficient dc(F, (n)) is defined as
[1(())]]
dc(F.n) == sup (EA(FxX)
As examples, the decoupling coefficient can be bounded for linear function classes, and more gener- ally any function class with low Eluder dimension (Russo & Van Roy, 2013) or star number (Foster et al., 2020).
Example K.2. Suppose that there exists à X Rd such that F {fo (0, ((x))())))))) IeE then dc(F,)) & d/(4y).
Definition K.3 (Eluder dimension). The eluder dimension e(F, A) is the maximum of the length of sequence (fi,T),... (Sa, nT) E F x II such that there is A > A, and
(f(m)) A
EI(())) & (A)), j
Vi.
Definition K.4 (Star number). The star number s s(F A) is the maximum of the length of sequence (fimT),.... (fn, Tn) E F such that there is a N > A. and
[((m))=4 A
Σ I & (A)) J#1
Vi.
Example K.5. When FC [-1,)- and 2 it holds that
min [52 cFF A)} log
de(F, 24 inf
More generally, the decoupling coefficient be bounded by the disagreement coefficient intro- duced (Foster et al., 2021, Definition 6.3). The proof of Example K.5 along with some further discussions can be found in Appendix K.4.
50

---

Under review as a conference paper at ICLR 2023
Bounding DEC/EDEC by decoupling coefficient of M We now state main intermediate result for bounding the DEC/EDEC for any M admitting a low-complexity Bellman representation, in the sense of bounded decoupling coefficient.
Proposition K.6 (Bounding DEC/EDEC by decoupling coefficient of Bellman representation), Sup- pose that 9 (g MeMM is Bellman representation of M. For any M M, we define
comp(g .) - max w//12222 6H
(54)
?
and let comp(9,7) :- MaXMeM comp .7)- Then we have for any q > 0 that
(1) If net M,h = TM (the on-policy case), we have dec,(M) & complg, 7) and (MC,,M,," M*) & comp(gM ,7) for all M* e .M.
(2) For 9 with general estimation policies, we have (.ec.,(M) & complg, 7).
Similarly, we show that the MLEC can also be bounded in terms of the Eluder dimension of GM' Proposition K.7. Suppose that G MMMMMME is Bellman representation of M in the on-policy case ( MM = TM for all (h, M)). Then we have for any 7 > 0, E Zoz1 that
[M (g AA + A
x & CHPL2
inf A3D
where C' is an absolute constant.
Bounding RFDEC under strong Bellman representability
We define a strong Bellman repre-
sentation as follows.
Definition K.8 (Strong Bellman representation). Given a pair (M = x R, P), its strong Bellman representation is collection of function classes G ( heam with G. M. II |- 1, 1]} MeM such that:
1. For M R) M, v e IL it holds that M RP,
E
M.n m
Mix (sh, an) - -rh V. (Sh+1)
& 9h
M.F (TT)
For M = R) E M, II, holds that
M.P 9h
(T)
LDD(P(=Tf))) P(mf)))
for some constant L > 1.
Given a strong Bellman representation 9 M, the REDEC of M can be bounded in terms of certain complexity measure of G as follows.
Proposition K.9 (Bounding RFDEC by decoupling coefficient of strong Bellman representation). Suppose G is strong Bellman representation of M. Then for çi A(P),
H
rfdec, (M.F) & 2H max max do ( 7/4HL2)
PEP he[H]
The proof of Proposition K.9 can be found in Appendix K.5.4. For its applications, see Ap- pendix K.3.4.
K.2 PROOF OF PROPOSITION 12
The claims about bounded DEC/EDEC/FFDCC in (1)-(3) follows by combining the bounds in terms of the decoupling coefficients (Proposition K.6(1), Proposition K.6(2), and Proposition K.9) with the bound of decoupling coefficient by the Eluder dimension/star number (Example K.5). Then, the claims about the sample complexities of the E2D algorithms follow by applying Theorem 2, Theo- rem 5, and Theorem 9 and optimizing 7 0, respectively.
51

---

Under review as a conference paper at ICLR 2023
Proposition 12 can be directly extended the more general case with infinite model classes, by using the TEMPERED AGGREGATION WITH COVERING subroutine (19) (and (48) for reward learning) in the corresponding E2D algorithms (see Theorem D.7, Theorem H.1 and Theorem I.1). We summarize this in the following proposition.
Proposition K.10 (Variant of Proposition 12 with covering). Suppose M admits Bellman repre- sentation 9 with low complexity: min(e(gr A), s(g), A))) (d), where (.) contains pos- sibly polylog( A/ factors. Further assume that M and P admits optimistic covers with bounded covering numbers: log.(MM.p)
Ö (dim(MM) and log.N(P: .P) & Ö (dim(P)) for any p O, where dim (M), dim > O and (-) contains possibly polylog(1/p) factors.
factors Then with subrou- tines changed correspondingly to the versions with covering, we have
(1) (No-regret learning) If rest = тM for all M E M (the on-policy case), then Algorithm
E2D-TA achieves RegDM & O(HL/d dim(M)))).
(2) (PAC learning) For any general (T., [ Mell) Algorithm EXPLORATIVE E2D achieves episodes play.
SubOpt < within δ (d di
(3) (Reward-free learning) If G strong Bellman representation. then Algorithm REWARD-
FREE E2D achieves SubOpt,r & & within Ô (d. dim episodes of play.
K.3 PROOF OF EXAMPLES
We first present some definitions and properties preparations. The proofs of Example 13-15 then presented in Appendix K.3.1-K.3.3 for the regret/PAC bounds, and in Appendix K.3.4 for the reward-free bounds.
Definition K.11 (Model-based bilinear class, Jin et al. (2021); Foster et al. (2021)), G is a bilinear Bellman representation of rank if there exists maps Xx(-:-) ) Mx Rd, Wh(:-)) M Rd, such that
M JM (M) (Xa(M: M), W.(M;; M)), 9h
VM, Me
Suppose that G is bilinear with rank d, then by Example K.2.
comp(9 2H L 2H +
7
Similarly, by Proposition K.7 we have mlec,, (M) Ô (2H+
Example K.12 (Bellman error as Bellman representation). For a model class M, its Q-type Bellman error is defined as
M (M) == MM MM' (n)) rh V ( On
M.
Along with n = π and L V2, it gives a Bellman representation of M, which we term as its QBE.
Similarly, we can consider the V-type Bellman error
M (M) M. QM ((s,, an) - M
V,M" Vi (st+1)) VM, M' M M,
9h
where JM ^ AM stands for the policy which executes for the first h - steps, and then follows TMP from the h-th step. Along with Tha = oo Unif(AA and L = /2A, it gives Bellman representation of M, which we term as VBE.
Relation to Model-based Bellman-Eluder dimension Take Q-type Bellman error for example. M'M
(M) corresponds to the roll-in policy æM. Therefore, one can Note that the argument of gh check that
A) = dimpr(Es, II, A),
MEM is the model-induced Bellman residual function class, is the collection of distributions over S x A at h-step induced by policies. Therefore, "( is indeed equivalent to the modell-ased version of the Q-type induul-induced) Bellman Eluder dimension (Jin et al., 2021).
where En. = 1000 M. Th PA V.
M.+
I1 {ah ;=
Tell
52

---

Under review as a conference paper at ICLR 2023
K.3.1 PROOF OF EXAMPLE 13, REGRET BOUND
Clearly, for the tabular MDP model class M of S' states and actions, its estimation complexity
log. = Ô (52 AH) (see Example K.13) and its QBE is bilinear with rank SA. Thus by
the definition of comp in (54) and Example K.2, we have comp(G, = O (SAH /n), and further by Proposition K.6(1) and Proposition K.10, E2D-TA achieves RegDM Ö Ö
regret.
We remark that the same regret bound also holds for MOPS and OMLE, by the PSC bound in Proposition K.6(1) and Proposition K.7 combined with Theorem F.1 and Theorem G.3.
In the following, demonstrate briefly how to construct optimistic covering of the class of tabular MDPs. Without loss of generality, we only cover the class of transition dynamic P.
Example K.13 (Optimistic covering of tabular MDP). Consider M, the class of MDPs with S states, A actions, H steps. Fix f E (0, 1]. and = pf/eHS. For M E M, we compute its P1-optimistic likelihood function as follows: define
(s'ls, = P
TP = P
PM (s)
(55)
and for Markov policy æ, let
T.M. (1,,01,"" ... sH, aH) ToA (81 ( (ails) (s) PPA
(82151, (
... P. (r
H
H-1 I.M (1n41(8haaa).
(PM(ss) (81) I (n(anls)) x
& 1.. Clearly, there are at most [1/p| S*A different optimistic likelihood functions defined by (55), and we can form Mo by picking representative in M for each optimistic likelihood function (if possible). Then, log [Mul O (s (S*AH log(SH/p1))
A direct calculation shows that IiM, >> ppd,. for all and
K.3.2 PROOF EXAMPLE 14, REGRET BOUND
We follow the commonly used definition of linear mixture MDPs (Chen et al., 2021), which is slightly more general than the one in Ayoub et al. (2020).
Definition K.14 (Linear mixture MDPs). A MDP is called a linear mixture MDP (of rank d) if there exists feature maps on(-I.)) S
Id and parameter (8)) Rdd such that Pn (s')s, a) =
(th. ( s,, a)). further assume that OAl1a 1 for all V S [o, 1] and tuple (s, a, h) E Ax [H].
< for all h [H], and | on (s' (V(ss)))V(ss')
Suppose that M is linear mixture MDP model with the given feature map ø. Then the definition above directly yields the QBE of M is bilinear with rank d. Therefore, as long as log ((M,
Ô (dH), by Proposition K.10 can obtain δ (d HTT) regret of E2D-TA claimed.
The following proposition provides upper bound (st via concrete construction. For the simplicity of discussion, we assume that the initial distribution is known, and we also assume the mean reward function is known for no-regret and PAC learning setting.
Proposition K.15 (Optimistic covering for lincar mixture MDPs), Given feature map & of dimen- sion d and constant B. Suppose that M consists of linear mixture MDPs with feature map & and parameter bounded by B (without reward component). Then for p, there exists a p-optimistic cov- ering (IP, Mo) with log MMo = (dH).
K.3.3 PROOF OF EXAMPLE 15, PAC BOUND
We consider the broader class of MDPs with low occupancy rank (Du al., 2021):
53

---

Under review as a conference paper at ICLR 2023
Definition K.16 (Occupancy rank). We say MDP is of occupancy rank for all h E [H] there exists map Φn II R.. V/ : S IR, such that (" = (M
ESE I
By definition, low-rank MDP with rank d is of occupancy rank d. Furthermore, for model class M consisting of MDPs with occupancy rank d, its VBE is bilinear with rank d. Therefore, EXPLO- RATIVE E2D achieves SubOpt Ô (H ddAlog M
on such model class as claimed. O
K.3.4 PROOF OF REWARD-FRER BOUNDS IN EXAMPLE 13-15
Example K.17 (Model estimation error). For model class M P R, its Q-type estimation error defined as
P.P 9h (π)) == IE... ( (PR(-10n, an), P1((1ss
Along with x est n and 22, it gives strong Bellman representation of M, which we term as its QER.
Similarly, we can consider the V-type estimation error
max Drv (FR(-1s,, a), a) (.ss.(()))))))) ai)
P.P 9h. (T) = EP
REA
Along with Th = ON (A) and L = 22A, it gives strong Bellman representation of M, which we term its VER.
As the following proposition indicates, the two choices of strong Bellman representation above are enough for us bound the RFDEC for tabular MDP, linear mixture MDP and MDP with low occupancy complexity. The proof of Proposition K.18 is mainly based on the decoupling behavior of linear function classes (cf. Example K.2), and can be found in Appendix K.5.6.
Proposition K.18. For model class M of linear mixture MDPs (of a given feature (), by its QER G and Proposition K.9, we have (Mde & 8dH2/
For model class M of MDPs with occupancy rank d, because its VER is bilinear, we have rfdec,(M) 8dAH2/7-
Combining Proposition K.18 with Theorem 1.1 gives that:
1. For tabular MDPs, REWARD-FREE E2D achieves SubOpt,r = ((VSSAPHH//
2. For linear mixture MDPs, REWARD-FREF E2D achieves SubOpt,r δ (VaHH3T))
3. For MDPs with occupancy rank at most d (including low-rank MDPs with rank d), REWARD- FREE E2D achieves SubOpt,r H (dAH log (PI/T).
K.4 DISCUSSIONS ABOUT BELLMAN REPRESENTATIONS AND DECOUPLING COEFFICIENT
Difference definition of Bellman representation Our Definition 11 slightly different from Foster et al. (2021, Definition F.1): They define the function Ih.
. :M (M) in terms of the dis-
crepancy function fM (M''; 5h, ahs Th, 8h+1), while only require 9r. AMM (M) can be upper bound by DRL- In general, 9p. MM (M) they define can be only upper bound by the Hellinger distance in the full observation (o, r) (which in general larger than DRL), as the expected discrepancy function may depend on distributional information about the reward that is not captured by the mean. How- ever, when the reward is included in the observation o, our definition is more general than theirs. More importantly, for the majority of known concrete examples, e.g. those in Du et al. (2021); Jin et al. (2021), the discrepancy function is linear in The and hence its expectation can be upper bound by DRI.
54

---

Under review as a conference paper at ICLR 2023
Complexity measure for Bellman representations In Foster al. (2021), the complexity of a Bellman representation is measured in terms of disagreement coefficient, which can be upper bounded by eluder dimension star number.
Definition K.19. The disagreement coefficient of a fuuuctio class F c (II [-1, 1]] is defined as
I x ( [f(T))] A, Ba [m) & x0)
0 (F, Ao: Eo: p) By Foster et al. (2021, Lemma f.r). E P A(II, it holds that
sup A
E2
(FF & 4 min ((F)
turns out that our decoupling coefficient can be upper bound by the disagreement coefficient: applying Foster al. (2021, Lemma E.3), we directly obtain the following result.
Lemma K.20. For function class F c (II - []), we have
0 (F.A.,) log ( v
dc(F, < inf A=D
2A + 6
7
where 0 (F,A,7 == sup (m) OF, spp).
Lemma K.20 also gives Example K.5 directly.
K.5 PROOF OF PROPOSITIONS
K.5.1 PROOF OF EXAMPLE K.2
Under the linearity assumption, can consider f - Og IRd such that f(x) (0,, o(z)) Vx X.
Given a v A(F x X)), let us set tx =- Ala + (2)r)((())()))) for A > 0. Then
=(f,a)= (z)) - 1001le, 10(x)),, . < ~1E |10 110112n]
1 - Exrr |b(x))1 :
47
For the first term, we have
Ey~o |1011 = Ex [0]] (xx))(())))0 [))0]] + -EE 10,1
=B -Bg-EErr [|((x)]]] 1000~=110,11
For the second term, we have
E Ex ( Exwe tr (1/0011/0000)00000111 11x)(()))())) क5 Tx)
=tr ( 1/2 1/2 [ (6())((z) J0, 1/2)
=tr 1 1/2 Φ 1/2)
< d.
Letting - 0+ and then taking inf, completes the proof.
As a corollary, we have the following result. Corollary K.21. Suppose that there exists & (di: X Re such that
F= f0= max (0,((())>) BeRd"
then de(F, 7) < d/y.
Corollary K.21 can be obtained similarly to the proof above of Example K.2. However, we believe the following fact is important:
Proposition K.22. Suppose that W = (X' x y - Ryo), then for the function class F defined by
Sw : max w(x, v) F:=
yEy
weW
have do(F,n) dc(W.n).
55

---

Under review as a conference paper at ICLR 2023
Combining Proposition K.22 and Example K.2 gives Corollary K.21 directly.
Proof of Proposition K.22 Fix a V E A(F x 2). Consider the map
- W so
that f(x) max, (z)) y) for all E X. Further consider Y F x X' - y defined as
Y (ff.z)= == arg max Bey: W (f))(x (break ties arbitrarily). Then we let ( X x )) given
by (/(w = v(((f x) ( = w, = (ff=))) and
-( [x)]]] = -B(,,,,))- [ y)]
<dc(WW 7) + Eu E8 (a. ~o (1e v)
<do(W),) + Ew Ba [
=dc(W, + E Exn 1
where the second inequality due the definition (1) max, w(x y), and the last equality is due to the fact that the marginalization of v' to X' agrees with marginalization of v to X, and for F, v'(w: fw fl) v(((f', 2) W(f') w, fw = f)) v(f). Taking infy completes the proof.
K.5.2 PROOF OF PROPOSITION K.6
To simplify the proof, we first introduce the PSC with estimation policies. Definition K.23. For M M, ler nes be the uniform mixture of M, M. M.H where we define TM, = TM. Let
est
D psc (M, M)
sup EM-MEM-- (MTr) (M(MM Di.. (M(M)) M(*7)) (z (EA(M)
where we understand
H H Σ Di (M M(FM))
(M
We further define psc.. (M) SUPMEM psc. est (M, M).
We generalize Proposition E.3 to pss by the argument, follows. Proposition K.24. When r म. it holds that
2(H + 1) ?
dM, & pssctooM
Generally, we always have
edec, psc (M 2(H 1)
Therefore, remains to upper bound psc.tl by comp(g,1) Proposition K.25. It holds that
H +
psc (M, & H max de 7/(H + 1)L?) +
47
Combining Proposition K.25 with Proposition K.24 completes the proof of Proposition K.6.
Proof of Proposition K.25 Fix a M E M and A(M). Then by the standard performance
decomposition using the simulation lemma, we have
EM- [ (TT) -d - (TTM)
56

---

Under review as a conference paper at ICLR 2023
H
EM V1 VyManar (s1) - EM
-EM
V1
Val,ans (51)
+
Σ
M
QM an) - Th - V.laa (sn+1))
H
< EM Drv (PD..P )
Eas
9/
M1:3
(M1)
Therefore, bound
H M:M
H
Σ
E Maa 12
Σ
[
9h
11 MM mm
9n
M:M N:MM (2r))
+1/BM M.B.M.. M/ -1
9h
(MMM(AN (MT')
M.M
sdo(G, m)
H
Σ
dc(g)h .1)
Pi.. (M M M(M))))
where the inequality is due to the definition of Bellman representation and decoupling coefficient. Furthermore, we have
Em-a Drv (P6' }P)]
SEM. | (M(T M ((M))) EM [ DRL (M(MM)
M ((T )
H ++1
H EM Dia (MTM))
47
Now taking y = 1H + 1) and combining the above two inequalities above completes the proof.
K.5.3 PROOF OF PROPOSITION K.7
Fix any set of models {M* tion lemma, we have
]E[[K] E M. By standard performance decomposition using the simula-
1
gMh (T - (M (TANL)
K
1
>
E M5 iF (Q iTas (sn, an) rb Vost
M tis (sh+z)
K
k= h=1
1
M (Mrh).
9h
K
On the other hand, by the definition Bellman representation,
Σ
M M
(Mr))
L
(M M (TTM))
gh
Therefore, defining
k-1
8:= max ke []]
D (MM"))) MM(TT:)))
we have Ik-1
M M Ih
(M/)
2 & 1 for all ke [K].
Our final step is to use Eluder dimension argument. By the above precondition, we can apply the Eluder dimension bound in Jin et al. (2021, Lemma 41) to obtain that, for any h [H] and A > 0.
K Mr:M" gh
(1)), K
(Ve(Cn. A)LBKK A)LBBK + min (e(gn, A) KJ + K A
(M/²)
<
K
57

---

Under review as a conference paper at ICLR 2023
(
(Vo A) max {3.1 + KA).
K
where O (1) hides the universal constant. Summing over E [H] gives
9h
M=:M"
(art)
& (
T.
H
max c(9n, A) max [3.1]K [+ KHA) hE|H]
K
K
h
[3.1]
(L)
L maXxe[m cGGn, A)K
KHLA).
max
K
?
where the last inequality uses AM-GM. Therefore, we have shown that for any {M*} RE[K]]
MM (TT -f-' ( ? mmxx { {
$0 (1) "H²LL² [M c(9 A) + HTA
< (1) H² max e( A) + +))
By definition of mlec,, taking inf A= completes the proof.
K.5.4 PROOF OF PROPOSITION K.9
By Proposition I.3 and the strong duality, we only need to upper bound the following quantity in terms of the decoupling coefficient:
sup inf ((,, E Pp-p (. - pp [P.((T')] -p] (A(PXRXI))FFACC
rrec,(M,
- -pE Ep-p (Pt P(T))
Then,
E E.p ( (P.
(EP EP) [1(
B.p. R.T) ~ E pmp
H
B. ((P. - Rh.
((P.. ((P+B) (sh+1)
R) Bpnp
h+1
+ Σ E E(p.R. Ep 11 10 (T)
B R. Ep DTV (Po. Po)]
where (i) because use the performance decomposition lemma, (ii) is due the definition of strong Bellman representation. Similar to the proof of Proposition K.25, we have
Σ
H1
E E...R..)~ Ep (
(P.R).P (T)
H
dolC 1) + o Br. (P.R).P (T)
2
<
H
do
11) + L3n
Σ h=1
Ep
( P( })
and
Eas DTV (PM,
?
H+1 Ep Bp- D (P(m),
H +
47
We just need to choose Pe.h E A(TI) (r. = u(((P, R, m n'}) (here mest x),
Pe /
DH Ph-o E A(II), and let 17 w-7. obtain
H
H +
rec,(M..)
dc H
47
Applying Proposition 1.3 completes the proof.
58

---

Under review as a conference paper at ICLR 2023
K.5.5 PROOF OF PROPOSITION K.15
We construct such a covering directly, which is generalization of the construction in Example K.1 An important observation is that, by the definition of feature map (cf. Definition K.14), it must hold that
[ & 2d,
a() E ( A.
Then, we set N [BBpp] and let B' = Np. For H [-'',, we define the p-neighborhood of B(O, p00/p] [0, rl and let
P9 s. a) == max
(0' (f'd(s'|s.a))
O'EB(O,p)
Then, if 0 induces a transition dynamic Pa. then Po 3 Fa. and
Σ Po(s'|s, a) Po(s"|s,, Σ max 8'EB(e,p)
K 0('sss)())ss.)) a)> &
Σ o(s (s)s|s)))) < 2pd.
Now, for θ (0n) (R4) define (g 01. ".
sH aH) : I (1 (521s1, (
H I
H-1
(s))
TA (as (n)
II
Po. (sh+1lsh, an).
h=1
Suppose that p d/)Hdd). then simple caleulation shows that when θ induces MDP,
P3
P3 2eHdp.
Therefore, let = deHddp then by picking representative in each --balll we can construct /1-optimistic covering with [Mol (2N) Ha
(2 (2(B/))) (2 p2)
Hd which
implies that log [Mo < O (dH log dHB/p1)).
K.5.6 PROOF OF PROPOSITION K.18
We deal with linear mixture MDP first. Suppose that for each P E P, P parameterized by 0P (0.).. Then the QER of P is given by
9h (T) = Fx
P.P
Drv (PM(-1on, an), P-(-Ssh an))]
1
P.P.T
Σ
PPP PP and P (s)).a)))))))))))) an)
max
2 V:Sx5xA-(-1.1)
Sh+1
1
EP.TT
Σ (ph - -Ph (n an) V ((sntilsn an)
max
2 V:5xSxA-(-11
1
O PP, BP
Σ (in
max
2 V:8x8xA-[-1.11
#h+1
V(sstilsh az) 18h, an) 1)
1
8P
R. EP
Σ 8h+t
max 2 V=5x5xA-[-1.1]
Applying Proposition K.9 and Corollary K.21 completes the proof of this case.
We deal with the class P of dynamic of MDPs with occupancy rank at most d. For P P, (vf S - Rd), such that pP. (sp s) (w)(s), (T)).
consider S" = ( II - IRd., vi
Then the VER of given by
max Dry (P. (P.(-)s,,)) ()) 4))]
P.P (T) 9h
PM
PM
(R max Drv (P)(-)s, (((1s, ,8(()) Σ
aEA
Applying Proposition K.9 and Example K.2 completes the proof of this case.
59


Reviews:
[{"review_id": "lU9gWrqdVu", "reviewer": "Reviewer_Tm8H", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "", "summary_of_the_paper": "The paper follows the framework of decision-estimation coefficient (DEC) proposed by (Foster et al. 2021). The major contribution of this work is to combine DEC with tempered aggregation to design algorithms for several problems (e.g., regret minimization, PAC-learning and reward-free learning) in DMSO (decision making under structured observation).", "summary_of_the_review": "Given the consideration above, I think the motivation is still not clear and tend to reject this paper. It would be helpful if the authors could give some meaningful examples where E2D-TA is computational efficient while E2D is not. ", "strength_and_weaknesses": "Strength: The authors proposed E2D-TA by combining E2D with tempered aggregation to help avoid estimating the transition model. \nIn technique, the authors propose a new definition for $dec$ and manage to derive a stronger bound for error term $Est_{RL}$. \n\n\nWeaknesses: The motivation is not strong enough. The authors compare this work with Foster et al., 2021 in the third paragraph in Section 1.  As stated above, the main merit of the proposed algorithm is to avoid estimating the transition model. However, the proposed algorithm is still computational intractable given this improvement.  Even assuming the tabular state-action space (where we can estimate the model efficiently), E2D-TA seems still computational inefficient. \n\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "jcntbKgTm9T", "reviewer": "Reviewer_oWcL", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "", "summary_of_the_paper": "The authors introduce a new model-based meta-algorithm called E2D-TA under the framework of E2D(Forster et al.,2021), which updates the model estimator by Tempered Aggregation. Under this main algorithm, the authors further introduced two complexity parameters, EDEC and RFDEC, and correspondingly designed two algorithms for PAC and reward-free learning tasks. The authors also provide the rate of growth for E2D, EDEC and RFDEC, and prove that with delicate choice of the parameters, these algorithms enjoy a sublinear regret bound, which also meets the lower bound. Moreover, the authors provide sublinear regret bounds for RL with Bellman representability under E2DTA framework.", "summary_of_the_review": "This paper generalizes the E2D framework in Foster et al. to PAC learning and reward-free learning by substituting the model estimation method with Tempered Aggregation and new complexity metrics. It further provides minimax optimal regret bound, which is also proved to be sublinear under many cases, including finite model class and low BE dimension cases. However, there are still difficulties to grasp its true novelty. In my opinion, it would be better if the authors can further highlight the contribution of their techniques in more concrete ways, especially:\n1. The generalization from simple E2D to their reward-free and PAC learning edition, and\n2. The connection between this generalization and using TA as the model estimator.", "strength_and_weaknesses": "The strengths of the paper according to me are the following:\n1. The authors prove the upper bound of DEC, EDEC and RFDEC under a uniform framework, which is not covered by previous works.\n2. The authors design an algorithm for reward-free and PAC learning case, with finite class and low-bellman dimension models as examples. This is not covered in previous works under E2D framework.\n\nThe weaknesses of the paper (according to me) are the following:\n1. In my humble optinion, it is hard to justify the paper's novelty. For me, the main algorithm E2D-TA seems to be a modification of Algorithm 1 in (Foster et al.,2021) only by changing the method of learning the underlying model.  Foster et al. first estimate the underlying model using methods such as Vovk aggregation which only incurs an extra estimation error of \\gamma\\log(|M|/\\delta). This paper estimates the underlying model by computing posterior distribution on the model set and claim to be a tighter bound justified by Jensen's inequality, but its contribution to the overall regret is still of scale \\gamma\\log(|M|/\\delta) and therefore this technique, as the main novelty, doesn't seem to optimize the regret bound. Meanwhile, this paper adopts different definition of estimation error i.e. EST. Therefore the authors need to further justify the importance of using this method.\n\n2. Forster et al. provide an analysis for infinite model class case in Section 3.2.3 with a proof base on covering number and further show its application in bilinear RL settings and covers low BE dimension results in Appendix F.   It is hard to see the main difference between the analyses in those two paper. The results in reward-free cases and PAC learning under those settings also seem to be a straightforward generalization. \n\n3. The necessity of using TA as the model estimator is not obvious. In my humble opinion, it would be better if the authors can justify why simply using other estimators (e.g. Vovk's aggregation) can not be generalized to reward-free/PAC cases.\n\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "YiliOlMvcVX", "reviewer": "Reviewer_tzo7", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "", "summary_of_the_paper": "This paper extended DEC from regret minimization to PAC guarantee and reward-free case. Similar algorithms, lower bounds and upper bounds are established. ", "summary_of_the_review": "A solid theoretical paper but a bit incremental. Computational efficiency is a big limitation. ", "strength_and_weaknesses": "I appreciate the authors' great effort to extend DEC to PAC setting and reward-free setting with a lot of tedious calculation. However, I feel this work is a bit incremental. Instead of covering material as much as possible, I suggest the author focuses on one problem and thinks deeper. There are some important problems left for DEC and this paper inherits them to other settings. \n \n1. It's better to explain clearly what do you mean \"sufficient and necessary\"? Clearly the upper bound (Thm 5) and lower bound (Proposition 6) differ by a log(|M|) term.\n \n2. The algorithm is far from computational efficient. There are several minimax operators involved such that there is little useful guidance for practitioners. The algorithm is not implementable and of course no experiments. \n \n3. The guarantee in Example 13 is far from optimal. The dependency for S is very bad. It is unclear this is due to analysis or due to the complexity measure. Again, then why you can claim \"sufficient and necessary\"? \"Unified algorithm\" should not be an excuse. That means this unified algorithm cannot pass the sanity check of tabular MDPs.\n \n4. It's very unusual for ICLR to have a 58 page submission. That means it is impossible for reviewers to check the correctness of the proof. And a lot of proofs are repeated from Foster et al. (2021) (for example, Section B.3). Such a paper is more suitable for journal submission in my mind.   \n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}]

Author rebuttal:

Decision: Reject