Maximize to Explore: One Objective Function Fusing Estimation, Planning, and Exploration
Authors: Zhihan Liu
Miao Lu
Wei Xiong
Han Zhong
Hao Hu
Shenao Zhang
Sirui Zheng
Zhuoran Yang
Zhaoran Wang
Venue: NeurIPS 2023 spotlight (2023)
Keywords: reinforcement learning; online learning; game
TL;DR: We design a both provable sample-efficient and easy-to-implement RL framework for exploration.

Abstract: In reinforcement learning (RL), balancing exploration and exploitation is crucial for achieving an optimal policy in a sample-efficient way. To this end, existing sample- efficient algorithms typically consist of three components: estimation, planning, and exploration. However, to cope with general function approximators, most of them involve impractical algorithmic components to incentivize exploration, such as data-dependent level-set constraints or complicated sampling procedures. To address this challenge, we propose an easy-to-implement RL framework called Maximize to Explore (MEX), which only needs to optimize unconstrainedly a single objective that integrates the estimation and planning components while balancing exploration and exploitation automatically. Theoretically, we prove that the MEX achieves a sublinear regret with general function approximators and is extendable to the zero-sum Markov game setting. Meanwhile, we adapt deep RL baselines to design practical versions of MEX in both the model-based and model-free settings, which outperform baselines in various MuJoCo environments with sparse reward by a stable margin. Compared with existing sample-efficient algorithms with general function approximators, MEX achieves similar sample efficiency while also enjoying a lower computational cost and is more compatible with modern deep RL methods.

Maximize to Explore: One Objective Function Fusing Estimation, Planning, and Exploration
Zhihan Liul
Miao Lu
Wei Xiong
Han Zhong'
Hao Hu
Shenao Zhang'
Sirui Zheng'
Zhuoran Yang
Zhaoran Wang'
Northwestern University
Stanford University University of Illinois Urbama- -hbama-Champainn
*Peking University Tsinghua University Yale University
shenaozhang2028. sirui (erriiieeng225]]46 northwesterr edu miaolu@stanford edu, wx130illinois edu, hanzhong@stu pku. edu. cn huh220mails. tsinghua, edu. cn, zhuoran, yang@yale edu, zhaoranvang@gaiil.oo com
(zhihanliu2027,
Abstract
In reinforcement learning (RL), balancing exploration and exploitation is crucial for achieving optimal policy in a sample-efficien way. To this end, existing sample- efficient algorithms typically consist of three components: estimation, planning, and exploration. However, to cope with general function approximators, most of them involve impractical algorithmic components to incentivize exploration, such data-dependent level-set constraints or complicated sampling procedures. To address this challenge, we propose an easy-to-implemen RL framework called Maximize to Explore (MEX), which only needs to optimize unconstrainedly single objective that integrates the estimation and planning components while balancing exploration and exploitation automatically. Theoretically, prove that the MEX achieves sublinear regret with general function approximators and is extendable the zero-sum Markov game setting. Meanwhile, adapt deep RL baselines design practical versions of MEX both the model-based and model-free settings, which outperform baselines in various MuJoCo environments with sparse reward by a stable margin. Compared with existing function approximators, MEX achieves similar sample efficiency while also enjoying a lower computational cost and is more compatible with modern deep RL methods. Our codes are available at https: /gg thub. cow/agentif weteeetiiiiaaiii/MM......
efficient algorithms with general
Introduction
The crux of online reinforcement learning (online RL) lies in maintaining a balance between exploiting the current knowledge of the agent about the environment and exploring unfamiliar areas [69]. To fulfill this, agents in existing sample-efficient RL algorithms predominantly undertake three tasks: estimate a hypothesis using historical data to encapsulate their understanding of the environment; ii) perform planning based on the estimated hypothesis exploit their current knowledge; iii) further explore the unknown environment via carefully designed exploration strategies.
There exists a long line of research on integrating the aforementioned three components harmoniously, to find optimal policies in sample-efficient manner. From theoretical perspectives, existing theories aim to minimize the notion of online external regret which measures the cumulative suboptimality gap of the policies learned during online learning. It is well studied that one can design both statistically and computationally efficient algorithms (e.g.. upper confidence bound (UCB), [6, 39, 12, 91]) with sublinear online regret for tabular and linear Markov decision processes (MDPs). But when
Equua contribution.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

comes to MDPs with general function approximations, most of them involve impractical algorithmic components to incentivize exploration. Usually, to cope with general function approximations, agents need to solve constrained optimization problems within data-dependent level-sets [37, 20], or sample from complicated posterior distributions over the space of hypotheses [19, 2, 89], both of which pose considerable challenges for implementation. From a practical perspective, a prevalent approach in deep RL for balancing exploration and exploitation is to use an ensemble of neural networks [75, 59, 14, 53, 44, 18, 45], which serves as empirical approximation of the UCB method. However, such an ensemble method suffers from high computational cost and lacks theoretical guarantee when the underly MDP is neither linear nor tabular. As for other deep RL algorithms for exploration [29, 3, 11, 9, 17, 65], such as surrosity-driveer method [60], it also remains unknown in theory whether they are provably sample-efficiens in the context of general function approximations.
Hence, this paper, we are aimed at tackling these issues and answering the following question:
Under general finction approximation, can we design a sample-efficient and easy-to-impe ton-tt-immlement RL framework to trade off between exploration and exploitation?
To this end, we propose an easy-to- conlleetimple RL framework, Maximize to Explore (MEX), as an affirmative answer to the question. To strike balance between exploration and exploitation, MEX propose to maximize a weighted sum of two objectives: (i) the optimal expected total return associated with given hypothesis and (ii) the negative estimation error of that hypothesis. Consequently, MEX naturally combines planning and estimation components in just a single objective. By choosing the hypothesis that maximizes the weighted sum and executing the optimal policy with respect to the chosen hypothesis, MEX automatically balances between exploration and exploitation.
We highlight that the objective of MEX is not obtained by taking the Lagrange dual of the constrained optimization objective within data-dependent level-sets [37, 20, 15J. is because the coefficient of the weighted sum, which remains fixed, is fata-independent and predetermined for all episodes. Contrary to Lagrangian methods, MEX does not necessitate an inner loop of optimization for dual variables, thereby circumventing the complications associated with minimax optimization. As maximization-only framework, MEX is friendly to implementations with neural networks and does not rely on sampling or ensemble.
In the theory part, we prove that MEX achieves a sublinear regret O(Poly(H) d (1/VHK) (HK))-// K1/ under mild assumptions and is thus sample-efficient, where K is the number of episodes and H is the horizon length. Here (-Fe(.) is the Generalized Eluder Coefficient (GEC) [89] that characterizes the complexity of learning the underlying MDP under general function approximations. Because the class of low-GEC MDPs includes almost all known theoretically tractable MDP instances, our proved result can be tailored to a multitude of specific settings with either a model-free or a model-based hypothesis, such as MDPs with low Bellman cluder dimension [37]. MDPs of bilinear class [20], and MDPs with low witness rank [67]. Besides, thanks to the flexibility of the MEX framework, further extend it to online RL in two-player zero-sum Markov games (MGs), for which we further extend the definition of GEC to two-player zero-sum MGs and establish the sample efficiency with general function approximations. Moving beyond theory and into practice, we adapt famous RL baselines TD3 [27] and MBPO [34] to design practical versions of MEX in model-free and model-based fashion, respectively. On various MuJoCo environments [71] with sparse rewards, experimental results show that MEX outperforms baselines steadily and significantly. Compared with other deep RL algorithms, MEX has low computational overhead and straightforward implementation while maintaining theoretical guarantee.
Contributions. We conclude our contributions from three perspectives.
1. We propose an sony-to-ippleentt RL algorithm framework MEX that unconstrainedly maximizes a single objective to fuse estimation and planning, automatically trading off between exploration and exploitation. Under mild structural assumptions, we prove that MEX achieves sublinear regret O(Poly(I)) d2/2 (1/ (LL/HK))/!
with general function approximators, and thus is sample- efficient. Here dcase(-) is the generalized Eluder Coefficient (GEC) of the underlying MDP.
We instantiate the generic MEX framework to several model-based and model-free examples and establish corresponding theoretical results. Further, we extend the MEX framework to two-player zero-sum MGs and also prove the sample efficiency with an extended definition of GEC.
3. We design practical implementations of MEX for MDPs in both model-based and model-free styles. Experiments on various MuloCo environments with sparse reward demonstrate the effectiveness of our proposed MEX framework.
2

---

1.1 Related work
Sample-efficient RL with function approximation. The success of DRL methods has motivated a line of work focused on function approximation scenarios. This work originated in the linear case [74, 81, 12, 39, 84, 5, 82, 57, 91, 90] and is later extended to general function approximation. Wang et al. [73] first study the general function approximation using the notion of eluder dimension [63], which takes the linear MDP [39] special case but with inferior results. Zanette et al. [85] consider a different type of framework based on Bellman completeness, which assumes that the class used for approximating the optimal Q-functions is closed in terms of the Bellman operator and improves the results for linear MDP. After this, Jin et al. [37] consider the eluder dimension of the class of Bellman residual associated with the RL problems, which captures more solvable problems. Another line of works focuses on the low-rank structures of the problems, where Jiang et al. [35] propose the Bellman rank for model-free RL and Sun et al. [67] propose the witness rank for model-based RL. Following these two works, Du et al. [20] propose the bilinear class, which contains more MDP models with low-rank structures [6, 67, 39, 57, 12, 91] by allowing flexible choice of discrepancy function class. However, it is known that neither BE nor bilinear class captures each other. Dann et al. [19] first consider eluder-coefficient-yyy complexity measure on the Q-type model-free RL. It was later extended by Zhong et al. [89] to cover all the above-known solvable problems in both model-free and model- manners. Foster al. [25, 23] study another notion of complexity measure, the -estimionnsttiaaiionn coefficient (DEC), which also unifies the Bellman eluder dimension and bilinear class. The DEC framework is appealing due to the matching lower bound in some decision- decision-making problems, where all other complexity measures do not have. However, due to the presence of a minimax subroutine in its definition, they require much more complicated minimax methods. Chen et al. [13], Foster et al. [24] extend the vanilla DEC (to the model-free case) by incorporating an optimistic modification, which was originally referred to as the feel-good modification in Zhang [87]. Chen et al. [15] study Admissible Bellman Characterization (ABC) class to generalize BE, They also extend the GOLF algorithm and Bellman completeness in model-free RL to the model-based case by considering more general (vector-form) discrepancy loss functions to construct sharper iamsample error estimators and obtain sharper bounds compared to Sun et al. [67]. Xie et al. [79] connect the online RL with the coverage condition in the offline RL, and also study the GOLF algorithm proposed in Jin et al. [37].
optimization oracle and cannot apply to the classical mntimism-based or sampling-base
A Algorithmic design in sample-efficient RL with function approximation. The most prominent approach in this area is based on the principle of "Optimism in the Face of Uncertainty" (OFU), which dates back to Auer et al. [4]. For instance, for linear function approximation, Jin et al. [39] propose an optimistic variant of Least-Squares Value Iteration (LSVI), which achieves optimism by adding a bonus at each step. For the general case, Jiang et al. [36] first propose an elimination-based algorithm with optimism in model-free RL and is extended to model-based RL by [67]. After these, Du et al. [20]. Jin et al. [37] propose two OFU-based algorithms, which are more similar to the lin-UCB algorithm [1] studied in the linear contextual bandit literature. The model-biis based counterpart (Optimistic Maximum Likelihood Estimation) is studied in Liu et al. [46], Chen et al. [13]. Specifically, these algorithms explicitly maintain confidence set that contains the ground truth with high probability and conducts a constraint optimization step at each iteration to select the most optimistic hypothesis in the confidence set. The other line of work studies another powerful algorithmic framework based on posterior sampling. For instance, Zanette et al. [84] study randomized least-squares value iteration (RLSVI), which can be interpreted as sampling- based algorithm and achieves an order-optimal result for linear MDP. For general function approximation, the works mainly follow the idea of the "feel-good" modification proposed in Zhang [87]. These algorithms start from some prior distribution over the hypothesis space and update the posterior distribution according to the collected samples but with certain optimistic modifications in either the prior or the loglikelihood function. Then the hypothesis for each iteration is sampled from the posterior and guides data collection. In particular, Dann et al. [19] studies the model-free Q-type problem, and Agarwal and Zhang [2] studies the model-based problems, but under different notions of complexity
measures. Zhong et al. [89] further utilize the idea in Zhang [87] and extend the posterior sampling
algorithm in Dann et al. [19] to be unified sampling- based framework to solve both model-free and model-based RL problems, which is also shown to apply to the more challenging partially observable setting. In addition to the OFU-based algorithm and the sampling- propose the -oeiiiiiioo-iiisnnssso (F2D) algorithm, which can solve problems with low DEC but requires solving complicated minimax subroutine to fit in the framework of DEC.
framework, Foster et al. [25]
3

---

Due to the limitation of the page, we defer the remaining discussions of Relationship with reward- biased maximum likelihood estimation, Exploration of DRL, and Two-player Zero-Sum Markoy Game to Appendix B.
2
Preliminaries
2.1 Episodic Markov Decision Processes and Online Reinforcement Learning
We consider an episodic MDP defined by tuple (S, A, H.P.r), where S and A are the state and action spaces, H is a finite horizon, = {1P with Pş. S x A (SS) the transition kernel at the li-th timestep, and {ra) with rh S A + [0. 1] the reward function at the h-th timestep. Without loss of generality, we assume that the reward function Ya is both deterministic and known.
In the episodic MDP, the agent interacts with the environment by the following online protocol. At the beginning of the k-th episode, the agent selects a policy n/ = { : :S + A(A) It takes an action of ~ T ( at timestep / and state x After receiving the reward r = Tn (1 a from the environment, it transits to the next state . ~ PA (- - at)) When the agent reaches the state 11 it ends the k-th episode. Without loss of generality, we assume that the initial state fixed. Our analysis can be generalized to the setting where Ii is sampled from a distribution on S.
is
Policy and value functions. For a policy ग = {T S - ((A)) we denote by - IR and Q7,-- S x A + I its value function and state-action value function at the h-th timestep, which characterizes the expected total rewards received by the agent under policy afterward, starting from some z/- x E S (or 2h = I E S, an = a A, resp.). till the end of the episode. Specifically,
Vi((2) == Ex
Σ
The (IW, axd
Th = x
Vo E S,
(2.1)
h//h
H
(% = Ex
Σ
The (IMC, ax))
Th = x, ah = a
(2.2)
Li=hh
We know there exists an optimal policy x² which has the optimal value function for all initial states [61], that is, V. (s) = sup, (x) for all E [H] and x E S. For simplicity, we abbreviate V"" as V and the optimal state-action value function QT as Q". Moreover, the optimal value functions Q" and V satisfy the following Bellman optimality equation [61], given by
(x) = max (x) aEA
(z+ 0,
(2.3)
Qh a) (T+))+1) (z,0) == := a) + I a.,a) VV (z')),
(2.4)
for all (x, a, h) S Ax [H]. We call Tn the Bellman optimality operator at timestep h. Also, for any two functions Qn and Qh+1 on S x A. we define
En, Qu+1: 2, a) = Qn a) (1 a), V(2,a) E ESA.
(2.5)
as the Bellman residual timestep h of (Q,, Qx+1).
Performance metric. We measure the online performance of an agent after K episodes by regret. We assume that the learner predicts the optimal policy x" via x* in the k-th episode for each k E [K]. Then the regret of K episodes is defined as the cumulative suboptimality gap of {m** ]ejKK]
Regret K) = Σ (m1) - VT (x1).
(2.6)
k=1
The target of sample-efficient online RL is to achieve sublinear regret (2.6) with respect to K.
2.2 Function Approximation: Model-Free and Model-Based Hypothesis
To handle MDPs with large or even infinite state space, we introduce a family of function approxi- mators. In specific, we consider a hypothesis class H Hi .... x Hr. which can be specified to model-based and model-free settings respectively. Also, we denote by II = II, x ... x II as the space of Markovian policies. We now specify H. for model-free and model-based settings.
We allow the agent to predict the optimal policy via x while executing some other exploration policy neep interact with the environment and collect data, as is considered in the related literature [67, 20, 89]

---

Algorithm 1 Maximize to Explore (MEX)
1: Input: Hypothesis class H. parameter 1j > O.
2: for k = 1.... do
3: Solve f E H via
H
argsup JCH
(21) -
(5)
(3.1)
h=1
4: Execute (f) to collect data D
(D) (hEMH with D (2 a 2 #ht1)
5: Predict the optimal policy via ya.
6: end for
Example 2.1 (Model-free hypothesis). For model-free hypothesis class, H contains state-action value functions of the MDP, i.e., HA. S Uf S x A RJ. Specifically, for any f (fi,-... {H) E H. with Qa. = Sn- Also, we denote the corresponding optimal state- value function V₁ (Vn,thee(m) with (t,s()) maxae.A Qh ( a) and denote the corresponding optimal policy by π [TT.. hell with T-) = arg max,E E.A Qh.s(;,a) Finally, we denote the optimal state-action value function under the true model, i.e., Q², by f
we denote 2 = {Qn.s
Example 2.2 (Model-based hypothesis). For model-based hypothesis class, H contains models of the MDP, i.e., the transition kernel. Specifically, we denote f = f = (Fi.f.-... . PH.I) E H.. For any (f.z) H. x II, we define V = =VV", The(m) as the state-value function induced by model P and policy x. We use V5 = {Vh,, to denote the corresponding optimal state-value function, i... V/., = su ViT.5 The corresponding optimal policy is denoted by π = {TTh, hEEMH, where Th, arg euI Vi,,r Finally, we denote the true model P of the MDP as f
We remark that the main difference between the modell-based hypothesis (Example 2.2) and the model-free hypothesis (Example 2.1) 1)) is that model-basee RL directly learns the transition kernel of the underlying MDP, while model-free RL learns the optimal state-action value function. Since do not add any specific structural form to the hypothesis class, c.g., linear function or kernel function, are in the context of general function approximations [67, 37, 20, 89, 15].
3 Algorithm: Maximize to Explore for Online RL
In this section, we propose Maximize to Explore (MEX, Algorithm 1) for online RL in MDPs with general function approximations. With novel single objective, MEX automatically balances the goal of exploration and exploitation. We first give a generic algorithm framework and then instantiate it to model-free (Example 2. and model- (Example 2.2) hypotheses respectively.
Generic algorithm design. each episode & E [K]. the agent first estimates a hypothesis f* E H using historical data [D= by maximizing a composite objective (3.1). Specifically, in order to achieve exploiting history knowledge while encouraging exploration, the agent considers a single objective that sums: (a) the negative loss - 1.A.- (f) induced by the hypothesis f. which represents the exploitation of the agent's current knowledge; (b) the expected total return of the optimal policy associated with this hypothesis, i.e.. Vi.j. which represents exploration for higher return. With tuning parameter > 0, the agent balances the weight put on the tasks of exploitation and exploration. The agent then predicts n²" via the optimal policy with respect the hypothesis that maximizes the composite exploration-explottaaai objective function, i.e., π yz. Also, the agent executes certain exploration policy (f*) to collect data t = {(ak ah rh x H and updates the loss function (f). The choice of Texp (J*) depends on the specific MDP structure, and we refer to examples Section 5 for detailed discussions.
We highlight that MEX is not Lagrangian duality of constrained optimization objectives within data-dependent level-sets [37. 20. 15]. fact, MEX only needs to fix the parameter 77 across each episode. Thus r7 is independent of data and predetermined, which contrasts Lagrangian methods that involve an inner loop of optimization for the dual variables. We also remark that we can rewrite (3.1) as joint optimization (f, œ) = arR (11) - v E L zk-11 (f). When 7 tends to infinity, MEX can be reduced to vanilla Actor-Critic framework [41], where critic f minimizes estimation error and actor conducts greedy policy following the critic f. In the following two parts,
5

---

we instantiate Algorithm to model-based and mode-free hypotheses by specifying the loss function (f). Model-free algorithm. For model-free hypothesis (Example 2.1), (3.1) becomes
H Q1. - Σ 4 (
argsup
max E.A
(f)
(3.2)
JEH
Regarding the choice of the loss function, for seek of theoretical analysis, deal with MDPs with low Bellman eluder dimension [37] and MDPs of bilinear class [20], we assume the existence of certain function 1 which generalizes the notion of Bellman residual.
Assumption 3.1. Suppose the function H. X Hr, X Hat1 x (S x X x S) + R satisfies: i) (Generalized Bellman completeness) [89, 15] there exists operator PA Hx+1 + HA such that for any (f', Shi fa+1) E H x Hh. x HA++1 and Dn. = (Ih, ah Thi Da+1) E S x A x R x S, it holds
(y fa+1), Da) - Lp ((Paf++1, fn+1), Dn) BEnttrFr (-las, P4 ((h, fn-1), Dn)], where we require that PhJh+1 f% and that Ph E Ho for any fa+1 E Ha+1 and step h [H]; ii) (Boundedness) it holds that sup M ((Sr, fn+1), Da)lloo S Bofor some constant B₁ O.
We then set the loss function LN an empirical estimation of the generalized squared Bellman error Ee Brl .l..)l)))))))))))). B ((En Ju+1). D))] given by
& () = - ((fh, fa+h Di)² inf KEHA
(3.3)
==1
s=1
We remark that the subtracted infimum term in (3.3) is to handle the variance terms in the estimation to
achieve a fast theoretical rate. Similar essential ideas are also adopted by [37, 78, 19, 38, 52, 2, 89, 15].
Model-based algorithm. For model-based hypothesis (Example 2.2), (3.1) becomes
#
8 argsup JEH
sup V1.5, (x1)- - Σ -4-00 TEll
(3.4)
h=1
which is a joint optimization over the model p, and the policy æ. In the model-based algorithm, we choose the loss function L as the negative log-likelihood loss, defined as
k
I = Σ
log Fr, 1 a..)
(3.5)
4 Regret Analysis for MEX Framework
In this section, we establish a regret analysis for the MEX framework (Algorithm 1). We give generic theoretical guarantee which holds for both model-free and model-based settings. We first present three key assumptions needed for sample-efficient learning with MEX. In Section 5, we specify the generic theory to specific examples of MDPs and hypothesis classes satisfying these assumptions.
Firstly, we assume that the hypothesis class H is well-specified, containing the true hypothesis J Assumption 4.1 (Realizablity). We assume that the true hypothesis f* E H.
Then we need to make structural assumption on the MDP to ensure sample-efficient online learning. Inspired by Zhong al. [89], we require the MDP have low Generalized Eluder Coefficient (GEC). A low GEC indicates that the agent can effectively mitigate out-of-sample prediction errors by minimizing in sample errors derived from historical data. To introduce, we define discrepancy function & (f; {x) H x H x (S x A x R S) + R which characterizes the error of hypothesis E H. on data čn (Ih, aje The .141). Specific choices of l are given in Section 5 for concrete model-free and model- based examples.
0, there Assumption 4.2 (Low Generalized Eluder Coefficient [89]). We assume that given exists d(e) E 1R,, such that for any sequence of [ C H. (f) C 11,
K
K "ΣΣΣ
d(c). +V(cHHKHHHK
Vv.y
inf MS0
E Pen-*Roplie (f)= (fh:
{2
24
1=1
h=
We denote the smallest number d(e) R4 satisfying this condition dGEC(E).

---

As is shown by Zhong et al. [89], the low-GEC MDP class covers almost all known theoretically tractable MDP instances, such as linear MDP [81, 39]. linear mixture MDP [5, 57, 12], MDPs of low witness rank [67], MDPs of low Bellman eluder dimension [37], and MDPs of bilinear class [20].
Finally, we make concentration-styl assumption which characterizes how the loss function T.ţ is related to the expectation of the discrepancy function [e[4] appearing in the definition of GEC. For ease of presentation, we assume that H. finite, i.e., [7| o0, but our result can be directly extended to an infinite H using covering number arguments [72, 37, 49, 38].
Assumption 4.3 (Generalization). We assume that H. is finite, ie., IH < +00, and that with probability at least - for any episode k E [K] and hypothesis f E H. holds that
H Σ h - -- (E
H k-1
+ B(H (oHooHHK/OO + +o)((HH));
b=1s=1
where B Bi for model-free hypothesis (Assumption 3.1) and B for model-based hypothesis. Such concentration style inequality is well known in the literature of online RL with general function approximation and similar analysis is also adopted by [37, 15]. With Assumptions 4.1, 4.2, and 4.3, we can present our main result (see Appendix D.I for a proof).
Theorem 4.4 (Online regret MEX (Algorithm 1)). Under Assumptions 4.1, 4.2, and 4.3, by setting
dGEC(L/VHH,
V
(H (8g(H//88) + log( B K
then the regret of Algorithm 1 after K episodes is upper bounded by
Regret( K) S v dGEc(1/VHKK (H log H K/8) + log((H()) B 3- K, with probability at least 1 Here d- is defined in Assumption 4.2.
Theorem 4.4 shows that the regret of Algorithm scales with the square root of the number of episodes K and the polynomials of horizon H, GEC dc //VV K), and log covering number log,((H, 1/K) When the number of episodes K tends to infinity, the average regret vanishes, meaning that the output policy of Algorithm 1 achieves global optimality. Since the regret of Algorithm is sublinear with respect to the number of episodes K, Algorithm is proved to be sample-efficiett In Appendix C, we extend the algorithm framework and the analysis to the two-player zero-sum Markov game (MG) setting, for which we also extend the definition of GEC to two-player zero-sum MGs.
Besides, as we can see from Theorem 4.4 and its specifications in Section 5, MEX matches existing theo- retical results in the literature of online RL with general function approximations [89, 67, 20, 37, 19, 2]. But in the meanwhile, MEX does not require explicitly solving a constrained optimization problem within data-dependent level-sets or performing a complex sampling procedure. This advantage makes MEX a principled approach with easier practical implementation. We conduct deep RI. experiments for MEX in Section 6 to demonstrate its power in complicated online problems.
5 Examples of MEX Framework
In this section, we specify Algorithm I to model-based and model-free hypothesis classes for various examples of MDPs of low GEC (Assumption 4.2), including MDPs with low witness rank [67], MDPs with low Bellman cluder dimension [37], and MDPs of bilinear class [20]. For case of presentation, we assume that [H| < 00, but our result can be directly extended to infinite H. using covering number arguments [72, 37, 49]. All the proofs of the propositions in this section are in Appendix E.
We note that another important step in specifying Theorem 4.4 to concrete hypothesis classes is to check Assumption 4.3 (supervised learning guarantee). It is worth highlighting that, in our analysis, for both model-free and model-based hypotheses, we provide supervised learning guarantees in a neat and unified manner, independent of specific MDP structures.
5.1 Model-free online RL in Markov Decision Processes
In this subsection, specify Algorithm I for model-free hypothesis class H (Example 2.1). For model-free hypothesis class, we choose the discrepancy function E as, given Dj, = (Ih, Qhy Thy Th+1),
Ep (f: DA) (Eeg PP (+Ixn, 14p ((hr, fn+ D+)1)
(5.1)
7

---

where the function 1: H. x HA X Hh+1 x (S x A - R satisfies Assumption 3.1. We specify the choice of in concrete examples of MDPs later. the following, we check and specify Assumptions 4.2 and 4.3 in Section 4 for model-free hypothesis classes.
Proposition 5.1 (Generalization: model-free RL). We assume that H is finite, i.e. 171] < +00. Then under Assumption 3.1, with probability al least 6, for any l E [K] and J E H. it holds that
H
H R-1
Σ R=1
-
-
(og(H66)) + log((H)))),
==
where I. and are defined in (3.3) and (5.1) respectively. Here B₁ is specified in Assumption 3.1. Proposition 5.1 specifies Assumption 4.3 for model-free hypothesis classes. For Assumption 4.2, we need structural assumptions on the MDP. Given an MDP with generalized eluder dimension dGEC. we have the following corollary our main theoretical result (Theorem 4.4).
Corollary 5.2 (Online regret of MEX: model-free hypothesis), Given an MDP with generalized eluder coefficient dcFa(.) and a finite model-free hypothesis class with J H. under Assumption 3. I, setling
(cLc(L/VHK)
(5.2)
(H log(HH/8)) + log( H()) B K'
then the regret of Algorithm 1 after K episodes is upper bounded by
Regret S Br v dcnc(1/VHK)) (H (/g(H + log((H()) K,
(5.3)
with probability at least 1 5. Here B₁ is specified in Assumption 3.1.
Corollary 5.2 can be directly specified to MDPs with low GEC, including MDPs with low Bellman eluder dimension [37] and MDPs of bilinear class [20]. See Appendix E. for a detailed discussion.
5.2 Model-based online RL in Markov Decision Processes
In this subsection, we specify Algorithm for model-based hypothesis class H (Example 2.2). For model-based hypothesis class, we choose the discrepancy function é in Assumption 4.2 and 4.3 as the hellinger distance. Given data D (Ih, Oh, The Th+1), we let
(f: Dr.)
(P.P,,,(-la (F) (+ an)).
(5.4)
where (-1(-ll) denotes the Hellinger distance. We note that by (5.4), the discrepancy function does not depend on the input I' H. In the following, we check and specify Assumption 4.2 and 4.3.
Proposition 5.3 (Generalization: model-based RL). We assume that H is finite, i.e., [H] < +00.
Then with probability at least 1 8, any k [K], f H. it holds that
H
H1 k-1
(r + Hlog(H/5) + log((?()),
h=1
b=1
where L and are defined in (3.5) and (5.4) respectively.
Proposition 5.3 specifies Assumption 4.3 for model-based hypothesis classes. For Assumption 4.2, we also need structural assumptions on the MDP, Given an MDP with generalized eluder dimension degc, we have the following corollary of our main theoretical result (Theorem 4.4).
Corollary 5.4 (Online regret of MEX: model-based hypothesis). Given an MDP with generalized eluder coefficient de (-) and a finite model-bar based hypothesis class H with f H. by setting
(cPv(L/VHK
11 1=
(Hogg(H/)) + log((?())) K"
then the regret of Algorithm 1 after K episodes is upper bounded by: with probability at least 1 8,
Regret(K) S V / VHK) (H log(H/6) + log((H()) K, (5.5)
Corollary 5.4 can directly specified to MDPs with low GEC, including MDPs with low witness rank [67]. We refer to Appendix E.2 for detailed discussion.

---

Experiments
In this section, we aim answer the following two questions: (a) What are the practical approaches to implementing MEX in both model-based (MEX-MB) and model-free (MEX-MF) settings? (b) Can MEX handle challenging exploration tasks, especially in sparse reward scenarios?
Experimental setups. We evaluate the effectiveness of MEX by assessing its performance in both standard gym locomotion tasks and sparse reward locomotion and navigation tasks within the MuloCo [71] environment. For sparse reward tasks, we select cheetah-vel, walker-vel, hopper-vel, ant-vel, and ant-goal adapted from Yu al. [83], where the agent receives reward only when it successfully attains the desired velocity or goal. To adapt to deep RI. settings, we consider infinite- horizon 7-discounted MDPs and MEX variants. We report the results averaged over five random seeds. The full experimental settings are in Appendix H.
Implementation details. For the model-based variant MEX-MB,
the following objective: max max E (x,a,, )~8 [log (a r xr, a)] + + Ea-a [VF (x)]
(6.1)
where we denote by a the initial state distribution, 3 the replay buffer, and n/ corresponds to 1/n the previous theory sections. We leverage the score function to obtain the model value gradient V V.V. in similar way to likelihood ratio policy gradient [70], with the gradient of action log-likelihood replaced by the gradient of state and reward log- -illieelloood in the model. Specifically.
V Exwo VF, (x)] = 1,, (1+ >VF (x') - QF, a)) V log I. oa . 1122,0) 22).)
(6.2)
where 73 is the trajectory under policy and transition P'., starting from σ.. We refer the readers to previous works [62, 76] for a derivation of (6.2). The model ø and policy π in (6.1) are updated iteratively in a Dyna [68] style, where model-free policy updates are performed on model-generated data. Particularly, we adopt SAC [30] to update the policy and estimate the value Q7, by performing temporal difference the model data generated by Ps. We also follow [62] update the model using mini-batches from B and normalize the advantage Ty + TV? - Q within each mini-batch.
For the model-free variant MEX-MF, we observe from (3.2) that adding a maximization bias term to the standard TD error is sufficient for exploration. However, this may lead to instabilities as the bias term only involves the state-action value function of the current policy, and thus the policy may be ever-changing. To address this issue, we adopt similar treatment in CQL [42] by subtracting bascline mate-accioo value from random policy μ = Unif(.A) and obtain the following objective:
max max Eg (r- ( 10 (a', d') 2)))xa))² + n/ Es [Eawa [eu a) Qo a)]- (6.3)
0
We update 0 and ग in (6.3) iteratively in an actor-critic fashion. Due to space limits, we refer the readers to Appendix H for more implementation details of MEX-MF.
Results. We report the performance of MEX-MB and MEX-MF MF in Figures and 2, respectively. We compare MEX with MBPO [34], where our method differs from MBPO only in the inclusion of the value gradient in (6.2) during model updates. We find that MEX-MB offers an easy implementation with minimal computational overhead and yet remains highly effective across sparse and standard MuloCo tasks. Notably, in the sparse reward settings, MEX-MB excels at achieving the goal velocity and outperforms MBPO by stable margin. In standard gym tasks, MEX-MB showcases greater sample efficiency in challenging high-dimensional tasks with higher asymptotic returns.
We then compare MEX-MF with the model-free baseline TD3 [27]. We observe that TD3 fails in many sparse reward tasks, while MEX-MF significantly boosts the performance. standard MuJoCo gym tasks, MEX-MP also steadily outperforms TD3 with faster convergence and higher final returns.
7 Conclusions
In this paper, we introduce a novel RL algorithm Mnneework-Maximizeee to Explore (MEX)-aini)) aimed at striking balance between exploration and exploitation in online learning scenarios. MEX is provably sample-efficient under general function approximations and is easy to implement. Theoretically, we prove that under mild structural assumptions (low generalized cluder coefficient (GEC)), MEX achieves

---

Figure 1: Model-based MEX MBX-MB in sparse and standard MuJoCo locomotion tasks.
Figure 2: Model-free MEX-MB in sparse and standard MuJoCo locomotion tasks.
-(VK)-nnlin regret for MDPs. We further extend the definition GEC and MEX framework to two-player zero-sum Markov games (see Appendix C) and also prove the ((VK))oollnee regret. In practice, adapt MEX deep RL methods in both model-based and model-free styles and apply them to sparse-rewarr MuJoCo environments, outperforming baselines significantly. We hope our work can shed light future research of designing both statistically efficient and practically effective RL algorithms with powerful function approximation.
Acknowledgement
Zhaoran Wang acknowledges National Science Foundation (Awards 2048075, 2008827, 2015568, 1934931), Simons Institute (Theory of Reinforcement Learning), Amazon, J.P. Morgan, and Two Sigma for their supports.
References
[1] ABBASI-YADEE YADKORI, Y., PÁL, D. and SZEPESV ÁRI, C. (2011). Improved algorithms for linear stochastic bandits. Advances neural information processing systems 24.
[2] AGARWAI, A. and ZhANG, T. (2022). Model-based with optimistic posterior sampling: Structural conditions and sample complexity. arXiv preprint arXiv:2206.07659)
[3] AUBRET, A., MATIGNON, L. and HASSAS, S. (2019). A survey on intrinsic motivation in reinforcement learning.
[4] AUER, P., CESA-BIANCHI, N. and FISCHER, P. (2002). Finite-time analysis of the multiarmed bandit problem. Machine learning 47 235-256.
10

---

[5] AYOUB, A., JIA, Z., SZEPESVARI, C., WANG, M. and YANG, L. (2020). Model-bases reinforcement learning with value-targeted regression. International Conference on Machine Learning. PMLR.
[6] AZAR, M. G., OSBAND, I. and MUNOS, R. (2017). Minimax regret bounds for reinforcement learning. In International Conference on Machine Learning. PMLR.
[7] BAI, Y. and JIN, C. (2020). Provable self-play algorithms for competitive reinforcement learning. In International Conference on Machine Learning. PMLR.
[8] BAI, Y., JIN, C. and Yu, T. (2020). Near-optimal reinforcement learning with self-play. arXiv preprint arXiv:2006. 200007700..20077
[9] BELLEMARE, M., SRINTVASAN, S., OSTROVSKI, G., SCHAUL, T., SAXTON, D. and MUNOS, R. (2016). Unifying count-based exploration and intrinsic motivation. Advances in neural information processing systems 29.
[10] BLANCHET. J., LU, M., ZHANG, T. and ZHONG, H. (2023). Double pessimism is provably efficient for distributionally robust offline reinforcement learning: Generic algorithm and robust partial coverage. arXiv preprint arXiv:2305.0966 096559.
[11] BURDA, Y., EDWARDS, H., STORKEY, A. and KLIMOV, O. (2018). Exploration by random network distillation. arXiv preprint arXiv:1810.12899
[12] CAI, Q., YANG, Z., JIN, C. and WANG, Z. (2020). Provably efficient exploration in policy optimization. In International Conference on Machine Learning. PMLR.
[13] CHENN, F., MEI, S. and BAI, Y. (2022). Unified algorithms for rl with decision-estimattion coefficients: No-regret, pac, and reward-free learning. arXiv preprint arXiv:2209. 11744
[14] CHEN, R. Y., SIDOR, S., ABBEEL, P. and SCHULMAN, J. (2017). Ucb exploration via g-ensembles. arXív preprint arXiv: 1706.01502.
[15] CHEN, Z., LI, C. J., YUAN, A.. Gu. Q. and JORDAN, M. (2022). A general frame- work for sample-efficient function approximation in reinforcement learning, arXiv preprint arXiv:2209. 15634
[16] CHEN, Z., ZHOU, D. and Gu, Q. (2021). Almost optimal algorithms for two-player Markov games with linear function approximation. arXiv preprint arXiv:2102.074000
[17] CHOI, J., GUo, Y., MOCZULSKI, M.. Oh, J., WU, N., NOROUZI, M. and LEE, H. (2018). Contingency-awand exploration in reinforcement learning. arXiv preprini arXiv: 18/1.01488
[18] CHUA, K., CALANDRA, R., MCALLISTER, R. and LEVINE, S. (2018). Deep reinforcement learning a handful of trials using probabilistic dynamics models. Advances in neural information processing systems 31.
[19] DANN, C., MOHRI, M., ZHANG, T. and ZIMMERT, J. (2021). A provably efficient model-free posterior sampling method for episodic reinforcement learning. Advances in Neural Information Processing Systems 34 12040-12051.
[20] DU, S., KAKADE, S., LEE, J., LOVETT, S., MAHAJAN, G., SUN, W. and WANG, R. (2021). Bilinear classes: A structural framework for provable generalization in rl. In International Conference on Machine Learning. PMLR.
[21] EYSENBACH, B., KHAZATSKY, A., LEVINE, S. and SALAKHUTDINOV, R. R. (2022). Mis- matched no more: Joint model policy optimization for model-based rl. Advances in Neural Information Processing Systems 35 23230-23243.
[22] FILAR, J. and VRIEZE, K. (2012). Competitive Markov decision processes. Springer Science & Business Media.
[23] FOSTER, J., GOLOWICH, N. and HAN, (2023). Tight guarantees for interactive decision making with the decision-estimation coefficient. arXiv preprint arXiv:2301.88215

---

[24] FOSTER, D. J.. GOLOWICH, N., QIAN, J., RAKHLIN, A. and SEKHARI, A. (2022). A note on model-free reinforcement learning with the decision-estimation coefficient. arXiv preprint arXiv:2211. 142500.
[25] FOSTER, D. J., KAKADE, S. M., QIAN, J. and RAKHLIN, A. (2021). The statistical complexity of interactive decision making. arXiv preprint arXiv:21 13487
[26] FREEDMAN, D. A. (1975). On tail probabilities for martingales. the Annals Probability 100-118.
[27] FUJмото, S., HOOF, H. and MEGER, D. (2018). Addressing function approximation error in actor-critic methods. International conference on machine learning. PMLR.
[28] GUO, H., CAL, Q. ZIIANG, Y., YANG, Z. and WANG, Z. (2022). Provably efficient offline reinforcement learning for partially observable markov decision processes. In International Conference on Machine Learning. PMLR.
[29] HAARNOJA, T., ZHOU, A., ABBEEL, P. and LEVINE, S. (2018). Off-policy maximum entropy deep reinforcement learning with a stochastic actor. In Proceedings of the 35th International Conference on machine learning (ICML-18).
[30] HAARNOJA, T., ZIIOU, A., ABBEEL, P. and LEVINE, S. (2018). Soft actor-critic: Off- policy maximum entropy deep reinforcement learning with a stochastic actor. In International conference on machine learning. PMLR.
[31] HOUTHOOFT, R., CHEN, X., DUAN, Y., SCHULMAN, J., DE TURCK, F. and ABBEEL, P. (2016). Vime: Variational information maximizing exploration, Advances neural information processing systems 29.
[32] HUANG, B., LEE, J. D., WANG, Z. and YANG, Z. (2021). Towards general function approxi- mation in zero-sum markov games. arXiv preprint arXiv:2107.
[33] HUNG, Y.-H., HSIEH, P.-C., LIU, X. and KUMAR, P. (2021). Reward-biased maximum likelihood estimation for linear stochastic bandits. In Proceedings of the AAAI Conference on Artificial Intelligence, vol. 35.
[34] JANNER, M., FU, J., ZHANG, M. and LEVINE, (2019). When to trust your model: Model- based policy optimization. Advances in neural information processing systems 32.
[35] JIANG, N., KRISHNAMURTHY, A., AGARWAL, A., LANGFORD, J. and SCHAPIRE, R. E. (2017). Contextual decision processes with low Bellman rank are PAC-learnable. In Proceedings the 34th International Conference on Machine Learning, vol. of Proceedings of Machine Learning Research. PMLR.
[36] JIANG, N., KRISHNAMURTHY, A., AGARWAL, A., LANGFORD, J. and SCHAPIRE, R. E. (2017). Contextual decision processes with low bellman rank are pac-learnable. In International Conference Machine Learning. PMLR.
[37] JIN, C., LIU, Q. and MIRYOOSEFI, S. (2021). Bellman eluder dimension: New rich classes of rl problems, and sample-efficient algorithms. Advances in Neural Information Processing Systems 34.
[38] JIN, C., LIU, Q. and YU, T. (2022). The power of exploiter: Provable multi-agent rl in large state spaces. In International Conference on Machine Learning. PMLR.
[39] JIN, C., YANG, Z., WANG, Z. and JORDAN, M. I. (2020). Provably efficient reinforcement learning with linear function approximation. In Conference on Learning Theory. PMLR.
[40] JIN, Y., YANG, Z. and WANG, Z. (2021). Is pessimism provably efficient for offline rl? In International Conference Machine Learning. PMLR.
[41] KONDA, V. and TSITSIKLIS, (1999). Actor-critic algorithms. In Advances in Neural Information Processing Systems (S. Solla, T. Leen and K. Müller, eds.), vol. 12. MIT Press.
12

---

[42] KUMAR, A., ZHOU, A., TUCKER, G. and LEVINE, S. (2020). Conservative q-learning for offline reinforcement learning. Advances in Neural Information Processing Systems 33 1179-1191.
[43] KUMAR, P. and BECKER, A. (1982). new family of optimal adaptive controllers for markov chains. JEEE Transactions on Automatic Control 27 137-146.
[44] KURUTACH, T., CLAVERA, I,, DUAN, Y., TAMAR, A. and ABBEEL, P. (2018). Model- ensemble trust-region policy optimization. arXiv preprint 18X.v2180..10592.
[45] LEE, K., LASKIN, M., SRINIVAS, A. and ABBEEL, P. (2021). Sunrise: A simple unified framework for ensemble learning in deep reinforcement learning. In International Conference on Machine Learning. PMLR.
[46] LIU, Q., CHINGG, A., SZEPESVÁRI, C. and JIN, C. (2022). When is partially observable reinforcement learning not scary? arXiv preprint 2204:22204.08667.
[47] LIU, Q., Yu, T., BAI, Y. and JIN, C. (2020). A sharp analysis of model- reinforcement learning with self-play. arXiv preprint arXiv20010.06004
[48] LIU, X., HSIEH, P.-C., HUNG, Y. H., BиATTACHARYA, A. and KUMAR, P. (2020). Explo- ration through reward biasing: Reward-biased maximum likelihood estimation for stochastic multi-armed bandits. In International Conference Machine Learning. PMLR.
[49] LIU, Z., LU, M., WANG, Z., JORDAN, M. and YANG, Z. (2022). Welfare maximization com- petitive equilibrium: Reinforcement learning for markov exchange economy. In International Conference on Machine Learning. PMLR.
[50] LIU, Z., ZHANG, Y., FU, Z., YANG, Z. and WANG, Z. (2022). Learning from demonstra- tion: Provably efficient adversarial policy imitation with linear function approximation. In International Conference on Machine Learning. PMLR.
[51] LOPES, M., LANG, T., TOUSSAINT, M. and OUDEYER, P.-Y. (2012). Exploration in model- based reinforcement learning by empirically estimating learning progress. Advances in neural information processing systems 25.
[52] LU, M., MIN, Y., WANG, and YANG, Z. (2022). Pessimism in the face of confounders: Prov- ably efficient offline reinforcement learning in partially observable markov decision processes. arXiv preprint arXiv:2205. 13589.
[53] LU, X. and VAN ROY, B. (2017). Ensemble sampling. Advances in neural information processing systems 30.
[54] METE, A., SINGH, R. and KUMAR, P. (2022). Augmented rbmle-uch approach for adaptive control of linear quadratic systems. Advances in Neural Information Processing Systems 35 9302-9314.
[55] METE, A.. SINGH, R. and KUMAR, P. (2022). The rbmle method for reinforcement learning. In 2022 56th Annual Conference on Information Sciences and Systems (CISS). IEEE.
[56) METE, A., SINGH, R., LIU, X. and KUMAR, P. (2021). Reward biased maximum likelihood estimation for reinforcement learning. In Learning for Dynamics and Control. PMLR.
[57] MODI, A., JIANG, N., TEWARI, A. and SINGH, S. (2020). Sample complexity of reinforcement learning using linearly combined model ensembles. In International Conference on Artificial Intelligence and Statistics. PMLR.
[58] MOHAMED, S. and JIMENEZ REZENDE, D. (2015). Variational information maximisation for intrinsically motivated reinforcement learning. Advances in neural information processing systems 28.
[59] OSBAND, I., BLUNDELLL C., PRITZEL, A. and VAN ROY, (2016). Deep exploration via bootstrapped dqn. Advances in neural information processing systems 29.
13

---

[60] PATHAK, D., AGRAWAL, P., EFROS, A. A. and DARRELL, T. (2017). Curiosity driven exploration by self-supervised prediction. In International conference on machine learning. PMLR.
[61] PUTERMAN, M. L. (2014). Markov decision processes: discrete stochastic dynamic program- ming. John Wiley & Sons.
[62] RIGTER, M., LACERDA, B. and HAWES, N. (2022). Rambo-rl: Robust adversarial model-based offline reinforcement learning. arXiv preprint urXiv:2204.12581
[63] RUSSO, D. and VAN RoY, B. (2013), Eluder dimension and the sample complexity of optimistic exploration. Advances Neural Information Processing Systems 26.
[64] STADIE, B. C., LEVINE, S. and ABBEEL, P. (2015). Incentivizing exploration in reinforcement learning with deep predictive models. arXiv preprint arXiv:1507.0000 000800
[65] SUN, H., HAN, L., YANG, R., MA, X., GUO, J. and ZHOU, B. (2022). Exploit reward shifting in value-based deep-rl: Optimistie curiosity- based exploration and conservative exploitation via linear reward shaping. Advances in Neural Information Processing Systems 35 37719-37734.
[66] SUN, H., XU, Z., FANG, M. and ZHOU, B. (2022). Supervised q-learning can be strong baseline for continuous control. In NeurIPS 2022 Foundation Models for Decision Making Workshop.
[67] SUN, W., JIANG, N., KRISHNAMURTHY, A., AGARWAL, A. and LANGFORD, J. (2019). Model-based rl in contextual decision processes: Pac bounds and exponential improvements over model-free approaches. Conference on learning theory. PMLR.
[68] SUTTON, R. S. (1990). Integrated architectures for learning, planning, and reacting based on approximating dynamic programming. In Machine learning proceedings 1990, Elsevier, 216-224.
[69] SUTTON, R. S. and BARTO, A. G. (2018). Reinforcement learning: An introduction.
[70] SUTTON, R. S., MCALLESTER, D., SINGH, S. and MANSOUR, (1999). Policy gradi- ent methods for reinforcement learning with function approximation. Advances in neural information processing systems 12.
[71] TODOROV, E., EREZ, T. and TASSA, Y. (2012). Mujoco: A physics engine for model-based control. In 2012 IEEE/RSJ international conference on intelligent robots and systems. IEEE.
[72] WAINWRIGHT, M. (2019). High-dimensional statistics: non-asymptotic viewpoint, vol. 48. Cambridge university press.
[73] WANG, R., SALAKHUTDINOV, R. R. and YANG, L. (2020). Reinforcement learning with gen- eral value function approximation: Provably efficient approach via bounded eluder dimension. Advances in Neural Information Processing Systems 33 6133-6135.
[74] WANG, Y., WANG, R., DU, S. S. and KRISHNAMURTHY. A. (2019). Optimism in reinforce- ment learning with generalized linear function approximation. arXiv preprint 1r11v:1912.04136
[75] WIERING, M. A. and VAN HASSELT, H. (2008). Ensemble algorithms in reinforcement learning. IEEE Transactions on Systems, Man, and Cybernetics, Part B (Cyberneties) 38 930-936.
[76] Wu, C., LI, T., ZHANG, Z. and Yu, Y. (2022). Bayesian optimistic optimization: Optimistic exploration for model-based reinforcement learning. Advances in Neural Information Processing Systems 35 14210-14223.
[77] XIE, Q. CHEN, Y., WANG, Z. and YANG, Z. (2020). Learning zero-sum simultaneous-move markov games using function approximation and correlated equilibrium. In Conference on learning theory. PMLR.
14

---

[78] XIE, T., CHENG, C.-A., JIANG, N., MINEIRO, P. and AGARWAL, A. (2021). Bellman- consistent pessimism for offline reinforcement learning. Advances neural information processing systems 34
[79] XIE, T., FOSTER, D. J., BAI, Y., JIANG, N. and KAKADE, S. M. (2022). The role of coverage in online reinforcement learning. arXiv preprint arXiv:2210.04157.
[80] XIONG, W., ZHONG, H., SHI, C., SHEN, C. and ZHANG, T. (2022). A self-play posterior sampling algorithm for zero-sum Markov games. In Proceedings of the 39th International Conference on Machine Learning, vol. 162 of Proceedings of Machine Learning Research. PMLR.
[81] YANG, and WANG, M. (2019). Sample-optimal parametric q-learning using linearly additive features. In International Conference on Machine Learning. PMLR.
[82] YANG, Z., JIN, C., WANG, Z., WANG, M. and JORDAN, M. (2020). Provably efficient reinforcement learning with kernel and neural function approximations. Advances in Neural Information Processing Systems 33 13903-13916.
[83] YU. T.,, QUILLEN, D., HE, Z., JULIAN, R., HAUSMAN, K., FINN, C. and LEVINE, S. (2020). Meta-world: A benchmark and evaluation for multi-task and meta reinforcement learning. In Conference robot learning. PMLR.
[84] ZANETTE, A., BRANDFONBRENER, D., BRUNSKILL, E., PIROTTA, M. and LAZARIC, A. (2020). Frequentist regret bounds for randomized least-squares value iteration. In International Conference on Artificial Intelligence and Statistics. PMLR.
[85] ZANETTE, A., LAZARIC, A., KOCHENDERFER, M. and BRUNSKILL, E. (2020). Learning near optimal policies with low inherent bellman error. In International Conference on Machine Learning. PMLR.
[86] ZUA. D., MA. W., YUAN, L., HU, X. and LIU, (2021). Rank the episodes: A simple approach for exploration in sereeddurall--eeeratte environments. arXiv preprint 101iv2200..0115...
[87] ZHANG, T. (2022). Feel-good thompson sampling for contextual bandits and reinforcement learning. SIAM Journal Mathematics of Data Science 4 834-857.
[88] ZHANG, T. (2022). Mathematical analysis of machine learning algorithms.
[89] ZHONG, H., XIONG, W., ZHENG, S., WANG, L., WANG, Z., YANG, Z. and ZHANG, T. (2022). A posterior sampling framework for interactive decision making. arXiv preprint arXiv:221 1.01962.
[90] ZHONG, H. and ZHANG, T. (2023). A theoretical analysis of optimistic proximal policy optimization in linear markov decision processes. arXiv preprint arXiv:2305.08841
[91] ZHOU, D., GU, Q. and SZEPESVARI, C. (2021). Nearly minimax optimal reinforcement learning for linear mixture markov decision processes. In Conference on Learning Theory. PMLR.
15


Reviews:
[{"review_id": "jcXYp5sRBC", "reviewer": "Reviewer_44XZ", "summary": "This paper proposes an RL framework, maximize to explore (MEX), that requires solving an unconstrained optimization which encompasses estimation, planning, and exploration. It proposes both model-free and model-based algorithms and further extends this framework to zero-sum Markov game setting. All these algorithms are proved to be efficient. It also designs practical algorithms based on existing deep RL baselines. Experimental results show that the proposed algorithms outperform baselines in sparse reward environments.", "questions": "While the theory indicates that the coefficient balancing value and evidence should change over time, it is set to be a constant in practice. Why is it the case?", "limitations": "This paper has not discussed its limitations, especially about optimization aspects of the learning objective and the practicality of assumptions.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "This paper proposes a general framework that is adapted to various settings while enjoying favorable theoretical guarantee. Its result generalizes previous ones and is important. It is technically sound, clearly written, and well organized.", "weaknesses": "The idea of maximizing to explore is not novel, and previous work are not adequately cited. This line of research is first developed by [Kumar & Becker (1982)](https://ieeexplore.ieee.org/document/1102878) who proposes an estimation criterion that biases maximum likelihood estimation with the cost (or value) of decision. In recent years, several work ([Liu et al., 2020](https://proceedings.mlr.press/v119/liu20g.html); [Mete et al., 2021](https://proceedings.mlr.press/v144/mete21a.html); [Hung et al., 2021](https://ojs.aaai.org/index.php/AAAI/article/view/16961); [Mete et al., 2022](https://ieeexplore.ieee.org/document/9751189/); [Mete et al., 2022](https://proceedings.neurips.cc/paper_files/paper/2022/hash/3c601cd5866099648c6dc783e7f39858-Abstract-Conference.html); [Wu et al., 2022](https://proceedings.neurips.cc/paper_files/paper/2022/hash/5bcb807ae43ad0851a6ba6162a866404-Abstract-Conference.html)) have applied this method to different settings and proved some theoretical results. In particular, [Wu et al. (2022)](https://proceedings.neurips.cc/paper_files/paper/2022/hash/5bcb807ae43ad0851a6ba6162a866404-Abstract-Conference.html) gives a theoretical result similar to the one for model-based MEX in this paper. Rather than completely ignoring previous efforts, it is more appropriate to propose MEX as a further generalization of previous research. \n\nThe proof of regret bound in this paper relies on the low generalized eluder coefficient assumption. However, it is not discussed whether this assumption hold in practice especially when the hypothesis class is parameterized by neural networks.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "\n**Weakness 1: Lacking discussions of previous research that have similar ideas.**\n\nThanks very much for pointing these related works out! We will add these works and discuss them in detail in the revision. In the following, we compare our work with these works briefly.\n\n[1]: While this work firstly proposed an estimation criterion that biases maximum likelihood estimation with the cost/value, their algorithm is actually different from ours, by their Eqn. (6) - (8) in Section 3, their algorithm performs the estimation of model $\\alpha$ and policy optimization separately, for which they only obtained asymptotic convergence guarantees. Also, how well their decision rule explores remains unknown in theory. In contrast, MEX adopts a single optimization objective that combines estimation with policy optimization, which also ensures sample-efficient online exploration.\n\n[2,3,4,5,6]: They study Reward-Biased Maximum Likelihood Estimation (RBMLE) in Multi-arm bandit ([2]), Linear Stochastic Bandits ([3]), tabular RL ([4]), and Linear Quadratic Regulator settings (a linear parameterized model of MDP,[5,6]) and also obtain the theoretical guarantees. While these settings are special cases for our proposed algorithms and our proven theoretical guarantee can also be generalized to these concrete cases. As we claim in this paper, our main contribution is to address the exploration-exploitation trade-off issue under general function approximation, which makes our work differs from these papers.\n\n\n[7]: It's true that this work considers an algorithm similar to MEX, but our theory differs from theirs in both techniques and results. Our theory is based upon a unified framework of online RL with general function approximations, which covers their setup for model-based hypothesis with kernel function approximation (RKHS). More importantly, they derived asymptotic regret of their algorithm based upon certain uniform boundedness and asymptotic normality assumptions, which are relatively strong conditions. In contrast, we derived finite sample regret upper bound for MEX, and the only fundamental assumption needed is a lower Generalized Eluder Coefficient (GEC) MDP, which contains almost all known theoretically tractable MDP classes (therefore covers their RKHS model). Finally, our paper further extends MEX to two-player zero-sum Markov games where similar algorithms and theories are previously unknown to the best of our knowledge.\n\nAlso, the works mentioned above do not design experiments in deep RL environments, while we propose deep RL implementations and demonstrate their effectiveness in MuJoco environment. \n\n**Weakness 2: It is not discussed whether the low GEC assumption hold in practice especially when the hypothesis class is parameterized by neural networks.**\n\nWe note Proposition 17.20 of [8] provides a general estimation result for GEC when the function class can be embedded into an RKHS. And the original GEC paper [9] also provides many examples that are beyond linear function approximation and can capture non-linearity to some degree.\n\n**Weakness 3: It seems that the provided code for MEX-MB is wrong and is merely an implementation of MBPO.**\n\nOur code for MEX-MB is adapted from MBPO. As described in Lines 341-344, MEX-MB differs from MBPO only in the model update procedure by adding the model value gradient during model updates. The corresponding code can be found in 'MEX_MB/mbrl/models/one_dim_tr_model.py'. This also shows that our method is easy to implement with minimal computational overhead to boost performance.\n\n**Question 1: While the theory indicates that the coefficient balancing value and evidence should change over time, it is set to be a constant in practice. Why is it the case?**\n\nWe note that both in the theory and experiments, we set the coefficient as a constant. In theory, we set it to be $1/\\sqrt{K}$ instead of $1/\\sqrt{k}$, where $K$ is the number of episodes for the entire online learning process.\n\n**References:**\n\n[1] P. Kumar and A. Becker, \"A new family of optimal adaptive controllers for Markov chains,\" in IEEE Transactions on Automatic Control, vol. 27, no. 1, pp. 137-146, February 1982, doi: 10.1109/TAC.1982.1102878.\n\n[2] Liu, Xi, et al. \"Exploration through reward biasing: Reward-biased maximum likelihood estimation for stochastic multi-armed bandits.\" International Conference on Machine Learning. PMLR, 2020.\n\n[3] Hung, Y.-H., Hsieh, P.-C., Liu, X., & Kumar, P. R. (2021). Reward-Biased Maximum Likelihood Estimation for Linear Stochastic Bandits. Proceedings of the AAAI Conference on Artificial Intelligence, 35(9), 7874-7882.\n\n[4] Mete, Akshay, et al. \"Reward biased maximum likelihood estimation for reinforcement learning.\" Learning for Dynamics and Control. PMLR, 2021.\n\n[5] Mete, Akshay, Rahul Singh, and P. R. Kumar. \"The RBMLE method for Reinforcement Learning.\" 2022 56th Annual Conference on Information Sciences and Systems (CISS). IEEE, 2022.\n\n[6] Mete, Akshay, Rahul Singh, and P. R. Kumar. \"Augmented RBMLE-UCB approach for adaptive control of linear quadratic systems.\" Advances in Neural Information Processing Systems 35 (2022): 9302-9314.\n\n[7] Wu, Chenyang, et al. \"Bayesian optimistic optimization: Optimistic exploration for model-based reinforcement learning.\" Advances in neural information processing systems 35 (2022): 14210-14223.\n\n[8] Zhang, Tong. Mathematical analysis of machine learning algorithms. Cambridge University Press, 2023.\n\n[9] Zhong, Han, et al. \"A posterior sampling framework for interactive decision making.\" *arXiv preprint arXiv:2211.01962* (2022).\n"}, {"review_id": "tEfuak0p7A", "reviewer": "Reviewer_vhgd", "summary": "The paper presents a unified objective for optimizing regret in online RL algorithms with theoretical justification and experimental evaluation. The objective crucially dos not dependent on posterior estimation or bi-level optimization, making it easier to implement in practice than previous theory motivated algorithms. The authors provide a thorough theoretical analysis of their framework, covering both model-based and model-free approaches.", "questions": "Assumption 4.3 and Proposition 5: Are there requirements on the exploration policy to guarantee that sufficient coverage is obtained for the supervised learning guarantee? I might be misunderstanding the exact details here, but for the supervised guarantee to hold, it feels like some assumptions on the data is needed?\n\nSection 5 (line 279) makes it seem like the choice of $l$ depends on characteristics of the MDP. If so, what aspects of the MDP need to be know a priori to make this choice?\n\nLine 298: Is the choice of the Hellinger distance crucial, or would other choices work here as well?\n\n6.2 If a differentiable model of the environment is learned, would it be possible to obtain the gradient wrt to the value function directly, without resorting to a PG style estimator? This would be directly implementable in MBPO, as the model is fully differentiable using reparametrization.\n\nThe experimental section results miss some standard information: what implementation of MBPO was used (this is also important to obtain hyperparameters), how where the environments chosen (especially why is Humanoid missing), and what is denoted by the shaded area in the plots.\n\nSeveral times \"specific MDP structure\" is mentioned (lines201, 275, 304 [I assume here it refers to the GEC assumption?]), but the authors do not fully clarify what is meant by this. What is meant by this?", "limitations": "The authors do not address the limitations of their work. Potential discussion points are: the reliance on structural assumptions in the MDP are not provided in-depth, and the tuning of the parameter $\\eta$.", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "The paper is very well crafted, and provides an algorithm that is both theoretically sound and empirically impactful, which is always a great achievement. Even though the presentation is necessarily dense at times, given the theoretical nature of the main contribution, the paper is fairly accessible, with the core intuitions mostly presented well. The results and the practical algorithm presented in the empirical section at the end are surprisingly intuitive and seem straightforward to implement on top of several model-based RL algorithms, not just MBPO.\n\nCaveat: I am not necessarily qualified to comment on the correctness of all mathematical details or the impact of the theoretical contributions. I am overall familiar with most concepts used (i.e. Bellman and Eluder rank) but not a core RL theory researcher, so I might be missing some details.", "weaknesses": "Given the theoretical nature of the paper, the presentation is necessarily dense, which makes it hard to grasp a couple of intuitive concepts. While the authors do their best to present all main components, here are some suggestions for improvement:\n- The authors use generic functions several times, most prominently in Section 3, 3.2 and 3.3. They defer concrete realizations to later, but it would be helpful to provide these examples earlier so that readers unfamiliar with the exact approach have an easier time understanding the role that these function play. (Similarly in Section 5, 5.1)\n- The authors use a unified notation for model-free and model-based hypotheses. While this makes generic statements easier to provide, it led to some confusion on my part because I lost track of whether a model-free or model-based hypothesis was meant at some points. Potentially a specialized notation would clarify these whenever a concrete algorithmic framework is discussed.\n- While I know that this is not always the main stylistic choice in theory papers, I want to encourage the authors to explain why each assumption is used, i.e. what role they play in proofs. This is especially important for 3.1, which is very abstract and hard to relate to anything this early in the presentation.\n\nThe role of the exploration policy is not elaborated on in the concrete implementation, etc. This is promised in line 199, but I cannot find a note on the exploration policy in Section 5.\n\nThe full loss presented in 6.3 does not clarify how the additional term fulfills all the requirements introduced in Section 4. While I was able to piece together most of it, an explicit explanation here would greatly improve the ease with which the role of the assumptions can be understood. In addition, some intuitive description of what this objective optimizes would be nice to have.\n\nThe experimental section is missing a discussion on how $\\eta'$ is set in practice (also, why is $\\eta'$ used instead of $\\eta$?).\n\n211: for seek of -> for the sake of?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Weakness 1: The presentation is necessarily dense, making it hard to grasp a couple of intuitive concepts.**\n\nThanks for the constructive comments! We address them in the following.\n\n-  *Function approximations:*  we will present the concrete realizations of the general function approximations ealier to make the audience get familiar more easily. We will use $\\mathcal{F}$ and $\\mathcal{M}$ to distinguish model-free and model-based hypotheses in the revised version. \n- *Bellman completeness assumption:* Please refer to **General Response Q1** for an explanation.\n\n**Weakness 3: The role of the exploration policy is not elaborated for the concrete implementations.** \n\nThanks for pointing it out. We actually referred to Appendix E for detailed discussions of each concrete example, including the choice of the exploration policy. We will add these to the main texts in the revision. \n\n**Weakness 4: About the loss Eqn. (6.3) used in experiments.**\n\nWe will give more elaboration in the revision. Intuitively, the whole second term of Eqn. (6.3) corresponds to the exploration term $\\max_{a_1\\in\\mathcal{A}}Q_{1,f}(x_1,a_1)$ in Sections 3 & 4, where we also used some tricks to stabilize training. In specific, motivated by CQL [1], we subtract the model value $E_{x\\sim\\beta}E_{a\\sim\\pi(\\cdot|x)}[Q_{\\theta} (x,a)]$ by $E_{x\\sim\\beta}E_{a\\sim \\mu}[Q_{\\theta}(x,a)]$, where $\\beta$ is the state distribution of the replay buffer, $Q_\\theta$ is the parameterized Q-network, and $\\mu$ is the uniform distribution over the actions. By introducing $E_{x\\sim\\beta}E_{a\\sim\\mu}[Q_{\\theta}(x,a)]$, we can reduce the variance during optimizing $\\theta$ for the model value, which stabilizes the training process.\n\n**Weakness 5: About the hyper-parameter $\\eta'$ in experiment.**\n\nPlease refer to **General Response Q2** for an explanation.\n\n**Question 1: About Assumption 4.3 and Proposition 5.**\n\n\nWe clarify that for both model-based and model-free settings, we **do not** require any coverage assumptions on the exploration policy to obtain the supervised learning guarantee. All we considered is a purely online learning protocol. The intuition is that the expectation involved in $E_{\\xi_h\\sim\\pi_{\\exp}}$ coincides with the policy to collect the data, thus the concentration ineq. doesn't require coverage conditions.\n\n**Question 2: What aspects of the MDP need to be known a priori to make the choice of $l$?**\n\n\nWe note that the technical treatment presented in line 279 is mainly due to the convention of the original GEC paper [2], where their authors mainly wanted to handle the linear mixture model in the model-free case and get a $\\sqrt{T}$-regret. Indeed, for most of the time, the loss choice is natural in practice. E.g., for the model-free case, $l$ would be the TD error $f_h(x_h,a_h) - r_h - f_{h+1}(x_{h+1})$. Meanwhile, for the model-based case, the loss estimator $\\ell$ would just be the log likelihood. We remark that the linear mixture model can be handled in a model-based manner and does not rely on the fact that its customized loss is known a priori.\n\n**Question 3: Is the choice of the Hellinger distance crucial, or would other choices work here as well?**\n\nWe note that there exist some variants of GEC using TV norm, but we can show that GEC-Hellinger is always smaller or equal to the GEC-TV. We do not include a detailed discussion on this since the main focus of this paper is the new algorithmic framework MEX. We will add a footnote to comment on this. \n\n**Question 4: 6.2 If a differentiable model of the environment is learned, would it be possible to obtain the gradient wrt to the value function directly, without using a PG style estimator?**\n\nYes, that would be possible. By adopting methods such that the planning process (corresponding to the optimal value function term in Mex's target) is differentiable, e.g., [3], we can obtain the gradient wrt to the value function directly in a differentiable model of the environment, e.g., MBPO.\n\n**Question 5: The experimental section results miss some standard information and add more experiments on the Humanoid environment.**\n\nWe used the MBPO implementation and the hyperparameters provided in the *mbrl-lib*([4]). The experiments in the paper are conducted in both the standard and the sparse-reward Mujoco locomotion tasks. We also clarify that the shaded area in all plots in the paper corresponds to the standard deviation among five random seeds.  As for the new humanoid task, we test the performance of model-based MEX in this task and report the results in Figure 1 of **General Response**, where $\\eta^\\prime=1e-3$.\n\n**Question 6: The authors do not fully clarify what is meant by \"specific MDP structure\".**\n\nThanks for pointing this out! We will elaborate on this in the revised version. To be specific, \n\n- Line 201: we mainly refer to the difference in Q-type and V-type problems in the literature: whether the action distribution used in the discrepancy loss $\\ell$ is the same as the historical one or not. If not, we need one step of uniform exploration over the action space in the exploration policy;\n- Line 275: we refer to the transition and reward model. We mean that for different MDPs, our analysis carries on in a unified manner, insead of a case-by-case one;\n- Line 304: we mean that the MDP should have some specific structures so that the GEC condition is satisfied. \n\n**References:**\n\n[1] Kumar, Aviral, et al. \"Conservative q-learning for offline reinforcement learning.\" Advances in Neural Information Processing Systems 33 (2020).\n\n[2] Zhong, Han, et al. \"A posterior sampling framework for interactive decision making.\" *arXiv preprint arXiv:2211.01962* (2022).\n\n[3] Amos, Brandon, et al. \"Differentiable mpc for end-to-end planning and control.\" Advances in neural information processing systems 31 (2018).\n\n[4] Pineda, Luis, et al. \"Mbrl-lib: A modular library for model-based reinforcement learning.\" arXiv preprint arXiv:2104.10159 (2021)."}, {"review_id": "LkjsUQGwOm", "reviewer": "Reviewer_wpGc", "summary": "This theory paper proposes an algorithmic framework where the \"hypothesis\" (model for MB methods, Q function for MF methods) for each iteration is chosen by maximizing one objective: the hypothesis likelihood (i.e., NLL for MB methods, TD error for MF methods) plus the expected returns (value function at the initial state). The paper provides regret guarantees matching prior work. The paper proposes a practical variant of the method (building on top of MBPO and TD3) that shows some promise on sparse versions of benchmark continuous control tasks (while matching performance on the standard, non-sparse versions).", "questions": "1. How important is the value of $\\eta$ for both the theoretical and empirical results?\n2. L147 \"Without loss of generality\" -- Can the authors elaborate on this point? My guess is that we can ignore stochastic rewards because we could define a new MDP that has a copy of each state for each possible reward that that state could have (and update the transition probabilities accordingly). I'm not sure why it's OK to assume that the reward function is known.\n3. There's a sense in which the proposed method resembles posterior sampling methods, by drawing a connection with Gumbel-softmax-style sampling. One way to sample a random variable is to _deterministically_ choose the value that maximizes likelihood + noise, for an appropriately chosen noise distribution (e.g., the Gumbel distribution for categorical distributions). I'm curious if we can interpret posterior sampling methods as a version of Eq. 3.1 where the first term ($V(x)$) is replaced by an appropriate noise distribution (which has nothing to do with the value). \n4. L206: Does $V_f^\\pi$ make sense for both the model-based and model-free versions of the method? For the model-based version, I'm interpreting this as the expected returns of policy $\\pi$ under model $f$. But for the model-free version, I'm unsure if this is supposed to be the expected returns of $\\pi$, or the estimate from (value function) $f$.\n5. L206, \"reduced to vanilla actor-critic\": Is this true for the model-based version of the method?\n6. Is the second term in Eq. 3.3 required?", "limitations": "Limitations are not discussed in the main paper. The appendix has a cursory paragraph on limitations. I would recommend including the limitations in the main text, and including a transparent discussion of benefits/limitations of the proposed method relative to prior methods. For example, the first term in Eq. 3.1 seems to sometimes cause optimization problems. Ensemble-based methods might be more stable.", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "**Originality**: To the best of my knowledge the proposed frame work is original.\n* One prior paper that's related to the model-based version of this paper is https://arxiv.org/abs/2110.02758. This that paper lacks the theoretical contributions of this paper, and comes at the problem from a different perspective, the resulting algorithms look surprisingly similar: both learn a model that is optimized to (1) have high likelihood and (2) produce high-return policies. I'd be curious to see if the current paper also performs well on the stochastic gridworlds used in the prior paper to showcase the benefits of the \"optimistic\" model.\n\n**Clarity**: I generally found the writing clear, which is especially impressive for a large theory project packed into 9 pages. The bottom of this text block has a few suggestions for improving clarity. A few high-level things\n* The related work section is generally well written, including a pretty thorough review of prior work. One suggestion is to explain the differences from prior work. What are the limitations that this paper will address?\n* I didn't get much from reading Section 5; I'd prefer that the space be spent on more intuition for the previous section, or more empirical results.\n\n\n**Significance**: Overall, it seems like the proposed framework is a novel and potentially useful way of designing better RL algorithms. I especially appreciate the simplicity of the proposed approach. I think that the paper may be a bit closer to prior work that the paper makes it out to be (see comment under Originality, and the comment about Gumbel), but it still seems to represent somewhat of a departure from the conventional ways of thinking about RL algorithms. Like most new algorithmic frameworks, it seems like there may be a few kinks that have to be worked out empirically (how to choose $\\eta$; is there a way of implementing the model-free version without the extra CQL term). Nonetheless, it seems like the paper could inspire more work in this direction.\n\n\n**Strengths**\n* The paper is generally well written, includes a thorough review of much prior work.\n* The proposed framework is derived for both model-free and model-based algorithm.\n* An empirical version of the proposed method is applied to to reasonable continuous control tasks. This is really nice to see in a theory paper.\n", "weaknesses": "* In a few spots, I felt like the paper claims were not entirely substantiated:\n  * \"One Objective to Rule Them All\" in the title -- Without comparisons to \"all\" prior methods, I don't think this is a fair claim. Perhaps a more accurate title would be \"An Objective Fusing Estimation and Planning for Exploration\"\n  * \"algorithms predominantly undertake three tasks\" -- This seems to be describing methods based on Thompson sampling and posterior sampling, but I'm not sure that R-MAX-style methods fit this mold\n  * \"outperforms MBPO by a stable margin ... showcases greater sample efficiency\" -- I'm a bit unsure what these statements are referring to. My read of Figure 1 is that there might be statistically significant gains on 2 / 8 tasks (cheetah-vel-sparse, ant-vel-sparse). I would still vote for accepting the paper even if it only outperforms baselines on 2/8 tasks (but I think that accurately portraying the results is very important); this is especially true if we see large benefits on some tabular settings (see suggestion under Originality).\n* The paper alludes to \"data-dependent level-sets\" in a number of places, but never defines what these are. I'd recommend either including a few sentences describing similarities/differences, or moving this discussion to the appendix.\n* I have a few questions about some of the technical details (see below).\n* From a practical perspective, the model-free version of the method seems to violate conventional wisdom: many practical TD methods (e.g., TD3, MBPO) choose the Q function that has lowest Q-values, whereas the proposed method chooses the one with highest Q values. Not only does this make be a bit concerned that the theoretical framework might not always work well in practice (as evinced by the need for the additional CQL regularizer), but it also makes me wonder exactly how the model-free version of the method is implemented when combined with TD3 (does it take the min or max of the Q functions)? At least for the model-free version, one thing that might help would be to sure that using the CQL regularizer allows the _same_ method to achieve good results in both online and offline settings.\n\n\n---------------------\n\n**Minor comments**:\n* In the abstract, mention that this is going to be a theory paper. I expected this to be an empirical paper until partway through the intro, when I realized that all of the citations were referring to other theory papers. As such, I found the claim that prior methods \"involve impractical algorithmic components\" a bit strange, as prior _practical_ methods cannot require impractical components.\n* L45 -- L47: I found this part a bit unclear because it was unclear what the optimization variable is (a policy, a model, data). This point is clarified later.\n* L50: I found this part a bit unclear because it was unclear what the hypothesis class was over (policies, models, etc).\n* Some small grammar errors throughout. An automated grammar checker should catch these (e.g., dropped articles)\n* L80 -- This definition could be cut, as it's already included a few paragraphs earlier. Cutting this would make it possible to remove some of the whitespace hacks.\n* L101 -- What is \"BE\"?\n* Empirically, in many TD algorithms the TD error _increases_ as the policy improves. The standard explanation is that collecting non-zero rewards results in higher TD errors. This seems potentially related to the analysis in this paper.\n* L260 -- Including a table for comparing these prior methods might help.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Originality: Compare MEX with [1] on Gridworld environments.**\nBased on [3], we compare MEX on Gridworld with [1] in Figure 2 of **General Response**.\n\n**Clarity: Comparison to related works and organization of Section 5.**\n\nPlease see **General Response Q3** for a brief comparison. We will add the comparison and reorganize Section 5 in the revision. \n\n**Weaknenss 1:Some of the paper claims were not entirely substantiated.**\n\n- *About the title*: By using \"all\", we meant to refer to the three of \"Estimation\", \"Planning\", and \"Exploration\", because our MEX objective can fuse all three components in a single objective.\n- *About \"algorithms predominantly undertake three tasks\"*: The tasks of estimation, planning, and exploration are the main components of most existing sample-efficient online RL algorithms, including but not restricted to Thompson-sampling-style methods. Essentially, all of these components are necessary for both model-free and model-based algorithms (TS-style method can also be either model-free or model-based).\n- *About \"outperforms MBPO by a stable margin,..., showcases greater sample efficiency\":* We clarify that the mean return of MEX-MB is higher than the MBPO baseline in the sparse-reward tasks, including cheetah-vel-sparse, ant-vel-sparse, hopper-vel-sparse, and ant-vel-sparse, especially the first two. Besides, MEX-MB outperforms MBPO with fewer samples in the standard Mujoco tasks, including walker2d, half cheetah, and ant. We will revise our statement to make it more accurate.\n\n**Weakness 2: About \"data-dependent level-sets\" in a number of places.**\n\nThanks for pointing that out! We will add a concrete discussion about the \"data-dependent level-sets\" adopted by previous theoretical works. \n\n**Weakness 3: The model-free version seems to violate conventional wisdom: many practical methods (e.g., TD3, MBPO) choose the Q function that has lowest Q-values.**\n\nFirstly, the method to choose the lowest Q-value is **NOT** addressing the same problem that MEX wants to solve. TD3 chooses the lowest value between two separate Q-networks to handle the overestimation faced when estimating things like $E[\\max_{a\\in\\mathcal{A}}\\{Q(x,a)\\}]$. In contrast, MEX chooses a high Q-value in order to incentivize exploration. These two methods do not contradict each other and can be implemented simultaneously. That is, when calculating the Bellman target, one chooses the lower value from two separate Q networks. When optimizing the Q-networks, we still use the objective (6.3) that combines TD error and Q-value.\n\nSecondly, we note that the CQL regularizer is actually a kind of entropy regularization (Appendix H.2). We use this in order to stabilize training. We highlight that the sign of the regularizer here is also the **opposite** to that adopted by the original offline CQL paper.\n\nFinally, we clarify that our method to choose a high Q-value does **NOT** violate conventional wisdom. Prevalent approaches in deep online RL that achieve good exploration commonly involve a bias to high Q-values, for instance, an ensemble of neural networks [62, 48, 13 cited in paper], intrinsic motivation-driven methods [26, 3, 10 cited in paper], etc. MEX is consistent with their convention of choosing a relatively high Q-value to help exploration.\n\n**Minor comments regarding writing and organization.** \n\nThanks for all your detailed comments! We will try to improve the readability and organization of our paper following your suggestions point-by-point.\n\n**Question 1: How important is the value of $\\eta$ for both the theoretical and empirical results?**\n\nSee **General Response Q2** for an explanation.\n\n**Question 2: About the known and deterministic reward, without loss of generality.**\n\nThanks for pointing this out! The better statement is that our result can be readily generalized to the case when the reward is stochastic and unknown. The techniques have been presented in, e.g., [2]. Thanks to these previous works, we can present our results in a simplified way.\n\n**Question 3: About using Gumbel-softmax to connect MEX to posterior sampling.**\n\nThis might be correct, but it is not clear whether this could achieve the desired theoretical results if we replace the value function term with a *value-independent* noise. Also, the original Gumbel-softmax trick is operated on a finite set of choices, where for each possible choice, a Gumbel noise is added. But in our setup, we choose a function from a possibly infinite class. Thus to implement a Gumbel-softmax trick, a stochastic process indexed by $f$ is required. This is unclear and complicated in practice.\n\n**Question 4: Does $V_f^{\\pi}$ make sense for both the model-based and model-free versions of the method?**\n\nWe clarify this as follows. As discussed in Example 2.1, for the model-free version, we use $V_{h, f}(x)$ to refer to $\\max_{a\\in\\mathcal{A}}f(x,a)$. However, we **did not** use the notation $V_{h,f}^{\\pi}$. This notation only appears in some intermediate definitions in Example 2.2 for the model-based case and does not appear in the unified algorithm and theory. We may only use the notation $V_h^{\\pi}$ to refer to the value function of $\\pi$ under the true model. Please check that out in our paper.\n\n**Question 5: About the reduction to vanilla actor-critic for the model-based version of MEX.**\n\nHere we only aimed to discuss the high-level relationship between the model-free version of MEX and the vanilla actor-critic. We will make it clearer in the revision.\n\n**Question 6: Is the second term in Eqn. (3.3) required?**\n\nSee to **General Response Q1** for an explanation.\n\n[1] Eysenbach, Benjamin, et al. \"Mismatched no more: Joint model-policy optimization for model-based rl.\".\n\n[2] Agarwal, Alekh, and Tong Zhang. \"Model-based rl with optimistic posterior sampling: Structural conditions and sample complexity.\" \n\n[3] Wu, Chenyang, et al. \"Bayesian optimistic optimization: Optimistic exploration for model-based reinforcement learning.\""}, {"review_id": "ALLl0X51lS", "reviewer": "Reviewer_J9HB", "summary": "This paper studied reinforcement learning with general function approximation setting. The authors proposed a new MEX framework, which unifies the exploration and exploitation within a unconstrained optimization objective. Under the structural assumptions about low GEC, they established regret upper bound for learning with their framework. Moreover, they conducted experiments in Mujoco under both model-based and model-free setting and achieved promising results.", "questions": "(1) for the model-free setting, does there exist a general choice of $l$ function in Assumption 3.1? When Assumption 4.2 is satisfied, does $l$ function always exist?", "limitations": "N.A.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "Computational efficiency is indeed an crucial shortage of existing provably efficient algorithm frameworks. I'm glad to see some effort to investigate how to close those gaps.\n\nThe idea is clean, the proof is sound to me. The experiments look interesting and promising.", "weaknesses": "(1) For the model-free setting, the objective (Eq. 3.1) may not be as easily to optimize as it looks like. By Eq. 3.3, the definition of L_h^k, solving Eq. 3.1 requires to solving a mini-max optimization problem. \nOn the other hand, those constrained optimization objectives in previous literatures (like [1] and [2]) can also be directly converted to a Lagrangian form, which can also be regarded as one objective (a with minimax optimization problem).\nI don't think it is easy to conclude the objective in this paper is indeed easier to implement than the others.\n\n(2) There is not much technique novelty. The proof techniques can be found in previous literatures. The maximization objective is quite straightforward, which just convert the confidence interval constrained optimization objective in previous literatures to a Lagrangian style objective, although there are indeed some difference (here the dual parameter is fixed).\n\n\n[1] Jin et. al., Bellman Eluder Dimension: New Rich Classes of RL Problems, and Sample-Efficient Algorithms\n\n[2] Du et. al., Bilinear Classes: A Structural Framework for Provable Generalization in RL", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Weakness 1: For the model-free setting, the objective (3.1) may not be as easy to optimize as it looks like. By (3.3), the definition of L_h^k, solving (3.1) requires to solving a mini-max optimization problem. On the other hand, those constrained optimization objectives in previous literature (like [1, 2]) can also be directly converted to a Lagrangian form, which can also be regarded as one objective (with a minimax optimization problem). I don't think it is easy to conclude the objective in this paper is indeed easier to implement than the others.**\n\nFirstly, we highlight that MEX is a maximization objective as a whole, w.r.t. value + loss. In contrast, using the Lagrangian form to solve previous constrained optimization program gives a minimax objective w.r.t. value + dual * loss, which is indeed harder to solve than MEX. If coupled with the choice of $L_h^k$ in (3.3) [1], their target would be even harder than minimax optimization. \n\nSecondly, we need to clarify that the definition of $L_h^k$ in (3.3) is only a specific estimator construction in theory. It is indeed used to handle the double-sampling issue to achieve a sharper supervised guarantee (Proposition 5.1). Under Bellman completeness assumption (Assumption 3.1), the extra infimum term can help us to control the variance term involved in estimating things like $(E[\\mathcal{E}(f)])^2$. Please refer to **General Response Q1** for more explanation for this. On the other hand, another straightforward choice of $L_h^k$ is to use the sample mean with $m$ trajectories as the estimator to achieve a low variance at the cost of a worse estimation guarantee (see [2] for a similar algorithmic design). From this perspective, the infimum term in (3.3) is not necessary, and solving (3.1) only involves maximization instead of minimax optimization.\n\nFinally, in practice, we can simply choose $L_h^k$ to be the squared TD error as an approximation, which gives a pure maximization objective. Also, for the model-based case, a simple log-likelihood estimator (3.5) is enough, which also doesn't involve minimax optimization.\n\n**Weakness 2: There is not much technique novelty. The maximization objective is quite straightforward, which just convert the confidence interval constrained optimization objective in previous literatures to a Lagrangian style objective, although there are indeed some difference (here the dual parameter is fixed).**\n\nWe clarify our technical novelty in the following. \n\nAs discussed in our paper, MEX is not simply a lagrangian form of the optimistic planning method proposed by existing works, e.g., [1, 2]. The theoretical gap is also non-trivial. Firstly, using Lagrangian duality to transform the constrained optimization to a minimax optimization requires both the objective function and the constraints to be convex, which in general does not hold for these optimistic planning methods. Secondly, analysis techniques in the previous papers with optimistic planning can **NOT** be generalized to our algorithm, and new proof techniques are in need.\n\nTo illustrate this, we point out that in the regret decomposition (Line 871), we make a tighter analysis of the value difference $V^\\star -V_{f^k}$ (Term (i)). In traditional optimistic planning papers, they need the selected hypothesis $f^k$ to maximize $V_f$ s.t. $L(f)\\le \\beta$ for some $\\beta$. As concentration analysis tells that $L(f^\\star)\\le \\beta$, they simply upper bound the model value difference $V^\\star -V_{f^k} = V_{f^{\\star}} - V_{f^k}$  by zero. \n\nWhile in MEX, we do not solve such a constrained optimization problem. Hence we are not proving that $V^\\star -V_{f^k}\\le 0$ for the selected hypothesis $f^k$. In contrast, our MEX objective (3.1) shows that its upper bound can be further refined as $-L(f^k) +L(f^\\star)$. It turns out that this term can cancel some parts in the upper bound of the other value difference $V_{f^k} - V^{\\pi_{f^k}}$ (Term (ii) in regret decomposition). The key here is to show the concentration type inequality (Assumption 4.3). After this cancellation, the remaining parts of both Term (i) and Term (ii) are relatively easy to handle. In contrast, traditional optimistic planning papers consider to upper bound the whole Term (ii) $V_{f^k} - V^{\\pi_{f^k}}$, which relies on more complicated arguments. Hence our proof technique is novel compared with previous literatures.\n\n**Question 1: for the model-free setting, does there exist a general choice of $l$ function in Assumption 3.1? When Assumption 4.2 is satisfied, does $l$ function always exist?**\n\nFirstly, we note that the introduction of the abstract function $l$ in Assumption 3.1 is mainly due to the technical consideration of our paper, since we aim to cover all existing known theoretically tractable model-free MDP instances. E.g., MDPs of bilinear class [2], which itself is defined based upon the abstract function $l$ (Line 944). Indeed, for most of the time, the loss choice is natural in practice as the TD error $f_h(x_h,a_h) - r_h - f_{h+1}(x_{h+1})$. \n\nSecondly, the existence of such an $l$ should actually be regarded as a part of Assumption 4.2 (low GEC) for the model-free setting, since the discrepancy function $\\ell$ in Assumption 4.2 is chosen as $\\ell_f = (E_{x_{h+1}\\sim P_h(\\cdot|x_h,a_h)}[l_f(x_h,a_h,x_{h+1})])^2$ (see Eq. 5.1). In Section 5 and Appendix E, we clarify the choice of $l$ for the specific MDP instances we consider, which satisfies Assumption 3.1 and 4.2 simultaneously. This demonstrates the existance of the desired function $l$. Thanks for your question and we will make it clearer in the revision.\n\n\n[1] Jin, Chi, Qinghua Liu, and Sobhan Miryoosefi. \"Bellman eluder dimension: New rich classes of rl problems, and sample-efficient algorithms.\" Advances in neural information processing systems 34 (2021): 13406-13418.\n\n[2] Du, Simon, et al. \"Bilinear classes: A structural framework for provable generalization in rl.\" International Conference on Machine Learning. PMLR, 2021.\n"}]

Author rebuttal:
**General Response:**

Thank each reviewer for the review. We provide comments on some common questions here.

**Q1: Explanations on the Bellman completeness assumption (Assumption 3.1) and the choice of loss function (3.3), especially the second term, for the model-free case.**

**A1:** **About the Bellman completeness assumption (Assumption 3.1)**: This assumption does have a very clear technical and also intuitive interpretation. It is critical for us to get a sharper supervised estimation guarantee (Assumption 4.3) for the model-free case. In short, to estimate $(\mathbb{E}[(f_{h}(x_h,a_h) - r_h - f_{h+1}(x_{h+1}))])^2$, we cannot simply use the empirical squared TD error $(f_{h}(x_h,a_h) - r_h - f_{h+1}(x_{h+1}))^2$ because $E[X^2] = (E[X])^2 + \sigma^2$, where $\sigma^2$ is the conditional variance. The main technical consideration is that with Assumption 3.1, we can use the second term in Eqn. (3.3) to control the conditional variance $\sigma^2$. The intuition why we need the function class to be complete under $\mathcal{P}_h$ is that if the $\mathcal{P}_h f$ still falls into the function class, then we can relate the conditional variance with the infimum over the function class which appears in the second term of (3.3). Otherwise, the infimum term can help nothing if $\mathcal{P}_h f$ falls outside the function class.

**About the loss function (3.3)**: At a high level, involving the second term of (3.3) is only a specific estimator construction under the Bellman completeness assumption. It is indeed used to handle the double-sampling issue via the Bellman completeness assumption to achieve a sharper supervised guarantee, as discussed above. On the other hand, in the model-free case, another straightforward choice is to use the sample mean with $m$ trajectories as the estimator to achieve a low variance, at the cost of a worse estimation guarantee (see [1] for a similar algorithmic design). From this perspective, this term is not necessary.



**Q2: About the hyper-parameter $\eta$ in theory and experiments.**

**A2:** In our theory, we select $\eta$ to be $1/\sqrt{K}$. Our theoretical result would keep the same if we set $\eta = c /\sqrt{K}$ for any constant $c>0$. Such a choice of $\eta$ is vital to balance between exploaration and exploitation so as to achieve the overall $\widetilde{\mathcal{O}}(\sqrt{K})$-regret. 

In the experiments, we make some adaptations of $\eta$ to the experimental setups:

- Firstly, slightly different from the theory, in the experiments (Line 322 to 337), the empirical loss is an averaging over $(k,h)\in[K]\times[H]$ instead of a direct summation, and $\eta'$ is multiplied in front of the model value instead of the empirical loss. Thus equivalently $\eta' = 1/(\eta T)$, where $T=HK$ is the number of timesteps during training, and $\eta$ is used in the theory. This trick stabilizes the training process. Higher $\eta'$ means a higher weight on exploration, which is often used in sparse-reward settings.  
- Secondly, since in the experiments the reward is not normalized to $[0,1]$ as in theory, we need to scale $\eta'$ up to a constant to match the model value and the empirical loss (we often consider squared TD error). Hence it is natural to further use $\eta'= r_{\max}/(\eta T) = r_{\max}\sqrt{K}/T$. Here $r_{\max}$ is the maximum reward in the experiment which is around $10$, $T=1e6$, and $K=1e3$. This gives $\eta'\approx 3e-3$. After some trials around $3e-3$, we choose the $\eta'$ as specified in Appendix H.3. 

**Q3: Comparison with existing theoretical works.**

**A3:** We will add more explanation of the difference between MEX and previous theoretical approaches in the revision, which can better position our work. In the following, we make a brief comparison.

- Compared to the most of the version-space-based algorithms, e.g., [1, 2], our framework does not maintain a version space at each iteration and then conducts constraint optimization over the space. Therefore, our algorithm can be much more easier to be approximated in practice. We believe that such a practical computational guidance is meaningful if we want to bridge the theoretical work with the practical one;
- Compared to the posterior sampling algorithms presented in, e.g. GEC paper [3], our framework does not require the algorithms to know a good prior distribution. In practice, whether such a prior distribution required by the posterior sampling is available is not guaranteed in general.
- Compared to the E2D algorithm proposed by [4], our framework only uses an maximization oracle instead of a minimax optimization subroutine. Similarly, the E2D algorithm cannot be approximated efficiently in practice.

**References:**

[1] Du, Simon, et al. “Bilinear classes: A structural framework for provable generalization in rl.” International Conference on Machine Learning. PMLR, 2021.

[2] Jin, Chi, Qinghua Liu, and Sobhan Miryoosefi. “Bellman eluder dimension: New rich classes of rl problems, and sample-efficient algorithms.” Advances in neural information processing systems 34 (2021): 13406-13418.

[3] Zhong, Han, et al. “A posterior sampling framework for interactive decision making.” arXiv preprint arXiv:2211.01962 (2022).

[4] Foster, Dylan J., et al. "The statistical complexity of interactive decision making." arXiv preprint arXiv:2112.13487 (2021).


Meta-review: The reviewer consensus is that this paper should be accepted; it has both seemingly novel theory and fairly interesting experimental results. There is also consensus that the title of this paper should probably be changed to make its claims more precise as this is unlikely the only objective that is relevant or needed.
Decision: Accept (spotlight)