Exploration from a Primal-Dual Lens: Value-Incentivized Actor-Critic Methods for Sample-Efficient Online RL
Authors: Tong Yang
Bo Dai
Lin Xiao
Yuejie Chi
Venue: NeurIPS 2025 poster ()
Keywords: exploration-exploitation trade-off
actor-critic
RL theory
Primary area: theory

Abstract: Online reinforcement learning (RL) with complex function approximations such as transformers and deep neural networks plays a significant role in the modern practice of artificial intelligence. Despite its popularity and importance, balancing the fundamental trade-off between exploration and exploitation remains a long-standing challenge; in particular, we are still in lack of efficient and practical schemes that are backed by theoretical performance guarantees. Motivated by recent developments in exploration via optimistic regularization, this paper provides an interpretation of the principle of optimism through the lens of primal-dual optimization. From this fresh perspective, we set forth a new value-incentivized actor-critic (VAC) method, which optimizes a single easy-to-optimize objective integrating exploration and exploitation --- it promotes state-action and policy estimates that are both consistent with collected data transitions and result in higher value functions. Theoretically, the proposed VAC method has near-optimal regret guarantees under linear Markov decision processes (MDPs) in both finite-horizon and infinite-horizon settings, which can be extended to the general function approximation setting under appropriate assumptions.

Exploration from a Primal-Dual Lens: Value-Incentivized Actor-Critic Methods for Sample-Effiient Online RL
Tong Yang* CMU
Bo Dai
Lin Xiao Meta
Yuejie Chi Meta & Yale
Georgia Tech
Abstract
Online reinforcement learning (RL) with complex function approximations such as transformers and deep neural networks plays a significant role in the modern practice of artificial intelligence. Despite its popularity and importance, balancing the fundamental trade-off between exploration and exploitation remains a long- still in lack of efficient and practical
standing challenge; in particular, schemes that are backed by theoretical performance guarantees. Motivated by recent developments in exploration via optimistic regularization, this paper pro- vides an interpretation of the principle of optimism through the lens of primal-dual optimization. From this fresh perspective, we forth new pallu-inceeniviied actor-critic (VAC) method, which optimizes a single casy-to-optimin objective integrating exploration and exploitation - it promotes state-action and policy es- timates that are both consistent with collected data transitions and result in higher value functions. Theoretically, the proposed VAC method has near-optimal regret guarantees under linear Markov decision processes (MDPs) in both horie- and horizon settings, which can be extended the general function ap- proximation setting under appropriate assumptions.
Introduction
In online reinforcement learning (RL) [Sutton et all (198), an agent learns to update their policy in an adaptive manner while interacting with an unknown environment to maximize long-term cumu- lative rewards. In conjunction with complex function approximation such as large neural networks and foundation models to reduce dimensionality, online RL has achieved remarkable performance in wide variety of applications such game playing [Silver 2017,, control [Mmi et all, 201
language model post-training [OpenAl, 2023. and many others.
Team et all 2023 and reasoning [Guo et all 2025
Despite its popularity, advancing beyond current successes is severely bottlenecked by the cost and constraints associated with data collection. While simulators can subsidize data acquisition in cer- tain domains, many real-world applications- such as clinical trials, recommendation systems and autonomous
under conditions where gathering interaction data is expensive, time- consuming or potentially risky. In these high-stake scenarios, managing the fundamental yet delicate trade-off between exploration (gathering new information about the environment) and exploitation (leveraging existing knowledge to maximize rewards) requires paramount care. Naive exploration schemes, such as the e-greedy method, are known to be sample-inefficient they explore randomly
cww.. "Camnegie Mellon University; Emails: tongyanglandrew. cmu. cmu. edu. I Georgia Institute of Technology; Email: bodai@ec. www.eh..t.cch..ee.... edu. Fundamental Al Research, Meta; Email: linx@meta. com.
8 Yale University; Emails; yuej meweie.chiiieeeeeeeee www.cchi@ll....... edu.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

without strategic information gathering [Dann et all develop practical online RL algorithms that come with provable sample-efficiency guarantees. especially in the presence of function approximation.
20221. Arguably, it is still an open challenge
Addressing this limitation, significant research attempts have been made develop statistically effi- cient approaches, often guided by the principle of optimism in the face of uncertainty [Lattmoree and Szepesvári 2020]. Prominent approaches include constructing optimistic estimates with data-driven confidence sets [[Auer el all 2008, Agarwal et all 20233 Chen el all 2025, Foster el all 20211]. as well as employing Bayesian methods like Thompson sampling [Russo et 2018] and its optimistic variants [Agrawal and Jıa, 2012, Zhang, 2022]. While appealing theoretically, translating them into practical algorithms compatible with general function approximators often proves difficult. Many such pearetically-gronndde approaches either suffer from prohibitive computational complexity or exhibit underwhelming empirical performance when scaled to complex problems.
Recently, Liu [2024] introduced an intriguing framework termed Maximize to Explore (MEX) for online RL, which optimizes single objective function over the state-action value function (i.e., Q-function), elegantly unifying estimation, planning and exploration in one framework. In addition, MEX comes with appealing sub-linear regret guarantees under function approximation. However, the practical optimization of the MEX objective presents significant challenges due to its inherent bi-level structure. Specifically, it incorporates the optimal value function derived from the target Q- Q-function as a regularizer [Kumar and Becker, [1922], which is not directly amenable to first-orde optimization toolkits. As a result, nontrivial modifications are introduced in the said implementation of MEX, making it challenging to ablate the benefit of the MEX framework. This practical hurdle raises crucial question:
Can we design a objective function, but without resorting to complex bilevel optimization?
model-free online RL algorithm that optimizes a uniffyin
1.1 Our contribution
In this paper, we answer this question the affirmative, introducing a novel actor-critic method that achieves near-optimal regret guarantees by optimizing single non-bilevel objective. Our contribu- tions are summarized as follows.
Incentivizing exploration from the primal-dual perspective. We start by offering a new interpre- tation of MEX, where optimistic regularization- central to MEX arises naturally from La- grangian formulation within primal-dual optimization perspective [Dai et all, 2018, Nachum and Dai 2020). Specifically, we demonstrate that the seemingly complex MEX objective function can be derived as the regularized Lagrangian of canonical value maximization problem, subject to the constraint that the Q-function satisfies the Bellman optimality equation. This viewpoint allows deeper understanding of the structure of the MEX objective and its exploration mechanism.
VAC: Value-incentivized actor-critic method. Motivated by this Lagrangian interpretation, we de- velop the value-inceen incentivized actor-critic (VAC) method for online RL, which jointly optimizes the Q-function and the policy under function approximation over single objective function. Different from MEX, VAC optimizes a regularized Lagrangian constructed with respect to the Bellman con- sistency equation as the constraint, naturally accommodating the interplay between the Q-function and the policy. This formulation preserves the crux of optimistic regularization, while allowing differentiable optimization of the Q-function and the policy simultancously under general function approximation.
Theoretical guaraniees of VAC. We substantiate the efficacy of VAC with rigorous theoretical anal- ysis, by proving it achieves rate of (dHH2 regret under the setting of episodic linear Markov decision processes (MDPs) [Tin ei all 2020], where d is the feature dimension, H is the horizon length, and T is the number of episodes. We further extend the analysis to the infinite-horizon discounted setting and the general function approximation setting under similar assumptions of prior art all 2024]
In summary, our work bridges the gap between theoretically efficient exploration principles and practical applicability in challenging online RL settings with function approximation.

---

1.2 Related work
We discuss a few lines of research that are closely related to our setting, focusing on those with theoretical guarantees under function approximation.
Regret bounds for online RL under function approximation. Balancing the exploration exploitation trade-off is of fundamental importance in the design of online RL algorithms. Most existing methods with provable guarantees rely on the construction of confidence sets and perform constrained optimization within the confident sets, including model-based [Wang et al, 2025, Foss
Ter et all 20235 Chen et all 2025), value-basee [Agarwal et al. 2022 Im et 2021 X1e et all
2023,, policy optimization [Lw at [023]. and actor-critic [Tan et all 2025 approaches. to name a few. Regret guarantees for approaches based on posterior sampling [Osband and Van Roy, 2017 provided in [Zhong et all 2022, Li aLand
2022 Agarwal and Zhang 2022] under function approximation. Regret analysis under the linear MDP model et et all 20200 has also been actively established for various methods, c.g., for the episodic setting [Zanetie all 2021, Inn ala 2020.
Papın et all, 202IT] and for the infinite-horizon setting [Zhou el 2021, Moulin etal 2025)] How- ever, the confident sets computation and posterior estimation are usually intractable with general function approximator, making the algorithm difficult to be applied.
Exploration via optimistic estimation. Exploration via optimistic estimation has been actively studied recently due to its promise in practice, which has been examined over a wide range of settings such as bandits [Kumar and Becker, 1982, Liu et all, 2020, Hung all 202T] RL with human feedback [C [Cen ala 2024, Xie et all MIRE! Zhang et al, 20244] single-agent RL MMete 2021, Lm et all 2022,, Chen all M025], and Markov games FEster et aD, 20245. Xiong et al, 2024, Yang et all 2025J. Tailored to online RL, most of the optimistic estimation algorithms are model-based, with a few exceptions such as the model-free variant of MEX in ef al. 2020 but still with computationally challenges.
Primal-dual optimization in RL. Primal-dual formulation has been exploited in RL for handling the "double-sampling" issue [Dai ef all, 2017 2018| from optimization perspective. By con- necting through the linear programming view of MDP [De Farias and Van Roy, 2004, Putterman. 2014, Wang 2017 Nen et all 2017, Lakshminaaayanan
all, 20177 Bas-Serrano et all, 2021], systematic framework [Nachuu et all 2010 has been developed for offline RI, which induces concrete algorithms for off off-policy evaluation Nachum et all XIT Debara el aL 2020, Yang et all 2020] confidence interval evaluation [DDa al 2020], imitation learning [Kostrikoy et al. 2019.
Zhu all 2020, Maetal, 2022, Sikeh et all. 2025], and policy optimization [Nachum et all, 20196.
Lee et all [021]]] However, how to exploit the primal-dual formulation in online RL setting has not been investigated formally the best of our knowledge.
Paper organization and notation. The rest of this paper is organized as follows. We describe the background, and illuminate the connection between exploration and primal-dual optimization in Section Q We present the proposed VAC method, and state its regret guarantee in Section B. Section @ provide numerical experiments to corroborate the effectiveness of the proposed method. Finally, conclude in Section E The proofs and generalizations to the anfinitehhorizon and general function approximation settings are deferred to the appendix.
Notation. Let A (AA be the probability simplex over the set A, and [n] denote the set {1....,,) n... For any x E R,, we let ||>||p denote the l, norm of x, where p E [1, oo). The d-dimensional Ez ball of radius R is denoted by (B (Rt,, and the d x d identity matrix is denoted by la-
2 Background and Motivation
2.1 Background
H) be finite-horizon episodic MDP, where S and A denote the state space and the action space, respectively, H E N+ the horizon length, and P = {Ph heer and r {ra]ee(m the inhomogeneous transition kernel and the reward function: for each time step h [H], Pa S X A(S) specifies the probability
Episodic Markov decision processes.
3

---

distribution over the next state given the current state and action at step h. and S x A + [0 the reward function step h. We let x {Th helm x [H] + (A4) denote the policy of the agent, where (-(sss) E (AA) specifies an action selection rule at time step h.
For any given policy म, the value function at step h, denoted by VE :S + R. is given as
vs S, [M]
(T((s) = |
=
(I)
which measures the expected cumulative reward starting from state time step h until the end of the episode. The expectation taken over the randomness of the trajectory generated following
a, Ty (-1s)) and the MDP dynamics 8,+1 ~ P.(-[s;, 0z) for = h,... H. We define (s) == 0
for all s S. The value function at the beginming of the episode, when h = 1, is often denoted simply as (s) == (s). Given initial state distribution $1 p over S, we also define (p(p) = E (s)).
Similarly, the Q-function of policy a at step h, denoted by Q% : A - IR, is defined as
V(s,a) E S A
(7 = Σ i= (: a4) 9/z = as =
(2)
which measures the expected discounted cumulative reward starting from state and taking action at time step h, and following policy thereafter, according to the time-dependent transitions. We
define + (s, a) = and Q" (s, a) == Qi (s, a) for all (s,a) E S A. They satisfy the Bellman consistency equation, given by, for all (s,a) E A, h [H]:
0% (s, a) = (* + E Re (ale,,))) mi (-18h-1) Q (#h+1,a*+1) an+1)]-
It is known that there exists at least one optimal policy xt' ( i ..... Rt) that maximizes the value function (*) for all initial states E S [Pmtermmaz 2014). The corresponding optimal
value function and Q-function are denoted as V* and Q*, respectively. In particular, they satisfy the Bellman optimality equation, given by, for all (s,a) E S x A, h [H]:
(s, rn(s, a)
(Im. 1 a1+1)).
(4)
Goal: regret minimization in online RL. In this paper, are interested in the online RL setting, where the agent interacts with the episodic MDP sequentially for T episodes, where in the 1-th episode (1 1), the agent executes policy n, ( learned based on the data collected up to the (t - 1) episode. To evaluate the performance of the learned policy, our goal is to minimize the cumulative regret, defined as
Regret(T) = =f= -
(5)
which measures the sub-optimality gap between the values of the optimal policy and the learned policies over T episodes. In particular, we would like the regret to scale sub-linearly in T, so the sub-optimality gap is amortized over time.
2.2 Motivation: revisiting MEX from primal-dual lens
Recently, MEX [Li 2022 emerges promising framework for online RI, which balances exploration and exploitation in a single objective while naturally enabling function approximation.
Consider a function class Q I On of the Q-fuctioon. For any f { he(M Q. we denote the corresponding Q-function Q = {Q,.n [ with Q, = Jn- At the beginning of the 1-th episode, given the collection D,-1,k of transition tuples (8h, 4g 86+1) at step h up to the (t-1)- 1)- th episode, MEX [[iu all 2024 (more precisely, its model-free variant) updates the Q-function estimate as
St = arg sup Egpp max Q,.1(11, L(), fEQ
(6)
aEA
where a > is some regularization parameter, and Li(f) is
# Σ Σ
-(
(rn(sn, + max
- -Qra(shaan)))
aEA
1=1 LAED

---

inf 9h E
Σ (ra(sh, and max 1 a) gh (sh, an))²
ae
EAEDIIIA
where En = (sh, an S1+1) the transition tuple. The first term in (8) promotes exploration by searching for QQ Q-functions with higher values, while the second term ensures the Bellman consistency of the Q-function with the collected data transitions. The policy is then updated greedily from Q collect the next batch of data. While Liu all [2022]] offered strong regret guarantees of MEX, there is little insight provided into the design of (6), which is deeply connected to the reward-biased framework in Kumar and Becker [1982]].
Interpretation from primal-dual lens. We offer a new interpretation of MEX, where optimistic regularization arises naturally from regularized Lagrangian formulation of certain constrained value maximization problem within a primal-dual optimization perspective. As brief detour to build intuition, consider value maximization problem over the Q-function with the exact (i.e., population) Bellman optimality equation as the constraints:
sup
Esgrp max (811 fEQ
(8)
aEA
s.t. (8, (n(s, + (g max Qf, a))s v(s,a, E A [M] aeA
with the boundary condition Qr = When the optimal Q-function is realizable, i.e., Q' the unique solution of (8) recovers the true optimal Q-function Q*,
Q
How is this connected to the MEX objective? Introducing the dual variables (AEAe the regular- ized Lagrangian (8) can be written as
sup Beimp max (s)) SE
(9)
aEA
( max Qr, (r,(s, + 3 a))
inf (n.he(M) hm1 DD
E
where is the regularization parameter of the dual variable. and Dr, denotes a properly de- fined joint distribution over the transition tuples that covers the state-action space over (s, a). We invoke the trick Dai al [2018), Baird [1995], which deals with the double-sampling issue, and reparameterize the dual variable
An(s,a) Qra(s,0) (n(a,))
(10)
which satisfies
(b( Qp)(s,a)) + 3 as)
(s)
= 29
(5h(s,a) - ()) - (6n(s,a) gh (s, a))
(11)
Consequently, by setting 8n (x, a) as) + max.eA Qf (s',a) in (.. the Lagrangian objective (H) becomes
11
sup F. Faro max (s) scl
Σ
sup R 23 h=1
sn Eun (= (ra(s, max Qna+i((' Qn)(s,))) aEA
aEA
(r, + max Q5, gn(s, a))² AE
(12)
By replacing the population distribution Dr with its samples in D.-1.6 at each round, then we recover the model-free MEX algorithm in (7))
However, (6) is a bilevel optimization problem where in the lower level, another optimization prob- lem max.EA A Q (s, a) needs to be computed in (Z)). This can be can be computationally intensive not intractable, this paper, inspired from this primal-dual view, we derive a more implementable algorithm.
'It is possible use an (s, a, dedeendedtt regularization too.
5

---

3 Value-incentivized Actor-Critic Method
3.1 Algorithm development
We now develop the proposed calee-incetivvized actor-critic method. In contrast to the model-free MEX for (II), consider value maximization problem over both the Q-function and the policy with the exact (i.e., population) Bellman consistency equation as the constraints:
sup
E Expr,, (-1or) (rr [s1,())
(13)
SEQ, TEP
S.L. Qsn(5,a) (8, + (1b.e) (Q,h+t(6',,'') c'-ag-1010)
A
[I],
where I Ph. is the policy class. This formulation explicits the joint optimization over the Q-function (critic) and the policy (actor), and uses the Bellman's consistency equation as the constraint, rather than the Bellman's optimality equation, which is key obtain more tractable optimization problem.
Similar as H., Beine, (91.
write the regularized Lagrangian of (T3
sup SEQ, TEP
(14)
H Σ
- -2a(s,a)) + 3 a)(3
inf (A
h=1
Similar to earlier discussion, we also consider the reparameterization (IC)) which gives
H
sup JKEP
{V7(0)
Σ
1 sup
E DOND (1
(oo(s,a)==(,,t11413 (aaa(t,,))--((ssss0 -0)16))))) Q)n(s,a))
28 on Eu
(rn(s,a)+ + (Qaa))+++(+++sss gn -)) (15)
where we define
V7()) = B Ba (s,, and (7) [VF (s)]
(16)
Note that, the objective function (LS)) is casier to optimize over both Q and Replacing the population distribution D,, of (s, a, s') by its empirical samples leads to the proposed algorithm, which is termed value-incentivized actor-critic (VAC) method; see Algorithm MI for summary.
Algorithm 1
ActorcCritic (VAC) for 1: Input: regularization coefficient a > 0.
MDPs
2: Initialization: dataset Do, = for all h [H].
3: for ( T do
4: Update Q-function estimation and policy:
(ole))) (Ji, me) arg sup TEQ
(17)
5: Data collection: run ne to obtain a trajectory {st,1, 01,1, 81......, and update the dataset Dr, + DE-LA U ((St,,, 0t, (1,441) for all h E [H].
6: end for
In Algorithm M. 1-th iteration, given dataset D of transitions (sk, dhe 8141) collected from the previous iterations for all h E [H). and use the current policy गe to collect new action a' for each tuples, define the loss function as follows:
C.(fm) = Σ
Σ
Ba' (wa an) + (aa.a
a()) - Qy,
inf 9A ERh
Σ
E Eetorantiin /qaaaa/laaaaaaaaaaaaaoaaaa..... + Q14411(6411,d") - g. (sh, (s))
(18)

---

where En (sh, ab; SM+1) is the transition tuple. To approximately solve the optimization prob-
lem (L))), which is the sample version of (IS)), we can, in practice, employ first-order method, i.e.
Critic evaluation: Given the policy T fixed, we solve the saddle-point problem for ft as biased policy evaluation for Ny- i.e.,
fi arg max JEQ
V ((-1).
(19)
Given the critic f is fixed, we can update the policy и through policy gradient following the gradient calculation in Nachum al [[0019]].
Policy update:
Clearly, the proposed VAC recovers an actor-critic style algorithm, therefore, demonstrating the practical potential of the proposed algorithm. However, we emphasize the critic evaluation step different from the vanilla policy evaluation, where we have (p) bias the policy value. In contrast, MEX only admits actor-critic implementation for = 0 (corresponding to vanilla actor- critic when there is no exploration) since their data loss term requires the optimal value function, while the data loss term Le(J, T) is volicy-dependent in VAC.
3.2 Theoretical guarantees
The design of VAC is versatile and can be implemented with arbitrary function approximation. To corroborate its efficacy, however, we focus on understanding its theoretical performance in the linear MDP model, which popular in the literature [I et all 2020, et 202T].
Assumption (linear MDP, Uin et all [2020]). There exist unknown vectors Ça E I2d and unknown
(1) (signed) measures Ph = (1h : 11h over S such that
(d)
(n(8, a) (n(ss,)) Gt. and Pa(s'(s,a) an(s,)) (.ra))(((s))) (n())),,
(20)
where On : S A + Rd is a known feature map satisfying [1on(s, < 1, and max (1lGnl2, (S)]1) Vd, for all (s,a,s") E A x and all E [M].
We also need to specify the function class Q for the Q-function and the policy class P for the policy. Under the linear MDP, it suffices represent Q-function linearly w.r.t. Φh (s,a). i.e. Qn (s,a)
dn (s, a) On and the log-linear function approx for the policy derived from the max-entropy policy [Ren et all, 2022), with the following two regularization assumptions on the weights.
Assumption 2 (linear Q-function class). The function class Q I On is
vh E [M] On == sar (n To 10112 & (H - 1 h) Vd, || & &H+1-11 11.
Assumption (log-linear policy class). The policy class P = II Pk is exp (dn(s,a)
PA = Tu, mall(ass) EneA exp (ph (8, (8,aa')aa Tw) with ||||| < BHVd
Vh E [M]
with some constant B 0.
Under these assumptions, we first state the regret bound of Algorithm Min Theorem m
Theorem 1. Suppose Assumptions [HG hold. We let B Tlog
|AI dH
in Assumption and set
73/2 d
1/2
a
H (log (8) log 1
(21)
Then for any E (0, 1), with probubility at least 1 6, the regret of VAC (ef. Algorithm M) satisfies
Regret(T) = ( dHH2 (THPTTy /los log((LA))T
1+ d )
T3/2
log
(22)
Theorem 01 shows that by choosing B = Ō(T/aH) and a = Ō (VT) the regret of VAC is no larger than the order of Ō(dII up log-factors. Compared the minimax lower bound H3T) etle 2023), this suggests that our bound is near-optimal up to a factor of VH, but with practical implementation generalizable to arbitrary function approximator.
7

---

Extension to the infinite-horizon setting. Our algorithm and theory can be extended to the infinite-horizon discounted setting leveraging the sampling procedure in Yuan et all 12223 Algo- rithm 3]. We demonstrate that the sample complexity of VAC is larger than Ō
da (1-7) to
return an e-optimal policy, where is the discount factor. This rate is near-optimal up to polynomial factors of I-y and logarithmic factors. We leave the details to the appendix.
Extension to the general function approximation. Our theoretical analysis can also be extended to general function approximation, under standard assumptions for general function approximation such as low generalized Eluder coefficient (GEC) [Zhong et all, 2022, Liu et all 2024]. The cor- responding tight regret bound is provided in Appendix B 3. which matches the bound given in Lui
[2024] Corollary 5.2] under similar assumptions.
Extension to KL-regularized MDPs. Recently, MDPs regularized by the Kullback-Leibler (KL) divergence [[(T][/rer) with respect to a reference policy Tref = fe H] S x [M] + A(A),
has attracted much attention for preventing over-optimization and increasing stability of the learning process [Ouyang et all, 2022, Yang et all 2025]]. Our framework of VAC can be extended straight- forwardly, by invoking the soft Bellman consistency equation the derivation:
(T,((sa))= = rh a) + E A4aamP
[ 1P,441(5H+1, ah+1) - log t1 (as 1186+1)
Nat (ah-1 (6+11
(23)
where T > 0 is the regularization parameter. We omit the details for conciseness.
4 Experiments
We provide numerical experiments to demonstrate the efficacy of the value-incentivized regulariza- tion the actor-critic framework.
Setup. We evaluate on two challenging continuous-conter benchmarks in MuJoCo [odoroy et all 2012]: Ant-v4 and Walker2d-v4. For the base learner, we adopt Soft Actor-Critic (SAC) imple- mented in Stable- Baselless [Raffin et all [021] and add simple sample-based value- incentiicet term to its critic objective.
Critic update. With two critics (Qo, 13=1 and target networks (Q0; 13=1, the SAC target is
y = r(s + min 90; (8/, a') - Tem log <<a' ( a' ~ a'~x(.116)
Here, r(s, a) denotes the one one-step reward, and π denotes the current stochastic policy used by SAC for target evaluation (i.e., a' .(. 8')). Our modified critic objective uses minibatch sample averages (replacing population expectations) and reads
Eo(10,)) E(sa..EB Ei=1 (0, y)² 1 18 E.eB
Di NV EN 20, as)
Here we use single Monte Carlo sample 1
N "NN (s, to approximate (s)
Ba (Q, a)). We found that setting N = 1, i.e., using a single policy sample is good enough. We use minibatch B of size 256 sampled uniformly from replay buffer of size 105. The buffer stores the historical data: during the first 100 steps we act uniformly at random (warm-up). After warm-up. the current policy selects action at each step, and the resulting (s, a, r(s, a), s') is appended to the replay buffer. We optimize the critic with Adam (learnngg rate 3 x 10 10-4),, perform one gradient step, and update target networks every step via Polyak averaging with Tpolyak 0.005. Training starts after collecting 100 steps. The entropy coefficient is tuned automatically by optimiz- ing learnable log-temperature to match target entropy.
Policy update. The actor is updated with the standard SAC loss
(x(ww)
1
EanT.a()))) Tent log (a |s)
min Q0, (s. jE(1.2)
B
8

---

10-44
30--8
4033
000
92
(a) Ant-v4: best return over 3 seeds
(b) Ant-v4: average return seeds
Figure Ant-v4 with 1/a E {0, 20003. Shaded area indicates standard deviation across seeds.
2009
4002
3000
(a) Walker2d-v4: best return over 3 seeds
(b) Walker2d-v4: average return over 3 seeds
Figure 2: Walker2d-v4 with 1/a E {0, 1000). Shaded area indicates standard deviation across seeds.
estimated with one reparameterized sample per state using the Tanh Tanh- squashed Gaussian policy; we optimize the actor with Adam (learning rate 3 x 10-1) in lockstep with the critic. VAC modifies only the critic objective above, leaving the actor update identical SAC.
Network architecture. Both critics are separate MLPs with two hidden layers of 256 ReLU units each ("twin Q"), and the actor is MLP with the same hidden sizes producing Gaussian policy with Tanh-squashed actions.
Results. We run both experiments for 106 iterations over seeds. Figures M and A summarize performance. For each task, we plot the best return across the three seeds and the average return over seeds; shaded regions denote standard deviation. The VAC regularization improves sample efficiency compared to SAC.
5 Conclusion
In this paper, we develop provably sample-efficient actor-critic method, called value-incentivized actor-critic (VAC), for online RI. with a single easy-to-optimize objective function that avoids com- plex bilevel optimization in the presence of complex function approximation. We theoretically es- tablish VAC's efficacy by proving it achieves Õ O(-T))regret in both episodic and discounted settings. Our work suggests that unified Lagrangian-basee based objective offers promising direction for prin- cipled and practical online RL, allowing many venues for future developments. Further, we empiri- cally validate VAC's performance on MuJoCo tasks. Follow-up efforts will focus more empirical validation, and extending the algorithm design to multi-agent settings.
Acknowledgments and Disclosure of Funding
This work of Yang and Y. Chi is supported part by the grants NSF DMSS2134080, CCF- 2 2106778, and ONR 400014-19-1-2440 T. Yang is also graciously supported by the CMU Wei

---

Shen and Xuehong Zhang Presidential Fellowship. The work of B. Dai is supported in part by the grants NSF ECCC-2401391, IIS-2403240, and ONR N00014-25-1-2173.
References
Y. Abbasi- Abbasi-Yadkori, D. Pál, and C. Szepesvári. Improved algorithms for linear stochastic bandits. Advances in neural information processing systems, 24, 2011.
A. Agarwal and T. Zhang. Non-linear reinforcement learning in large action spaces: Structural conditions and sample-efficiency of posterior sampling. In Conference on Learning Theory, pages 2776-2814. PMLR, 2022.
A. Agarwal, Y. Jin, and Zhang. Vogl: Towards optimal regret in model-free RL with nonlinear function approximation. In The Thirty Sixth Annual Conference on Learning Theory, pages 987- 1063. PMLR, 2023.
S. Agrawal and R. Jia. Posterior sampling for reinforcement learning: worst-case regret bounds. arXiv preprini arXiv: aeee:-105004444 2017.
Auer, Jaksch, and Ortner. Near-optimal regret bounds for reinforcement learning. Advances in neural information processing systems, 21, 2008.
A. Ayoub, Z. Jia, C. Szepesvari, M. Wang, and L. Yang. Model-based reinforcement learning with tarue-targeted regression. In International Conference on Machine Learning, pages 463-474. PMLR, 2020.
Baird. Residual algorithms: Reinforcement learning with function approximation. Proceedings of the twelfth international conference on machine learning, pages 30-37, 1995.
J. Bas- Sar-anr S. Curi, A. Krause, and G. Neu. Logistic q-learning. In International conference on artificial intelligence and statistics, pages 3610-361 PMLR, 2021.
A. Beck. First-order methods in optimization. SIAM, 2017.
S. Cen, J. Mei, K. Goshvadi, H. Dai, T. Yang, S. Yang, D. Schuurmans, Y. Chi, and B. Dai. Value- incentivized preference optimization: unified approach to online and offline RLHE. arXiv preprint 2rXiv:2405.1995 19320, 2024.
Chen, S. Mei, and Y. Bai. Unified algorithms for RL with decision-estimatto coefficients: PAC. reward-free, preference-ber baaeed learning and beyond. The Annals of Statistics, 53(1):426-456, 2025.
B. Dai, N. He, Y. Pan, B. Boots, and L. Song. Learning from conditional distributions via dual embeddings. In Artificial Intelligence and Statistics, pages 1458 1467. PMLR, 2017.
B. Dai, A. Shaw, L. Li, L. Xiao, N. He, Z. Liu, Chen, and Song. SBEED: Convergent reinforce- ment learning with nonlinear function approximation. In International conference on machine learning, pages 113--134. PMLR, 2018.
B. Dai, O. Nachum, Y. Chow, Li, C. Szepesvári, and D. Schuurmans. Coindice: Off-policy confidence interval estimation. Advances in neural information processing systems, 33:9398- 9411, 2020.
C. Dann, Y. Mansour, M. Mohri, A. Sekhari, and K. Sridharan. Guarantees for ausilon-greeds reinforcement learning with function approximation. In International conference on machine learning, pages 4666-4689. PMLR, 2022.
D. P. De Farias and B. Van Roy. On constraint sampling in the linear programming approach to approximate dynamic programming. Mathematics of operations research, 29(3):462-478, 2004.
S. Du, S. Kakade, J. Lee, S. Lovett, G. Mahajan, W. Sun, and R. Wang. Bilinear classes: A structural framework for provable generalization in In International Conference on Machine Learning pages 2826-2833 PMLR, 2021.
10

---

B. L. Edelman, S. Goel, S. Kakade, and C. Zhang. Inductive biases and variable creation in self- attention mechanisms. In International Conference Machine Learning, pages 5793-5831. PMLR, 2022.
D. Foster, D. J. Foster, N. Golowich, and A. Rakhlin. On the complexity of multi-agent decision making: From learning games partial monitoring. In The Thirty Sixth Anmual Conference on Learning Theory, pages 27982279.. PMLR, 2023a.
J. Foster, S. M. Kakade, J. Qian, and A. Rakhlin. The statistical complexity of d'inerractvve decision making. arXiv preprint arXiv:2112. 13487, 2021.
D. Foster, N. Golowich, and Y. Han. Tight guarantees for interactive decision making with the decision-estimation coefficient. In The Thirty Sixth Annual Conference on Learning Theory, pages 3969-4043. PMLR, 2023b.
D. Guo, D. Yang, H. Zhang, J. Song. R. Zhang, R. Xu, Q. Zhu, S. Ma, P. Wang. X. Bi, al. Deepseek-R1: Incentivizing reasoning capability in LLMs via reinforcement learning. arXiv preprint arXiv:2501.12944 2025.
J. He, H. Zhao, D. Zhou, and Q. Gu. Nearly minimax optimal reinforcement learning for linear Markov decision processes. In International Conference on Machine Learning, pages 12790- 12822. PMLR, 2023.
Y.HH. Hung, P.-.. Hsich, X. Liu, and P. Kumar. Reward-biased maximum likelihood estimation for linear stochastic bandits. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pages 7874-7882, 2021.
C. Jin, Z. Yang. Z. Wang. and M. Jordan. Provably efficient reinforcement learning with linear function approximation. In Conference on learning theory, pages 2137-2143. PMLR, 2020.
C. Jin, Q. Liu, and Miryoosefi. Bellman Eluder dimension: New rich classes RL problems, and sample-efficient algorithms. Advances in neural information processing systems, 34:13406- 13418, 2021.
I. Kostrikov, O. Nachum, and J. Tompson. Imitation learning via off off-pooicy distribution matching. arXiv preprint arXiv: arXiv:/9/2.050:2 2019.
P. Kumar and A. Becker. A new family of optimal adaptive controllers for markov chains. 1EEE Transactions on Automatic Control, 27(1):137-146, 1982.
C. Lakshminarayanan, S. Bhatnagar, and C. Szepesvári. A linearly relaxed approximate linear pro- gram for markov decision processes. IEEE Transactions on Automatic control, 2017.
Lattimore and C. Szepesvári. Bandit algorithms. Cambridge University Press, 2020.
J. Lee, W. Jeon, B. Lee, J. Pineau, and K.-E. Kim. Optidice: Offline policy optimization via station- ary distribution correction estimation. In International Conference on Machine Learning, pages 4120-6130. PMLR, 2021.
Y. Li and Z. Luo. Prier-dependent analysis of posterior sampling reinforcement learning with func- tion approximation. International Conference on Artificial Intelligence and Statistics, pages 559-563 PMLR, 2024.
Q. Liu, G. Weisz, A. György, C. Jin, and C. Szepesvári. Optimistic natural policy gradient: simple efficient policy optimization framework for online RL. Advances in Neural Information Processing Systems, 36:3560-333 3577, 2023.
X. Liu, P.-. Hsich, Y. H. Hung. A. Bhattacharya, and P. Kumar. Exploration through reward biasing: Reward-biased maximum likelihood estimation for stochastic multi-armed bandits. In International Conference Machine Learning, pages 6248-6258. PMLR, 2020.
Z. Liu, M. Lu, W. Xiong, H. Zhong, H. Hu, S. Zhang, S. Zheng, Z. Yang, and Z. Wang. Maximize to explore: One objective function fusing estimation, planning, and exploration. Advances Neural Information Processing Systems, 36, 2024.

---

R. Lu, G. Huang, and S. S. Du. On the power of multitask representation learning in linear mdp. arXiv preprint arXiv:2106.0805: 2021.
Y. Ma, A. Shen, D. Jayaraman, and O. Bastani. Versatile offline imitation from observations and examples via regularized state-occupancy matching. In International Conference Machine Learning, pages 14639-14663. PMLR, 2022.
A. Mete, R. Singh, X. Liu, and P. Kumar. Reward biased maximum likelihood estimation for rein- forcement learning. In Learning for Dynamics and Control, pages 815-827. PMLR, 2021.
V. Mnih, K. Kavukcuoglu, D. Silver, A. A. Rusu, J. Veness, M. G. Bellemare, A. Graves, M. Ried- miller, A. K. Fidjeland, and G. Ostrovski. Human-level control through deep reinforcement learn- ing. Nature, 518(7540):529-333 533, 2015.
A. Moulin, G. Neu, and L. Viano. Optimistically optimistic exploration for provably efficient infinite- horizon reinforcement and imitation learning. arXiv preprint arXiv:2502. 13900, 2025.
O. Nachum and B. Dai. Reinforcement learning via fenchel-rockafellar duality. arXiv preprint arXiv:2001.01 866, 2020.
O. Nachum, Y. Chow, B. Dai, and L.. Li. Dualdice: Behavior-agnostic estimation of discounted stationary distribution corrections. Advances in neural information processing systems, 32, 2019a.
O. Nachum, B. Dai, I. Kostrikov, Y. Chow, L. Li, and D. Schuurmans. Algaedice: Policy gradient from arbitrary experience. arXiv preprint DTt.:v:9112000777 2019b.
G. Neu, Jonsson, and V. Gómez. A unified view of gutropy-regularized markov decision pro- cesses, arXiv preprint arXiv:1705.077 2017.
OpenAl. Gpt-4 technical report. arXiv preprint arXiv: 2023.
I. Oshand and B. Van Roy. Why is posterior sampling better than optimism for reinforcement learning? In International conference on machine learning, pages 2701-2710. PMLR, 2017.
L. Ouyang, J. Wu, X. Jiang, D. Almeida, C. Wainwright, Mishkin, C. Zhang. S. Agarwal, K. Slama, A. Ray, et al. Training language models to follow instructions with human feedback. Advances in neural information processing systems, 35:27730-27744 2022.
M. Papini, A. Tirinzoni, A. Pacchiano, M. Restelli, A. Lazaric, and M. Pirotta. Reinforcement learn- ing in linear MDPs: Constant regret and representation selection. Advances in Neural Information Processing Systems, $4:163311166 2021.
M. L. Puterman. Markov decision processes: discrete stochastic dynamic programmin. John Wiley & Sons, 2014.
A. Raffin, A. Hill, A. Gleave, A. Kanervisto, M. Ernestus, and N. Dormann. Stable- baselines3: Reliable reinforcement learning implementations. GitHub repository, 2021. URL wtt.s//o//ooet///aaaaeeeeeeeeeee
T. Ren, T. Zhang, I.. Lee, J. E. Gonzalez, D. Schuurmans, and B. Dai. Spectral decomposition representation for reinforcement learning. arXiv preprint arXiv:2208.09. 095.5, 15, 2022.
D. J. Russo, B. Van Roy, A. Kazerouni, I. Osband, Z. Wen, et al. A tutorial on thompson sampling. Foundations and Trends@ in Machine Learning, 11(1):1-96 2018.
H. Sikchi, Q Zheng, A. Zhang, and S. Nickum. Dual rl: Unification and new methods for reinforce- ment and imitation learning. arXiv preprint 230ivv2302.08566 2023.
D. Silver, J. Schrittwieser, K. Simonyan, I. Antonoglou, A. Huang, A. Guez, T. Hubert, L. Baker, M. Lai, A. Bolton, et al. Mastering the game of Go without human knowledge. Nature, 550 (7676):3543355) 2017.
W. Sun, N. Jiang, A. Krishnamurthy, A. Agarwal, and J. Langford. Model-based RL in contextual decision processes: PAC bounds and exponential improvements over model-free approaches. In Conference on learning theory, pages 2898-2933, PMLR, 2019.
12

---

R. S. Sutton, A. G. Barto, et al. Reinforcement learning: An introduction, volume 1. MIT press Cambridge, 1998.
K. Tan, W. Fan, and Y. Wei. Actor-critics can achieve optimal sample efficiency. arXiv preprint 2XXv:22005.03700, 2025.
G. Team, Anil, S. Borgeaud, J.-B. Alayrac, J. Yu, Soricut, J. Schalkwyk, A. M. Dai, A. Hauth, K. Millican, et al. Gemini: a family of highly capable multimodal models. arXiv preprint
wrXiv:2312.11805, 2023.
E. Todorov, T. Erez, and Y. Tassa. MuloCo: A physies engine for model-based control. 2012 JEEE/RSJ International Conference on Intelligent Robots and Systems, pages 5026-5033, 2012.
M. Uehara, J. Huang, and N. Jiang- Minimax weight and q-function learning for off-policy evalua- tion. In International Conference on Machine Learning, pages 9659-9668. PMLR, 2020.
M. Wang. Primal-dual π learning: Sample complexity and sublinear run time for ergodic markov decision problems. arXiv preprint 171.v:1710006100, 2017.
Z. Wang, D. Zhou, J. C. Lui, and W. Sun. Model-based RL as a minimalist approach to horizon- and second-order bounds. In The Thirteenth International Conference on Learning Representa- tions, 2025.
T. Xie, J. J. Foster, Y. Bai, N. Jiang, and S. M. Kakade. The role of coverage in online reinforcement learning. In The Eleventh International Conference on Learning Representations, 2023.
T. Xie, J. Foster, A. Krishnamurthy, C. Rosset, A. Awadallah, and A. Rakhlin. Exploratory pref- erence optimization: Harnessing implicit Q"-approximation for sample-efficient RLHF. arXiv preprint arXiv:2405.21046. 2024.
N. Xiong, Z. Liu, Z. Wang, and Z. Yang. Sample-efficient multi-agent RL: An optimization perspec- tive. In The Twelfth International Conference Learning Representations, 2024.
L. Yang and M. Wang. Sample-optimal parametric Q-learning using linearly additive features. In International Conference on Machine Learning, pages 6995-7004, 2019.
M. Yang, O. Nachum, B. Dai, L. Li, and D. Schuurmans. Off Off-policy evaluation via the regularized lagrangian. Advances in Neural Information Processing Systems, 13:6551-6561, 2020.
T. Yang, S. Cen, Y. Wei, Y. Chen, and Y. Chi. Federated natural policy gradient and actor critic methods for multi-task reinforcement learning. In The Thirty-eighth Annual Conference on Neural Information Processing Systems, 2024.
T. Yang, B. Dai, L. Xiao, and Y. Chi. Incentivize without bonus: Provably efficient model-based online multi-agent RL for markov games. arXiv preprint MXXi:22002.09880 2025.
R. Yuan, S. S. Du, R. M. Gower, A. Lazaric, and L. Xiao. Linear convergence of natural policy gra- dient methods with log-linear policies. In International Conference Learning Representations, 2023.
A. Zanette, D. Brandfonbrener, E. Brunskill, M. Pirotta, and A. Lazaric. Frequentist regret bounds for randomized seastesquares value iteration. In International Conference on Artificial Intelligence and Statistics, pages 1954-1964 PMLR, 2020.
S. Zhang, D. Yu, H. Sharma, H. Zhong, Z. Liu, Z. Yang, S. Wang. H. Hassan, and Z. Wang. Self- exploring language models: Active preference elicitation for online alignment. arXiv preprint arXiv:2405. 19332, 2024.
Zhang. Feel-good Thompson sampling for contextual bandits and reinforcement learning. SIAM Journal on Mathematics of Data Science, 4(2):834 857, 2022.
H. Zhong, W. Xiong, S. Zheng, L. Wang, Z. Wang. Z. Yang, and T. Zhang. GEC: A uni- fied framework for interactive decision making MDP, POMDP, and beyond. arXiv preprint arX1v:2211.0196,, 2022.
13

---

D. Zhou, J. He. and Q. Gu. Provably efficient reinforcement learning for discounted MDPs with feature mapping. International Conference on Machine Learning, pages 12793-12802. PMLR, 2021.
Z. Zhu, K. Lin, B. Dai, and J. Zhou. Off-policy imitation learning from observations. Advances in neural information processing systems, 1112202--12113 2020.
NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: The claims made in the abstract and introduction accurately reflect the paper's contributions and scope.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the con- tributions made in the paper and important assumptions and limitations. A No NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification:
We discuss the limitations of the work.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to vi- olations of these assumptions (c.g.. independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect the scope of the claims made, c.g., if the approach only tested on a few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low or images are taken low lighting. Or a speech-to-tex system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency the proposed algorithms and how they scale with dataset size.
If applicale,, the authors should discuss possible limitations of their approach address problems of privacy and faimeess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might that reviewers discover limitations that aren't 'tt't acknowledged in the paper. The authors should use their best
14

---

judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification:
We provide the full set of assumptions and a complete (and correct) proof.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main experimental results of the paper to the extent that it affects the main claims and/or conclu- sions of the paper (regardless of whether the code and data provided not)?
Answer: [Yes]
Justification: We provide the full set of information needed to reproduce the main experi- mental results.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, No answer this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided not.
If the contribution is a dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending the contribution, reproducibility For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how replicate the results, access hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate the research performed.
be accomplished in various ways.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) If the contribution is primarily a model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution a new model (e-g., a large language model), then there should either be a way to access this model for reproducing the results or way reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
15

---

(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path to reproducing verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [No]
Justification: We do not provide open access to the data and code since the experiments are simple and are not central the contribution.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please
the NeurIPS code and data submission guidelines (https://nips.cc/pp www.lliccuuddessSoeeuuuiiiiiiiie
for more details.
While encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (nttps://nips.ccppublcccc/
for more details.
The authors should provide instructions data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new pro- posed method and baselines. If only a subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized ver- sions (if applicable).
Providing as much information possible in supplemental material (appended to the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification:
We provide all the details necessary understand the results.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper level of detail that necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined other appropri- ate information about the statistical significance of the experiments?
Answer: [Yes]
Justification:
We run experiments over seeds and report the standard deviation of the
returns.
Guidelines:
16

---

The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by enror bars, confidence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should clear whether the error bar the standard deviation or the standard error of the mean.
It is OK report 1-sigma enror bars, but one should state it. The authors should prefer- ably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is verified.
For asymmetric distributions, the authors should be careful not to show in tables or fig- ures symmetric error bars that would yield results that are out of range (e.g. negative error rates).
If error bars are reported tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory. time of execution) needed reproduce the experiments?
Question:
Answer: [NA]
Justification:
The experiments are simple and can be run on a single CPU.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't 't make it into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics http:///uuuuppc.ooooooooo/ccciie
Answer: [Yes]
Justification:
We conform to the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurlPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (c.g., if there is a special considera- tion due to laws regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: This is foundational research paper and does not have any socictal impact.
17

---

Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA No, they should explain why their work has societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (c.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g.. deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path any negative applications, the authors should point it out. For example, it is legitimate to point out that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release models, providing defenses in addition to attacks, mecha- nisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of MI...
11. Safeguards
Does the paper deseribe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (c.g.. pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
This is foundational research paper and does not have any societal impact.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions access the model implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification:
We properly credit and mention the license and terms of use.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (e.g.. CC-BY 4.0) should be included for each asset.
18

---

For scraped data from particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package
should be provided. For popular datasets, seperswithoode.comddteeess has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information not available online, the authors are encouraged to reach out the asset's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documenta- tion provided alongside the assets?
Answer: [NA]
Justification:
We do not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limi- tations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the pa- per include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification:
We have no crowdsourcing research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contri- bution of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collec- tor.
15. Institutional review board (IRB) approvals equivalent for research with human subjects
Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Question:
Answer: [NA]
Justification:
We have no crowdsoureing or research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
19

---

Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, originality of the research, declaration is not required.
Question:
Answer: [NA]
Justification:
We do not use LLMS the core methods.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, or non-standard components.
Please refer to our LLM policy https///burrraccccoooomeeeeeeees for what should should not described.
20

---

A Technical Lemmas
We provide some technical lemmas that will be used in our proofs.
Lemma 2 (Freedman's inequality, Lemma D.2 in Liu et all [20024]). ) Let (X (Xe)err be a real-valued martingale difference sequence adapted to filtatiinn {Ft).sT (X(x R almost surely, then for any (0, 1/ R) it holds that with probability at least 1 - 6,
T Ex
T " E|X log(1/0)
Lemma (Covering number of Eg ball, Lemma D.5 in enn [M00 For any E > 0 and d N.. the e-covering number of the &2 ball of radius R in R& is bounded by (1 + 2R/e)².
[20TI]). Let (ee) be sequence of vectors with Is E V for some Hilbert space V. Let Ao be a positive definite matrix and define At = Ao + >s=1 2, Then it holds that
Lemma 4 (Lemma in Abbasi-Yadkorr
Σ min {1, ( IL.ll,l } & 2 2og
(de((Ar) det(Ap)
Lemma 5 (Lemma F3 in Du et all [2021]]). Let X C Rd and suPsex ||||| & Bx. Then for any N4, we have
AY O:
max Jw EX
log det
1 Ia
+
Σ 2
< d'log
1+
nB
X 1=1
dd
Lemma 6 (Corollary A.7 Edelman all [2022]). Define the softmax function as softmax(.)
Rd + A by softmax(z); Ejsı exp(x,) for all i [d] and x E IRd, Then for any y E R we
exp(2:)
have
|softmax(2) softmax())ll: 2|| ylloo.
B Proofs for Episodic MDPs
B.1 Proof of Theorem II
Notation and preparation. For notation simplicity, we let f* Q be the optimal Q-function.
We let II == A (A) denote the whole policy space. We have Ph. C II for all h E [H). We also define the transition tuples
{ = (8, a, 8') ESX and &b = (8hy ahe 81+1) S AxS.
(24)
Given any policy profile π [an]NE( and f = (fn : AASSAAAAO A we define P. as
V(sh, an) ES A: Pī]((n -Th(s an) E * (w)) (8h41)
(25)
and let p= (PTShe Let
Ω= {w: 1|wl2 & BHVd
O == (0: So.n E 2n),
(26)
be the parameter space of Qn and Pr, respectively for all h E H). We also define
VJA (s) (a- (Q,,(s, a)] and VīA(p) Eaup [v], Vf Q.EP 8, [H].
(27)
We'll repeatedly use the following lemma, which guarantees that under Assumption the optimal
Q-function Q* is in Q, and pa Q for any Q and E T Similar results can be found in the literature, e.g., et all [2020]. For completeness, we include the proof of Lemma D in Appendix Bwl
21

---

Lemma (Linear MDP + Bellman completeness + realizability). Under Assumption W we have
(realizabilitt) Q* Q:
(Bellman completeness) Vπ and f P
We also the following lemma, which bounds the difference between the optimal value function V and m V - the optimal value over the policy class P, where we let
= arg max V (P),, wh E [H).
(28)
SaEPs
and π [ helm be the optimal policy within the policy class P. The proof of Lemma is
deferred to Appendix Be
Lemma 8 (model error with log-linear policies), Under Assumptions 1A we have
Vs E S, E [H]: 0 <& V%)) V (+) log |A|
(29)
B
where B is defined in Assumption
Main proof.
We first decompose the regret (cf. (55) as follows:
T Regret Σ (V* V2 v V.
VT. (p) - (V)( (30)
(i)
where recall we define V f.1 in (LG). We will bound the two terms separately.
Step I: bounding term (i). The linear MDP assumption guarantees that Q* Q by Lemma M
and by definition (28). A is P. Thus by our update rule (I we have
14 N (p) - aLi Vi (p) aLa(Ji, Tt).
which gives
VJ & <a(c(((; Lr(se. T.))
Invoking Lemma & have
('(p) - (7) & (C,(f (C((())))))) - C((fe + log IA
(31)
B
Thus to bound (i), it suffices to bound (, Lr Te) for each E [T]. introduce our lemmas, we define ln On S x A x I IR for all h E [H]
(n(.ss,,m))= = E V- (rn(s, a) fati fn(s,a)) a'
(32)
We give the following lemma that bounds (i), whose proof is given in Appendix B.2.3
Lemma 9. Suppose Assumptions DHG hold. For any E (0, 1), with probability at least 6, for any E [1], have
1- H1
f,(," m <
E
(eLa (
[Cn(Se, 8i,b, 0i,h, TT)]
im
A=1
BHdT
T log (A
+CH3 ddog
(33)
BH
for some absolute constant C > 0. Here, d is the stute-uction visitation distribution induced by policy at step h.
22

---

By (11) and Lemmal H. we have
t-1
BHdT
("()) - V7 &
[CA Ss,h as, CH&
(FLa a )rr
2
8
1=1 A=1
log AAl
(CH +1)
B
which gives
T 1-1
H
BHdT
① 0
(eLa,o [ea(fe. Si, (...m))) + CTH
+ +CCHfaT++ Tlog [A]
(34)
B
Step bounding term (ii). For any x > O, we define
1 -
T
d(A) = dlog
(35)
dA
We use the following lemma to bound (ii), whose proof in Appendix B.2.4.
Lemma 10. Under Assumption DI for any 1l > we have
1-1
H
Σ 7. (p) < Σ
E
St. me) +))++ + (6112 H/n)d(A)+ XdT.
By Lemma
we have
T t-1 H
iii <
B
(n sa a, m.) + (6H² H/n)d(A) + Hd.. (36)
Step combining (i) and (ii).
Substituting and (56) into (BO), and letting 7) 2 we have
BHAT
(CH +1) Tlog [A]
Regret(T) < dCT
B (6H2 + +2H/a)d(N) + Hd
(37)
Setting À = log(log (1 log (1 + _2z) 222²)) 1/2 bound, we have with probability at least
and B = Ting IAl dll
in the above
V
(log((AA)T
T3/2
Regret(T) & C'dH' VT
VT
log
log 1 +
for some absolute constant C" > 0. This completes the proof of Theorem [II.
B.2
Proof of key lemmas
B.2.1 Proof Lemma
Assumption guarantees that
(sh; an)
rn (sh, an) + BentirPaClennon (s++1))
or (s and Sn + Ps Pa(shtilsn Vit (1 1ds
[ Vit ((=
(h (h++ + Ss
(38)
23

---

where v E R² satisfies
11 = ||cA + [ Vh+ (
< 111 + + (S) &
(H h)vd= (H- Vd(H - +
We also have 10 +1+1= h for all h E [M]. Thus Q" Q.
Moreover, for any f 2, we have (18 (4) = rn (8h: an)
3 (Sh+1 an+1)] ant anti aepinenttiii Glent))
(sh: T + I Ph Ph an B
woa (l ( dsn+1
Sn (Ren- f (sn+ ab+1)) dun(5n+1)) = onn an)
where E IRd satisfies
||Gall2 = (/h / (Bossrrantttaaann//eee (++11:+++1+))))))+++000++)11)1)) dun dun (8
=
< 1|Sal12 + Ilfnti 1lall2 < Vd h)va = Vd(H - 1).
In addition, we have
|P & Ila < H - h+1, vh E
Thus IP f TEQ. Q.
B.2.2
Proof of Lemma H
From Lemma M it is known that for all h E [H], there exists VA E O such that
Qī(s.a) = (n un V(s,a) E A.
(39)
Let
(s) (x)
TA (als) = Ea'EA exp( (s,a(s,a') ug) V(s,a) ES
(40)
where B is defined in Assumption EL It follows that Th E Ph. and for all E S, (-(ss)) is the solution to the following optimization problem [Beck 2017 Example 3.71]:
max PEA(A)
(p,,)(s))) + B (D), where
H(p)
Σ Mog
(41)
aEA
Here, H(-) is the entropy function satisfying
0 & H(p) < log LAI.
Vp A(A).
(42)
The optimality of mn for (l),, together with 2 implies
log A
YsES: v +
(ma((ss)
B
1
(mi()18), (2 (2. a))
3 H (m
1
= VV((s) + 7 (+T(()) > (s),,,
(43)
B
which further indicates
log
max VTA (T (s( EP
(44)
B
The desired bound (AA) follows from the above inequality and the fact that (i)(s) =
max,5A Q* V for any policy profile n'. s S and h e [H].
24

---

B.2.3 Proof of Lemma! M
We bound the two terms Lz(f", R)) and -Le(fe, nT) on the left-hand side of (LX) separately,
Step 1: bounding (f,, Te). Given f. E Q, data tuple & = (s, a, s') and policy profile
(Tr)k=) 11 we define the random variable
vh E [H] lef. () rn(s,a)+ fn+1 fl,,,
(45)
where d' 1 (+1s). Then we have (recall we define Pa f in (25)
WnS, PP J,E, R) In+1(5',a') E (pac)))) al d'maa-1(ll)
[[at1(s',a')]
(46)
which indicates that for any f f E Q. and
f. 1 (...f.f....... T.E,T) = ((
Bolf.f'
(47)
d'
For any / E E v E II and E (7), we define /,,,, as
jj,nh == Ba [, Ee,,, x)² PF Ee,,, x)
(48)
where Ei, (8t,1, de 81,4+1) is the transition tuple collected at time t and step h. Then have for any f E Q:
B Mal. x)
E ( S. x)²
Σ
inf
E Ba C (1 (n Ei, T)² (,,
gEQ
(49)
where the inequality uses the fact that fTfE Q, which is guaranteed by Lemma Here, we define
(f, Ba [(a(ss,)) as.) + f1+I(S.N+1,a')) - fa ax,))
inf gE Q
Bar o.)41) (rn(sen, a..) + JAtI (141(11441, g(8,,, )
(50)
Therefore, to upper bound (f( = -E" Cr,((femm)). it suffices to bound -E=l xi J for all h E [H]. In what follows, we use Freedman's 's inequality (Lemma n and covering number argument similar to that in Yang et all [2025] to give the desired bound.
Step 1.1: building the covering argument. We start with some basic preparation on covering argument. For any X C Rdd let & be the e-covering number of X' with respect to the
norm ||-I1- Assumption A and Assumption B guarantee that (cf. (A) O
(Hvd) and Ω
(R) to denote the la ball of radius R in Rd. Thus by Bg (BHV)) for all h, where we use (B)
Lemma & we have
2H
log.N (Op, (1-112) < log.N (B [ (Hvd) e, (1--12) < dlog
1
(51a)
2BHVd
log,N(S,,, (1.112) = LogN(B)) (BHva) e, 11-112) < dlog
1+
(51b)
25

---

for any e > O. This suggests that for any e >> O, there exists an é-net bb. C b₁ and an e-net Ω2 C Ω
such that
2H 2Hvd vd
and log [2,1] < dloog 1+ 2BHvd
log Oh,el dlog
1
(52)
e
For any fn forn Qn with On On, there exists On,e Un such that |10, - 0n,ell2 & and let Sn,e == Son.. and define
Ore Whe On E On.c
Q.
II A=1
2n.
(53)
In addition, for any E Ph, there exists w/ Ω and whir Z2 such that ||wh whelle & such that
exp(ón a) wn) (w))
exp(in (aaa))wa whe))
(als))) = Eo'es exp(ox aT)
The(als) Ewed exp(@n(s,at) wh,e) V(s E exA
w')e)
We define
H
Ph.e = (The whee E El,),
P.
II h=1
Ph.e-
(54)
We claim that for any f E Q and πT P. there exists fc E Q. and Tee E Pe such that
[X x)m 24112
(55)
The proof of (655) deferred to end of this proof.
Step 1.2: bounding the mean and variance.
Assumption ensures X f.m. is bounded: EP |X),,,al < 4H².
(56)
We now bound E BeL. jx) Notice that
4. (f..f... (In(f.fEE, 1. f. In f.)
E (nep (A.(if.E 4, S.h,TT))
mn(f + 1. d'maRi1
2B
(loa)) (AC.
o' (
(57)
where the expectation of the last term satisfies
E (l
E Weeat a.a)
[n(fff.E
[4 1P" f.E,T)) olweh41(-1e
8F
0.
(58)
Combining 4& and (58), we have
(all,,a [X
(n de,h, TT)
(59)
Now we consider the martingale variance term. Define the filtration F. == (D:)) (the o-algebra generated by the dataset D, = U D. We have
vf Q [H] E
E
[X] [x)m,]] [Fe-1]
EAA
(e Iod
(Ca (J,,,,
8t,hs C2,b, (t,,,,,,,,,,,,
(60)
26

---

where we define d to be the state-action visitation distribution at step h and time t under policy profile π and initial state distribution p. i.e.,
df (p a) = E Pa (s) = =5,05, = als1).
(61)
Furthermore, we have
Var [X] f.r.h [F-1]
& E
[ s.m,h) |
En Ea (ra(sch) futz fu((st,e E
(J+t2(9,4+1, - -Brenntteer (h Un-1((', a'wentalle)
Fi-1
< E Pa(sL, + 2f - fn(Su, B. (faza(s, 2
2
(TuloLih anh) + E. B Breeachnnn [fu+ils', (s', - fh(sen,
Fi-1
< 16H 16HH (o (R, St,bs 01,h, m)],
E
(62)
where the first equality follows from (95) and (9f),, and the second inequality follows from Jenson's inequality.
Step 1.3: applying Freedman's inequality and finishing up. By Lemma P. and noticing that (,, 8, a, x) is only related to Shs fh+1 and Th+1, we have with probability at least 1 - 6, for all / E [T], l E [e E Q and n. E E...
(60) and (22).
(-
ass, Te)l
x
i=1
Mannanaaa Len (Ser 8i,h, ai Re)] + H2
BHd + log(T//)) (63)
di (al,e,8i,h Rc)] H
dlog
where C1 Cf > are absolute constants. From (33) we deduce that for all t E (T). fc e Q. and T, Pee we have with probability at least 1 - 8,
H
BHd
X Je &
E Eo [la
Sin 8i, ar (.)) + CHH (dlog
+ log(T/6)
(64)
Note that for any t E [T] and h E [H]. there exist 0r, E O₁ and Wan E Ω such that frr = for, E 2n and Te. Twin Pn. We choose Og,r, On,c and wa,se E Ω. such that 110cr Oct < é and | we,b,el22 < We let fiee = (f Jeem E Q. and Tee Twr.n. hee(m) E P... Then by (Z)) we have for all t E [T].
t-1 H
X Juxcc
x Khaweech + 24H3 ET
H
E Beels a Judz Whlfeersrhh ai, Tec)l + H (dlog (BHd)
log(T/6)) 2
e
27

---

1-1
H
BHd
CHHh$ mt)) + ((
(alfer 8i, (s,h,
dlog
log(((0)) + 3633 ET,
(65)
where the last line follows from (5.5) and (59).
Step 2: bounding L,( For any f E Q and & [T], we define
yj, Bad (lewn) PnlSS, ",ls",JEtta #5) Ia(s", Gn,,, #1) +1
where /= ppa s
(66)
Note that for any tuple & (s, a, 5'), have
Inlf 1
J #,
-M, 1. (,
< <AH (le If 201
(67)
where the last line follows from Furthermore, we have
E (lna) a'wihestie
E (- dma7t+1(1e))
[ra(s,a) + fitrls', [s)
() + (gr-Pa(-)),a))
V ( lh(s,a)
= Ey (1ssa)
V ( - ExrwPa(tssa) [Vi+z(s') (68)
where the last line follows from Bellman's optimality equation:
(x a) + Eg [s'] f) =0.
Note that by Lemma S. we have
Eew-Pa(-)saa)) [Vi+1(8)] log |Al
< (.
[ < (eewRa(Hen) [+tt1(/)]
B
(69)
Plugging the above inequality into (672) and (68) leads to
log |A]
|A (f*, S "". I,(d" F'
4H
(70)
B
The above bounds 7i and (50) imply that
1-1
Cr,
2 E # (f .f ff" &.
inf SE
By
(1
Eut #*)
[-1
4HT log [A]
sup
(-Y;.)) + B
(71)
SEQ 1=1
where we also use the definitions of Yj, (c.f. (66) and J (c.f. (66)). Thus to bound Le( **))
below we bound the sum Σ Yf,, for any f E Q [T] and h [H] by applying Freedman's
inequality and the covering argument. By similar argument earlier, have for any ʃ E Q there exists Se E Q. such that
Y - -Y & 4Hc,
(72)
whose proof is deferred the end. We next compute the key quantities required to apply Freedman's incquality.
28

---

Repeating similar derivation of (59), we have
[YA = (R danatilan)
(73)
which implies
: E B = R ((o (Banat Ma, -,,,,,,,))))))) )))])
(74)
We have
Var
[F
E
(Y7,h) [e-1
E
En Pal (ra(s)n) + fhtt (s,44,,))) ((,))
(fin1 E. Bage ((ins)) ){)) e
Fo-1
(1 )
<
E
ra(se,, (r,)) + 2/h+1 (80,011; Sa (n - E
a' (lasa)1)
2 [1 Salse,,, Sulordnneh))) achh) Fe-1 )
(ra(8e,,, at.h) + E ae Pa aaaiee) alway M (lee441)
( E
< 1 A bodd
[al Io S...n.
(75)
a' (14
where the first line uses (by (EM))
le(f", f (c,hi = fhit1 (1,, EE ( [fh+2(0uat1, d' (10001111)))
(76)
where a' T ( (+181,441) and the second inequality uses Jenson's inequality. Last but not least, it's easy verify that
|r) < 4H?.
(77)
Invoking Lemma and setting 1) as
log log((O)..l10 1 (TT
min
4H2*
Σ Var YjA Fi
we have with probability at least 1 5, for all fe E Qc,te (T), h E [H],
Yi + BeLa
E Se [n(f" fer [t]]
a'we a (18,.112
1-1 E (s
( E BBo Un(f feihh [t)]] (78)
27
< и (0e(0)nellO0+1.e)HHH)
( Sorngealleeee
+ I 1,
Reorganizing the above inequality, we have for any E Qc,te [T]:
Σ (-Y).,))
29

---

(
Pn(S SeesSenh )
I8 Eenger MaantimBhhii ma afwaid (16)))))
H² (o.((0), HT
27
B as H log((On.ell0htt. HT/0/
En Ceeaarnaa Wel Ses d'way 1 (112)1)
2 log( 0b.e|10==1,,|
(79)
where the last line makes use of the fact that -x² + bx & b?
Combining (79) and (72), we have with probability at least 6, for any E (T) and f E Q
H
H
(-Yj.,) + 2T2
C2113
Hdd (dlog
( + log((T/)) + RT,
(80)
where C2 >> 0 is an absolute constant. Plugging this into (FII, we have
Hd (Ee) + log(((6)) + 4H +
4 4H AHHTToog log IA
L(F",)) & C2113
(dlog
(81)
B
Step combining the two bounds.
Combining
(65) and we have for any t [2].
-
E Be [en (Jrs 8t,bs aiA, Te)l
BHd
Tlog (Al)
+ CH3
ddlog
1og +
(82)
BH
for some absolute constant C Letting c TT we obtain the desired result.
Proof of 55 and
By Assumption M we have
E
(s. -h..s. (s,n(s, 10, 0n.el12 Sc,
(83)
and thus for any f E Q and π E P, we have
X J.mTh Xt Kmmma
Ea (e,) f1+za(( f
(JotIc(((4411 E (1+ta(s',a')) )² d'manittion
(( (ra(se,,) + (n+2(0en41,a") (e,)))
(fnti(9eN41,d) -Ev-nateea [fntils (a41lss,aa)) a'maneilia")
Bownans)(eana (2ra (2rn, ann) + Sh+ (h+tLc(ELNt) -
+ fht (0+1( - -n (n(o,,
(J - (nt1(0na41,a")) - E Barngntinnnnnnn [suti d') (ntlee(',dd))) a'mopsilioo)
Earraaelleann) (fft1190. fn+I. E. [fntils', a') fntiee(s,a)) a'mantille")
(Joti(srAt1)aa) - E Basannna (ntils', a')) (44tIc9),441,aa) E (Esseatiaaaann (nttac a'mmpsst1l))
30

---

< 8Hc + 8Hc c
(84)
where in the last inequality we use (33) Similarly, by Lemma have
Ys E h E [ [| (+)((1 & max (s, a)lla || wheel2 < 2c. (85)
s,
Therefore, have
[X] Jorch
X1 f,,,,al
R Be (ra arhh) + fn+i(sent1,,')) ae(s))
(fft1(44nt1,a)) E Be [fn+z(s', , '1
nh (1 ((,h) fhtz (n+1( (u(se,h Eag (eeaaas))
E 4H² (11+,1(s11,)441))) Tht1,e (1s,xail
[[ht1 ,
8H2e,
(86)
where the first inequality follows from Hölder's inequality and the fact that
(ra(s,a) + Sntild' d') - ()()) (Int16 -E dappelan) domapaatib
Unni(s,a2))
< 4H2
for all as E S A, E Q and π T.P.
Combining R and ( have the desired bound in (55)):
X Je j.mA x
X x., + [ X/,x,al & 16HE SH2 24H
Similarly, we have ( follows by
Ih - Vj.- = Ea (18e)))
(ra(sen, and)) + fh+1((1 - Sem((un.
- aLN) + fi (s. - fn(sen.
Ea (H (2rn
+ 2ff -calsae)ee__ttttlleeeeeeaaaaaaa (.,) - fa fn(sena
(fh - o(,))
< 4He.
where the last inequality uses X
B.2.4 Proof of Lemma I0I
First note that for any policy profile E IT any E Q and h E [M], we have (note that Vr.++1
VJ (p) = E semping mo
(VfA(s)) - (Fnt((9nt1))
Σ (Qyu(sn, an) Vinni(0nti))
E Sieeeeg -a
(87)
and
Σ rh (s)
T (p)
(88)
31

---

The above two expressions (7 and (8
together give that
vo(e) V (p) E
Σ (Q (h(sh) an) (
" 7
H
E an (Qrn(on, - (r (sh,
(89)
(Jen
where we define
PA (s, = -BsaPh(-aa)) (T)+)(s')).
(90)
and
(, a, (), - r2(s,)) - PxVF
(91)
By Assumption for any f Q, there exists 0f E O such that (n(8, a) (0 on (s) Thus
we have
-().s.a,m))n(((. (s) 0f,n Of - Sn / (1'n2z
(92)
=Wi(ffa))
where Wa(f, 1) satisfies
Ef Q 11, [M] [[Wx(f,))ll & 2HHV
(93)
under Assumption MI We define
(T( Breaaaa [s)(
(94)
Then we have
Σ
((aa)aa7, ( (,, Σ (e(x))
(95)
h=1
For all E [T] and I E [H], we define
Aa = Ala + Σ xa (T)) T, AA > 0,
(96)
where la is the d x d identity matrix. Then by Lemma HL we have
11 < log det La + Σ _aattneea
min
(97)
Further, we could use Lemma to bound the last term in (,))), and obtain
11 E [T):
Σ min [Ian((T))l
< 2d(A),
(98)
1=1
where in the last line, we use the definition of d(A) (c.f. (55)) and the fact that
|| ( 1,
(99)
which is ensured by Assumption I
Observe that
T
T
(P) - VV
(T)( (aaTm. Wa m))
1=1
32

---

H
(an (Te), Wi T))) ( & }}
T
H
(T)(T)), Wa m {1len 1> } (100)
where 1(-} is the indicator function. To give the desired bound, we will bound (a) and (b) separately. Bounding (a). We have for any À >
T H
(a)
[Wa m.) m.)l [
<1}
H
I1,, (.) mi)llanaca min (IanTT)llA)
(101)
A=1
Note that [fe, mi) (x) can be bounded follows:
1/2
[ Tella & VA -
Σ (Ts), Wo (Ft, (f,,
(102)
where we use and the fact that va bb+be & Va + Vb for any a, > 0.
The above two bounds (ITOI) and (IT02) together give
T H
1/2
(a) <
2
Kon (T.). Wa (he, m2))
min | m ( ..13
T
1/2
T
1/2
4dH2
Σ
min ( [
1=1
A=1
1=1
1=1
(a-1)
THE
1/2
T
H
1/2
ΣΣΣ
min [Iea(t)))l
h=1
(a-ii)
(103)
where in the second inequality we use Cauchy-Schwarz inequality and the fact that
min (T))))))))) 113 < min [I 13.
Vt [T]
(104)
The first term (a-i) in (10)) could be bounded as follows:
1R
(a-i) 2H² / 2XdTd(A).
(105)
To bound (a-ii), note that for any n. 7' "I we have
2
(xn(x'), (ia ())
B(ea))aph ()) -
E (r.a) (f,,
(106)
33

---

where the inequality follows from Jenson's inequality, and recall (f 8, a, (T) is defined in (32).
Combining (TTG)) and (98), we could bound (a-ii) in (TUS) as follows:
T 1-1
1/2
(a-ii) <
(Hd()) ΣΣΣ
as Enffer S5, Og. Ti)
(107)
Plugging (1I))) and into (ICE), we have
1/2
(a) < 2H² 2xdTd(A) + (H
ΣΣΣ
)i Lo lilfti St, Te)
(108)
Bounding (b). By Assumption M and (2S) we have
VT E IT: Combining the above inequality with (98), we have
(Tx(T), (R().))) 2H.
(109)
(b) < d())
(110)
Combining (a) and (b). Plugging (1U8) and into (TUO), we have
Vi (p) - (V)
T T-1
1-1 H
1/2
< 2H 2xdT + (2d(2))
la st (.) + d(H)
(s pa
(111)
The first term in the right hand side of (III) could be bounded as
2H 2xdT H² (AdT + 2d(A)),
(112)
and the second term in the right hand side (ITI) could be bounded as
1-1 H
1/2
Hd(A)
1-1 H
2Hd(A) ΣΣΣ (s. (i) en (n st, (t,, st,
E
(s:as) laffe 8 ag me) pih
(113)
for any 17 where in both (112 and (1L3) the fact that Vab d for any a, 0.
Substituting ( and ([I)) into (IIl) and reorganizing the terms, we have
H
VT. (p) V= <
E (a wih
la 8,, 0, m.) + (6112 + H/n))d(A) + H² ATT.
(114)
This gives the desired result.
B.3 Extension to general function approximation
We now extend the analysis to finite-horizon MDPs with general function approximation. We first state assumptions in this section.
Assumption (Q-function class), The Q-function class Q A= On satisfies
(realizability) Q* Q.
(Bellman completeness) VT E P and f Q Q
(boundedness) Vfn. Qn. llf < --+1-h h.
34

---

Assumption 2 is standard condition in prior literature involving general function approxima- tion [Li et all 2024, Assumption 3.1]. [Jmn et all 2021, Assumption 2.1]. In particular, Assump- tion g holds under linear MDPs (c.f. Assumption II), as established inl Lemma Under Assumption ! we set the policy class P follows.
Assumption (Policy class). The policy class P II
1 Ph
exp (BQn a))
VQx e 2n)
vh E [ PA =
(s) En'es exp (s,
(115)
with some constant B O.
Moreover, drawing upon the work of Zhong et al. 2022 et [M224]] require the MDP to feature low generalized Eluder coefficient (GEC). This characteristic essential for ensuring that the minimization of in-sample prediction enror, based on historical data, also effectively limits sample prediction error.
Assumption 6 (Generalized Eluder coefficient, Assumption 4.2 in Liu et al (2224).. Given any
0, there exists d(()= E R,, such that for any sequence {fr)e= Q, { C P, we have
H
la (f 84, 8, me) + d(A) + Va(HHT ÄHT.
V. 4. (p)
inf ?uu
E (o..a)))d h=1
(116)
For each À denote the smallest a(A) R4 that makes (L hold dGEC
From Lemma we can see that under linear MDPs (c.f. Assumption W. Assumption B holds with dGEC(A) (X) $ Hd dif where d(.) is defined in (3S).. Morcover, demonstrated by Zhong et al [2022], RL problems characterized by a low Generalized Eluder Coefficient (GEC) constitute a significantly broad category, such linear MDPs [[ang and Wang 2019, lin all, [020), linear mixture MDPs [Ayoub et all 2020), MDPs of bilinear classes [Du et all 2021], MDPs with low witness rank elln 2019. and MDPs with low Bellman Eluder dimension [lin 2021]] Zhong et all [2022] for more detailed discussion.
We let (N 11-11s))) denote the e-covering number of On w.r.t. the loo norm, and assume the e-nets Qi.e are finite.
Assumption (Finite e-nets). M(e)) == max M(Qn, 11-11 < +00.
The following theorem gives the regret bound under the above more general assumptions.
Theorem (Regret under general function approximation). Suppose Assumptions HL B hold.
We let B = Tlogg [A| in Assumption E and set
1/2
H
dGEC
(117)
TH log
NCe/ByHT
T
Then for any E (0, 1), with probability least 1 8, the regret of Algorithm W satisfies
Regret(T) (T) = 13/25TT (1og
HT 8
+ log [
(N(T He
Tlog [Ai ))) dGEO V T
(118)
Under linear MDPs, (1I8) reduces to (22) given in Theorem Besides, this bound also matches (is slightly tighter than) the bound given in Corollary 5.2 of Liuctal 2024] under similar assumptions.
B.4 Proof of Theorem
In this proof, the same notations in the proof of Theorem M in Appendix t define
First,
arg max VJ (p). Yh [H]. EPP
(119)
and #' (h)ee Using the same argument as Lemma g we have the following lemma.
35

---

Lemma 12 (model enror with log linear policies), Under Assumption ! and DI
we have
log |A]
vs E S, h [ 0 0 (v
(120)
B
where B defined in Assumption
We bound the two terms in the regret decomposition (50) separately.
Bounding term (i). Following the same analysis as we have
((( + log (AA
(-()- & (C. Li(e,, (T))
(121)
B
It boils down to bound (x(J", Lr(Se, me) for each / [T]. Recall the definition of (J, 8, a.
in (32)), we give the following lemma, whose proof is deferred to Appendix B2N3
Lemma 13. Suppose Assumption M. S Ø hold. For any (0, 1), with probability at least for any t [T], we have
t-1 H 2
f((f - (e(fe.t)) <
B (es (r [en(fe Si, as,, Tel
1=1
+ +CH [log (N (c/B)) + 18) + Tlog [A]
(122)
BH
for some absolute constant C > O.
By (121 and Lemma B. we have
H
(N(e/B) HT
i1 E
B BOLLsaNDdd [Ra 8i, (... + CTH
5
[=1
T log |A|
+ +CH +
(123)
Bounding term (ii).
By Assumption R we have for any X> 0, 0.
d(A)
(ii) ΣΣΣ E (e (s m1)
v HT ÄHT.
(124)
Combining (i) and (ii).
Substituting (1233 and (144 into (M)) and letting 1/ = 2. we have
N (c/B) HT
T log LA|
2doEc + ddGEo (A))(())TTT) +
Regret(T) < aCTH log
+ (CH of + +1)
B
Setting
1/2
H 3 = T a=
dGEC
V
T log [A]
and
(125)
N(e/B)HT
TH3 log
the above bound, we have with probability at least 1 - 8,
Regret(T) 33 [log
HT 8
+ log (N
He
(A
))) dGEC
H V
T Tlog
T
for absolute constant C" > 0. This completes the proof of Theorem I
36

---

B.4.1 Proof of Lemma 1K
The proof is similar to the proof of Lemma 8 given in Appendix B.2.3. We use the same notations as in Appendix B.2.1. and also bound the two terms Li T²' and Ciffe me) in the left-hand side of (122)) separately.
Bounding
-f(fe Te). Same as in (98), here we also define
j,ah = Ba 1)
T)² L, F A. (e
(126)
then for any E Q:
Be' Ba (lla
Ea'n a H 14 f. (.
inf Ba - (1 Ma Le, (J,
(127)
where we use the fact that P 2 guaranteed by Assumption Therefore, to upper bound - [Le, me) = - E Ca, mt), it suffices to bound - Ei=l X; fomth for all E [H].
For all [H]. there exists an c-net Qr.e of Qn w.r.t. the &o norm such that
Qunel (e() +00,
(128)
where the last relation is due to Assumption g. Then for any f E Qh, there exists fn,e E Q1.e such that
|l fh,eloo &c.
(129)
and thus for any f E Q and E P, we have
X Se,thh
X %.m.
Ea (e, Shit (nsre((enntia'))) Sno())n)
(IntIc(8LA411 Bawnthaa Untils'aa')) d'massitio)
(olommnnaaamma (ra(se,,, and) + fntz( ac,)))
- -(fhtllsenti,dd - a'wani (1111)
- Exsennlann [fntils', a')]
Es Barnn and)) + Shott (o.01110)))) Ihalleeh, + Sh+ (8L,41,)) - (1(8),
(JoHI)()))A))))) - Sn+1 - E.reggeinnnn [n+ils', (d), Snti,ess, alvonsitian)
(e [ (Iataln/o(atttaaaaaaaaa (Jnt1(rr0-1,a')) (1tt,,((th-1110)))) Beogatha (nntils' ,a) (ntr,((', a'mensitio"
(Jnt d') E. E. at almttaati
(s Snttee(s,ht - Unntee (s',))
8HH 8H 16He, 16HH,
(130)
where in the last inequality we use (224) and the boundedness of fr, and fh+1 assumed in Assump- tion H.
In addition, there exists Qn.e/ of On w.r.t. the foo norm such that
Que/// & (N(cB)) < +00.
(131)
37

---

We define
exp (BQ((s))) a))
Ph.c = Th (T,
vQn E CneIBB
(132)
Ed'ed exp (BQN(s,)))
then we have
hh,el 1h,t/Bl &e(e/B),
(133)
and by Assumption E, for any Th E Ph, there exists Qn E Ch.efB such that
exp (BQn(s,a) a))
(s( a) En'e exp (BQ a'))
(134)
There also exists Qh,e/B E Qh,e/B such that
||Q: - Qne/Blloo < c/B.
(135)
We let
exp (BQQne/B(B,0)
(s, Enee exp (BQ (BQh.e/B(s,d"))
(136)
Then by Lemma f we have
| - Thelll < 2c.
(137)
In other words, we have shown that Ph.e is an 2e-net of Pa w.r.t. the l norm. Therefore, have
Jo X fmmnll = Ba [a (nassn art)) + Snti(seat1, - ft (((sL)
(J+ti(eLnt1,d') E [fh42(6', _a,s d'watillk")
Th (h (e,)) + Sut1 (s - Sh ax.1))
( - E Ea (6tt(6'aa'))
4 [| (11),,41)) (18,4(1)
SH
(138)
where the first inequality follows from Hölder's inequality and the fact that
(r)(s, + fnti(5', d') - fa(s,a))² - (fnti(st,
E (e d'woh41lles
<
4H²
for all (s, E S A. f Q and स P, which is ensured by Assumption H
Combining 33 and (T3)) we have
X F.re
X /o < X fertc Xt M. + J X/.m,al & 16He 8H 24H
(139)
On the other hand, Assumption @ ensures X f.n. is bounded:
E 2, P, E [M] [Xfmmvl < 4H²
(140)
Thus following the same argument as in Appendix B that leads to (b3). here we could obtain that for any 8 E (0, 1), with probability at least 1 6, for all t [T], E [H]. fo E e and n. E P. 1 Ph.c.
I1 On.
E Be (Ser Bi, di Re)]
Xi
Je
38

---

2 ( Si (0r.
Σ B (
di + H2 (log (N (c/ Hog(H (141)
2
where C₁ Cj > 0 are absolute constants.
From
(441) we deduce that for all E (T), Se E Q. and E Pe, we have with probability at least
1 6
H
t-1 H
Tes
Σ
Σ
E
(..
Sth m.)l + H2 (log (N (e/B)) +
+ogg(TH/)))
(142)
By (L.)). for any [T] and h E [H], we can choose fihhe. Qne and The E Pi,e such that
[l fe,b,elloo &,, || Te,belll & 2E.
(143)
Then by (142)
we have for all / E [T].
Lx(se.m) mt)
t- H
X
Me + 2T
[-1
1BC.
E ( (s [en (fa,fe ar,,, xe,e)l HHH (log (N (c/B)) + log(THH))) + 2
1-1
H
B (o
[a(fe, si,,, ai, my)) + 1 (log (N + 361
(144)
where the last line follows from (L3 and (5%).
Bounding Lef,, #*). Same as in (66), for any Q and t E [T), we define
f.h = E. ( (1ra) InIf S.,,,,,, 1nft, E.
(145)
where we define
p" ft
(146)
Then following the same argument that leads to (79), setting in Lemma D as
log( Qn.e 1++ HT/8)
= min
4H²
Σ Var (inlFFi1
we have with probability at least
5, for any fe Qe,t E [T]:
k
27 fer Ei,,, Ei,,,
E (es.n bi
E Baaariaee E (ee, f af a'witga (lo4441)
H² log( Qn.c
39

---

27
+ H Qu+1, HT/6) Σ (s.. as
Bar Balf Eaite ++) a'map (PaLa)))
I H² Log(W(()HT/))
(147)
where the last line makes use of the fact that -x² bx & 12/4.
Moreoever, for any E [T], [H]], we have
Ff, Vjn EB Bu (1 (ra(s)n)))))) fh+1((1,-1.. a(u))
(rn(suuh, fh+ 1 (S.,44,, fu(s4h)
Barnat (1aa))
(2rn(seh, and 2 fc,h(st,h (ateaa)))n((fneonon (1,
(fr(sL,; fen(su,h:
4Hc.
(148)
Combining
(447 and (148),
have with probability least 1 for any E [T] and f e Q
t-1 H
H (-Yie.) 4H2TT
Σ
C2HPlog(N())HH/8)) + +4H2ET,
(149)
where C2 0 an absolute constant.
By (74I we have
4H log [A]
C, & C2ll (o(())))))) + AHPET +
(150)
B
Combining the two bounds.
Combining (14 and 50
we have for any E [T],
((f+, - Li(f, x
E (oLh (e Si,hs Gi,h, mt)
2 i=1 h=1
T log (A]
+
CH3
log (N log ET
(151)
BH
for some absolute constant C > 0. Letting
4. we obtain the desired result.
C Value-incentivizeed Actor-Critic Method for Discounted MDPs
Infinite-horizon MDPs. Let = (S,A, be an infinite-horizon discounted MDP, where S and A denote the state space and the action space, respectively, E [0. 1) denotes the discount factor, : A + A(S) the transition kernel, and r A [0, is the reward function. A policy S + ((A) specifies of taking action a in state s for each (s,a) E S A. For any given policy n, the value function,
action selection rule, where π [a]s) specifies the probability
denoted by V S + R. is given
V VB(3==B
Σ r'r(s as)
(152)
which measures the expected discounted cumulative reward starting from an initial state where the randomness over the trajectory generated following a, ~ <(-(se) and the MDP dynamic
8141
P(-|st, az). Given initial state distribution So p over S, we also define V* v*(p) =
40

---

Bgup (s) with slight abuse of notation. Similarly, the Q-function of policy म, denoted by Q"
S A is defined
Exx: (=(s,a)= E
Σ g ae)lso 8,00
(153)
which measures the expected discounted cumulative reward with initial state So and initial action ag = a, with expectation taken over the randomness the trajectory. It is known that there exists at least one optimal policy x* that maximizes the value function (*(s) for all states E S Poterman, 2014), whose corresponding optimal value function and Q-function are denoted as V* and Q", respectively. We also define the state-action visitation distribution dz E A(S A) induced by policy x and initial state distribution p as
(s, = (1 Boo
A (sh = 8, also)
(154)
h=0
C.1
Algorithm development
Similar as
we start with an optimization problem:
max (1 -1 Be (e0-p.a-a(()s))) 1Q, (so. a)] fEQ,
(155)
s.t. Q, (s, (s,a) + ? (1 (st,d,) ((s,a)
Writing the regularized Lagrangian system of (1155) as
max (1 - (epr)pannn(( [Q, (so.a)) f,x
+ min / A(s;a) (r(s, a) + Ba (8', (8, + B(s,a) a)
A(s d
2
(156)
Similar to the finite-horizon case, we use the reparameterization (II) which gives
E P( (r(s,a)+ (s, (s)
max f
28(s, a)
(157)
min + v(s,
doda
which is easier to optimize over both Q, and The population primal-dual optimization problem (IS22) prompts us to design the proposed algorithm, by computing the sample version (IS7)) see Algorithm E, where we let
(s) = (o) [Q,(s, and (p) = E [V]
(158)
In Algorithm D at iteration t, given dataset D,-1 collected from the previous iterations, we define the loss function as follows:
Le(f.))
Σ
Ea (r(s,a) + (Qp('' (1((,5)) - (s)
(s,0,
inf
Σ
Earnttlo (r(s, + 1Q,(' g(s,
(159)
gEQ
(s.a,")ED,-.
We compute (166) in each iteration, which is the sample version of (152)). and use the current policy
T; to collect new data following the sampling procedure Algorithm G. which is also used in Yuaan
all [22 Algorithm 3]. Yang al. [2024] Algorithm 5], and Yang et all [2025, Algorithm 7].
Algorithm has an expected iteration number E[h + 1] = I and it guarantees P(sh. 4n
a) d (s, a) [Yuan all 2023 for any (s,a) S x A and any policy
41

---

Algorithm 2 Value-incentivized Actor-Critic (VAC) for infinite-horizz discounted MDPs.
1: Input: regularization coefficient >> 0.
2: Initialization: dataset Du ==
3: for = 1,..... T do
4: Update Q-function estimation and policy:
(fr, Tx) t arg max SE2,TE
(1-)) - aci(f,
(160)
5: Data collection: sample (st, 02, si) +- Sampler(Tee p). and update the dataset D, Di-1 {Se, de, s())-
6: end for
Algorithm 3 Sampler for (s, a) ~ dz and P(-]s,a)
1: Input: policy я, initial state distribution p. player index n.
2: Initialization: 8o p, ag TT-]su), time step h = 0, variable X Bernouli(yy).
3: while == do
4: Sample 84+1 P(-|sh, an)
5: Sample 01++1 ~ T( (-18)+1)
6: h h h h+
7: X Bernoull(7))
8: end while
9: Sample Sh+1 ~ P(|shh, an)
return (sh, ahh 5h+1).
C.2 Theoretical guarantees
Same as the finite-horizon setting, we assume the following d-dimensional linear MDP model. Assumption 8 (infinite-horizon linear MDP). There exists unknown vector I& and unknown (signed) measures = (1x12, ,H/dd) over S such that
r(8,a) a) a(s,a) and P(s'ls, a) - M(s (((s)) where & S x A + Rd is a known feature map satisfying (l0(s,0) 1, and max (oxc(1<1122 [[(())]2)} & Vd, for all (s,a,8') E Axx. S.
Similar as for the finite case, under Assumption &. we only need to set the Q-function class to be linear and the policy class P to be the set of log-linear policies. Assumption (linear Q-function class (infinite-horizon)), The function class Q is defined as
Q -= - fa = pl, |0012 < Vd
ll < 1-7
Assumption 10 Mog-linear policy class exp (p(s. (())
The policy class P is defined as
Byd P Tw : Tw (s) Evee exp (Ø(s (o(s,a')Ta Tw) with ||l|| & 1-7
with some constant 0.
We give the regret bound of Algorithm in Theorem A Theorem 14 (infinite-horizon). Suppose Assumptions 8- hold. We let B
Tlog [AIl1-)) in
d
Assumption M. and set
(1 7)
T3/2
1/2
a
log (log |A(T/8) log
(161)
d(1 - (11-))2
Then for any 8 E (0, 1), with probability least 1 5, the regret of Algorithm D satisfies
( dvT
log log(LA))?
T3/2
Regret(T) = O
( -
log
1+
d(1 - 7)
(162)
42

---

Note that
Regret(T)
min (V (p) V (p))
1E
T
thus Theorem
E
guarantees that the iteration complexity to reach e-aceuracy w.r.t. value sub-
optimality for any e 0 O
de and the total sample complexity is ① d² (1-1)
(1-7)²²"
C.3 Proof of Theorem
Notation. For notation simplicity, we let I* == Q* be the optimal Q-function. We Ie A(A) denote the of all policies. We also define transition tuples
(s, (s,0,8) 8') E Axx and & = (5t, úr Ax8
(163)
Given any policy и and f: S x A- R. we define Pr as
(ss,a) PT f() = r(s, a) t If(s', ,a)]
(164)
We let
w:llwllz Bvd 1
θ {0: fo E 2), a= w:
(165)
be the parameter space of and P, respectively.
We'll repeatedly use the following lemma, which a standard consequence of linear MDP.
Lemma 15 (Linear MDP + Bellman completeness + realizability (infinite-horizon)). Under As-
sumption & we have
(realizability) Q* E Q:
(Bellman completeness) VT and f Q, P
We'll also use the following lemma, which bounds the difference between the optimal value function V* (p) and max (p) - the optimal value over the policy class P, where we
arg max VJ. (p). TEP
(166)
Lemma 16 (model error with log linear policies (infinite- huninite-horizon)). Under Assumptions S we have
log A
Vs S: 0 V*())
(167)
where defined in Assumption W
We omit the proofs of the above two lemmas due to similarity to that of the finite-horizon setting.
Main proof of Theorem IEL separately.
Given the regret decomposition in (50),, we will bound the two terms
Step bounding term (i).
Similar the argument in the finite-horizon setting, invoking
Lemma I& we have
(D( V2-V Fe (p) < I- (Co(f) - Ci(fe, + log |A|
(168)
B
Thus to bound (i), we only need to bound 6, L.(fe, m.) for each E [T]. Define é Q x S x A x as
{(, 8, a, T) (Esre(((e.))aa>aatt [r(s, a) 7f(s', ((s,
(169)
We give the following lemma, whose proof is deferred to Appendix CE:!
43

---

Lemma 17.
Suppose Assumption B m hold. For any 8 E (0, 1), with probability at least 1 5. for any E [T], we have
1
(((", Le(Se, TT)
Σ
B
(o (e(St, 0z, TT)]
2
(1 (1-7) 7)2
C
(dlog
(1-
BdT
+ +(1 (1--7)
T log [A
(170)
for some absolute constant C 0.
By (1668) and Lemma 17, we have
(n(p) V. (p) < a 7
C
BdT
E (a
Tz) +
dlog (1 710
2
(1 (1-9) 7)2
Cal
log IA|
+ (11 (1- 7)2 +1
1
which gives
CT
BdT
(dd s; az me)l+
dlog
7)²
(1 (1-7)6
CaT
T log |A
(1 7)- +1
(171)
Step 2: bounding term (ii). For any x > O, we define
T
dA dooo
1+ dA(1 (A(1-)}²)
(172)
We use the following lemma to bound (ii), whose proof deferred to Appendix ME Lemma 18. Under Assumption & for any 1) have
T
Via (p) v=(
[=1
1
3TdA
E ( (i + (1-
11(1 - -7) d₂(A)
2(1 77)
(173)
By Lemma M. have
T
1- (1-, n11 - 7) dz(2)
3TdA
(ii) < 7
E
(f
(i, +
2(1 7))
(174)
Step combining (i) and (ii). Substituting and (174 into (II). and letting 1) 2. we have
CTa
BdT
CaT
T Tlog IA
Regret(T)
dlog
(1 7)2 +
(1 733
(1 7)6
B
7
2
3TdA
(2(2) +
(175)
- y
a(1 - 7)
2(1 - 77)
Setting
(1 72 log (1
7//2
1/2
T llog [A - -7)
A
a=
and
B
(176)
T
T' log (log A(17/5)
d
44

---

in the above bound, we have with probability at least 1 - 6,
dvT
Log((AA))>)
T3/2
(T) & C²
log
log
+
71-7)2
5
d(1 7)2
for some absolute constant C" > 0. This completes the proof of Theorem 44
C.4 Proof of key lemmas
C.4.1 Proof of Lemma 17
We bound the two terms L, #*) and (fe Te) in the left-hand side of (T7L) separately. Given f.J' S x A + R, data tuple { = (x, a, 8') and policy n, we define the random variable
If. f T) == r(s,a) + 7f(s', d') (s,
(177)
where d' (-(ss'). Then have (recall we define pp in (I644)
(U, = - (s(d) - E2 Raiiinn ino ((s',a')) afmutilo?)
(178)
Combining (177)) and (178), we deduce that for any = S A R. g and ,.
1(f.f',e, 1(f, f,E,
(. d'wet(ee)
[[f. f..
(179)
Bounding (Lr me). For any / 2, and E [7], define j
x Rasna(tee) [1, (T,, 1(S, TPx Ec. m), m
(180)
Then we have for any f E Q:
E 16)
Σ E le f,,, TT)
En (o (.
inf gEΩ
E - Fe De
Le(f,T), (181)
where the inequality uses the fact that IPT E Q which is guaranteed by Lemma upper bound - (fe, we only need to bound - Σ!=1 X X
T Therefore, to
Below we use Freedman's 's inequality (Lemma 2) and a covering number argument to give the desired bound. Repeating similar argument as the finite-horizon setting, for any > 0, there exists an e-net O, C and an e-net Pt C Ω such that
log 00l & dlog (1 1 (1
2vd ) and log [Sel < dloog (1 2BVd
(1-9)8) ()-
(182)
(1 7)c
exp(o(s.a) Tw.)
Let Q. = (fe fo. : 0 E 0c), and Pe = (Te(a)s) Evee "xp(o(s,a')) we) We Scc. For any
Q and π E P. there exists fe Q. and Te Pe such that
24c
X Jerke - -X, fint
(183)
(1-7)2
To invoke Freedman's inequality, calculate the following quantities.
Assumption E eensures that X is bounded:
VfEQ: | (1- 7)22
(184)
45

---

Repeating the argument for (19),, we have
( [x],]] =
Exgaaiiaa almet(l)))
M.S, m]]
8tS Cee T).
(185)
Define the filtration F = o (Dt). then we have (recall Algorithm Gl ensures (st, az) ~ d)
e Q:
E 3 Fi E (() [x [F E (s [e(f, 8/ a2 T)).
(186)
Furthermore, we have
Var [x) [i-1]
E
(X) ),m) [F-1]]
[1(6) )
B Bx ((((0,, oz) + 7s((,,) - [8,, -
E Beg dl
(r() + + - f(0), az) (ereeiaara
[[((
a(mu(ila))
(r(s), +
[f((), - f(s az) Fi-1
16
(1 (1- (ana)))a [e(S, (1, Q.
(187)
where the first equality follows from (77)) and (178) and the second inequality follows from Jenson's 's inequality.
Therefore, by Lemma D. we have with probability at least 1 - 5, for all t E [T]. e Qc ne E Pe:
E (e [ 86, St a.)
x
Jome
C1
E (snaa)aa ((fer Tell +
(1 7)2 log(T(0,110.1/0)
C₁
4Bd (a- (1-7)pe2)
+ log(T/6)) (188)
(e [f(fer 8, an
0,, Re)]
dloo
(1 7
where C > 0 is an absolute constant. T. Pc.
From (8S we deduce that for all / E [7] Se E e. and
Ci (1 71-
4Bd (1- + log((T
Ser
E (e [e(Se, 81, 04 Tc)l
(dlog
(189)
Note that for any & E [7], there exist 0g E θ and wi Ω such that ft = fo, E Q and n. = aw,, P. We can choose dr, O and Wh.c E Ω such that |10, 0r,el12 & and ||w: wr,ell2 & We let ft.e = for.- E Q. Then by (IK9) we have for all t [T],
m.(se.me)
xi fe
2
71
46

---

C1
4Bd
24Te
(1) [e[Fee 81, Oz Reeel
dlog
+ +log(T/6))
(1 (1=
(1 (1-
(1 7)2
Ci
4Bd
( )
+ 36Т
)o [C(Se, 81, 0z, m+)] + (1 1 7)2
dlog
+ +lo
(1 (1-
(1-7)2²
(190)
where the last line follows from (SS)) and
Bounding C,(f", R*), For any f and t E [T], we define
Yj = Ea
[((F
where 10= fr. (191)
Note that for any tuple _ (s, we have
((f (. 1(f", - |00 fUm.f"ETT 1(f J {,5)) -1
E Beselnn ( o'w5+((12)
(192)
where the last line follows from Furthermore, we have
E Basciaa [( 100
2e (r(s, a) + 7f'(s'a')) (s, ('1a)
1Ø (6)) (*)
r((,a) + 7BgewP()).)))
-( VØ= (5') "BOND s,)) V (s')
(193)
where the last line Bellman's optimality equation
r(s, a) + P(.
(VT (8)) f f( =0
(194)
By Lemma IR we have
E. [V (5)) log AA
< Eg-r(()s,)) V3 (5') & Esenoriaaa) [ [s)
(195)
Plugging the above inequality into (143) and (12)), we have
4y log log|AA
[(f' f f" llf [ <
(196)
1-7
The above bound (I9)) implies that
f,lft
B - (f ,,,
inf gER
E Eal
( "f ,9,
1=1
4yT log [A|
sup FEQ
E--r)
(197)
1-7
where also the definitions of Y7, J (c.f. (I91)), and L. (c.f. (159 Thus to bound
C,("","" below we bound the sum Σ Yi for any / E Q and E [T]. To invoke Freedman?s
inequality, we calculate the following quantities.
Repeating the argument for (59) we have
[У]] = Ey Pe(ea()))
(Equacinn [V'* (,,,,,,,,,7)) d
(198)
which implies
27 E Exporttenn [(f* fr, ) dlaartie))
Vf : E F = E B(naaidd
(199)
47

---

We have
Var
[r & IE (x7) Fr--1
E
Ba (ai (r(0), 71 [s,, ax))
(f )1)
-32 - -Bqpallnan d'aas(16()
Fi-1
<
E
0() + 2xf (s(; - f(((; 01) - Eqqar mine) [f
a'werclo))
(((s).a)) + t.Bgga (s( -(((,a)) ((( (lw))(ld))
Fi-1
((
< (1 7)2
16
B (er
P1' (00,,,5577)1 (14
(200)
where the first line uses (by (178))
US" J', (M(tiaa) - -Egrriee (66))a)))
(201)
where a' ~ (+1s)), and the second inequality uses Jenson's 's inequality. Last but not least, it's easy to verify that
4
17 & (1 7)2
(202)
Invoking Lemma and setting 7y in Lemma
(1 -
(1- 7)2
log(10.(7/o)
1 min
- Var /
for each fo E Qr, we have with probability at least -6, 8,
7)
Afe E [T):
Yj. + E (saaa))a5
E Bagaactinnn [(f Ee. #*] ] (laaa(14))
[
) 27
(TT((),TT/5) Σ Blonaaadd
(Eguniingng M(ft fer dlate(in))
1 1->1
+ (1 71 log().
(203)
Reorganizing the above inequality, we have for any Sa E e
27
Σ (-r))) S (1 - 7)2 log((0.(7/8)
E (s
Se,
(
log(le,
E (e
EEguneeaa [(f (( alwar(le()
1
log((O,[T/))
(204)
7)
48

---

where the last line makes use of the fact that -x² + bx < 62/4.
Moreoever, for any E [7], have
xf - xj
(09, fc(s), ( f(0,, az))
4e
(f( ( - se( - f(),, (a(a))))(((()))))) ax) - Je(s), ar))
<
1-
(205)
where the last inequality uses [[ a) Sc(8, a)] < ||o(s, 10 0ell2 < Combining (204) and (205), we have with probability at least 1 - 8, for any E [T] and f E Q.
C2
4eT
Σ i=1
(-x))) < (1 7)2
log O (
T/6)
1 -
C2
2vd
4CT + 1 1-7"
dlog
1+
+ loog +log(T/8)
(206)
(1 21-
(1 7)=
where C2 > 0 is an absolute constant.
By (1 we have
C2
dlog 1+ 2vd
4T (et
log ( (207)
Li & (1 (1-
+ log(T(8)
+ 1 1-7
(1 7)
B
Combining the two bounds.
Combining (1 and (201)) have for any E [[].
((( <
(m [8(fe. Si ai mz)
2 1=1
Bd
+ loog (7) Te + (1 Tog |A]
(dlog
(11 (117)e)
71-
(208)
for some absolute constant C > 0. Letting c t, we obtain the desired result.
C.4.2 Proof of Lemma
K
First note that for any policy π and f S A R. we have
(p) = E nompog=<tlon)) oh-1 wB( Wkikk)e
(>"V7(s)) - ~ (S(+2)s)))
Am
E (ompugeatilog) *h-1 Wihee
(Qr(sh, and (
(209)
and
Mr(sh, anh)
o (ay,) Pe V.NN
(210)
The above two expressions
(2S) and 2411 together give that
V VT)
1 (Qr(sn, an) - r(sn, -
(V7
1==
[y(s,)) r(s, - -PPVF(s,
(211)
1 ?
49

---

where we define
Bx [V]
(212)
and
E(J, 8, a, Q)(,,a)
r(s,a) Q(( -
(PV
(213)
By Assumption & for any f 2, there exists 0f E @ such that [(s, (05, Thus have
=((s,)) (0 05-5 -- 1 ((s.)))0)
(7(()))(()))
(214)
W(fx))
where W(f, 1) satisfies
3 Va
V [W(,,))l < 1-7
(215)
under Assumption g
We define
1 xT(T)= 1- d( [d(s,a)]
(216)
Then we have
1 E Ba [((f,s,a = W(f. x))
-v =
((.
(217)
For all t [T], define
Ac(A) Ala Σ ((T))(()) AY 0,
(218)
where Ia is the x d identity matrix. Then by Lemma we have
Σ min (Ia(T))la 1] < 2og det Ia + E (amm))(a)))
(219)
Further, we could use Lemma 5 to bound the last term in (21%), and obtain
V1 : miin (II((T))) < 2d,
(220)
where in the last line, we use the definition of (A) (c.f. (172)) and the fact that
| 122 & 1-
(221)
which is ensured by Assumption S
Observe that
(p) (z) A8
E 1y [E(fe, a,)))
MBF
(I(TT), W ((ferz)))
((((T))) W m.)) ( <1}
(o(T.), m.)) 1 [ 1
>1}.
(222)
where 1(-) is the indicator function.
To give the desired bound, we will bound (a) and (b) separately.
50

---

Bounding (a).
We have for any A > 0.
W mill I ( =1}
(a)
[W(fa min {1a(a)llaa))-..111
(223)
(W ()) be bounded follows:
1/2
[W m.)la & VA. 3vd
Σ (I(m).) W ((). (((
+
(224)
I 1-7
where we use (1.)
and the fact that Va + & va + vb for any a, b > 0.
(223) and (2244 together give
T
3
1/2
(o)())) W WWe ((inmmaa) min {1o(Ta))a 1.13
1=1
1/2
1/2
9d
Σ min [I((
?)
(a-i)
1/2
1/2
(a((T)) W m())
Σ
min (100)))))
(225)
(n-ii)
where in the second inequality we use Cauchy-Sehwarz inequality and the fact that
min [Ia(T))llA 13 2
Vt
[T]
< min
(226)
(a-i) in (225)) could be bounded as follows:
XdT
(a-i)
7)2 (d)
(227)
To bound (a-ii), note that for any ग, n' E II, we have
(1 7)2 I (oaa)) (8)(s,))-((s,))) - (s, (s)a)
< (1 7)2 E (a,a)aa) [,(f,,,a,T)]
(228)
where the inequality follows from Jenson's inequality, and recall {(f, 8, T) is defined in (169)
Combining (228) and (220)), we could bound (a-ii) in (225) follows:
T
1/2
(a-ii)
2d 2d (A)
E
ai, Te)
(229)
[=1
Plugging (227) and (229) into (255),, we have
1/2
(a) < 1 1-
AdT (1) + 1-7
(2d) Σ
E (l ElSe (s,,, 81, (z)
(230)
51

---

Bounding (b). By Assumption & and (2T77), we have
VT E IT: [((()), ((f, Combining the above inequality with (220), we have
(231)
1-
(b) E 4 (A).
(232)
Combining (a) and (b). Plugging (230 and 2 into 2222) we have
VT (p) (p)
1/2
3
AdT (A)
(A)
Σ
Σ
E
((Sts 8ú, dis me))
(233)
The first term in the right hand side of (233) could be bounded as
3 AdT 2dl (A) <
3
2(1 -7) (AdT + (d),
(234)
1 1-
and the second term in the right hand side of P could be bounded
1/2
(A)
(s Sis mt)
(A)
T
(s) ((ft, Sy, as mt),
(235)
(1 -7)
1
for any 17 > where both M4 and (2E5)
we use the fact that va atb for any a, >
Substituting (233)
and (25 into M4 and reorganizing the terms, we have
T
V (p) v=(
( 1 C(fe (l Te) + (1- 711 7) dn(A)
3TdA
E
2(1 7(1-))'
(236)
This gives the desired result.
52


Reviews:
[{"review_id": "FtlSyFbLVj", "reviewer": "Reviewer_1Y1J", "summary": "The paper revisits optimistic exploration in online RL through a primal-dual lens and proposes a Value-Incentivized Actor-Critic (VAC) algorithm. VAC merges exploration and exploitation in a single, first-order-optimizable objective that favors high-value policies while staying consistent with data. It sidesteps the bilevel optimization hurdle faced by Maximize-to-Explore. Under linear MDPs, VAC achieves near-optimal sub-linear regret in both finite- and infinite-horizon cases.", "questions": "Question 1: I am still not really clear how the proposed method improves the bound in MEX from the order of each variable (e.g., d, H, and T)? Or could the authors provide more intuition for the improvement?", "limitations": "NA", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strength 1: The theoretical results are sound and solid. The presentation is good to follow and clear to understand.\n\nStrength 2:  It is innovative to incorporate the MEX idea to the actor-critic framework and help readers understand how to incentivize exploration from the primal-dual perspective.\n\nStrength 3: The derived sample complexity bound in this paper is nearly optimal and tight, which also matches the results in the other paper.\n\nWeakness 1: From my understanding, one advantage of MEX is to use a single objective for the optimization to trade-off between exploration and exploitation in RL, which is implementation-friendly in the deep RL framework, which is also verified by experiments on Mujoco tasks. However, this paper does not study the empirical performance on the proposed method, which limits the potential of the board application of the proposed method empirically.", "was_revised": false, "final_justification": "", "rebuttal": "## Response to Reviewer 1Y1J\n\nThank you for your positive evaluation and insightful questions! Below we address your main concern.\n\n>**Weakness 1: From my understanding, one advantage of MEX is to use a single objective for the optimization to trade-off between exploration and exploitation in RL, which is implementation-friendly in the deep RL framework, which is also verified by experiments on Mujoco tasks. However, this paper does not study the empirical performance on the proposed method, which limits the potential of the board application of the proposed method empirically.**\n\nThank you for your valuable feedback.\nWe conducted experiments on two difficult MuJoCo continuous control tasks: Walker2d and Ant. We benchmark VAC against the state-of-the-art Soft Actor-Critic (SAC) algorithm [Haarnoja et al., 2018]. The average return and standard deviation of the algorithms over 3 random seeds after 1000,000 training steps are summarized in the following table:\n\n| env / alg | SAC | VAC (ours, $\\alpha=1000$) | VAC (ours, $\\alpha=500$) |\n|---|---|---|---|\n| Ant-v4 | 3163.86 $\\pm$ 268.90 | 3974.44 $\\pm$ 390.95 | **5134.55** $\\pm$ 424.42 |\n| Walker2D-v4 | 4394.68 $\\pm$ 181.42 | **4609.53** $\\pm$ 333.98 | 4434.75 $\\pm$ 117.34 |\n\nThe results demonstrate VAC outperforms the strong SAC baseline.\n\n- **Implementation details**: we use a SAC style implementation with a different Q-learning objective. To be specific:\n\n    - We perform alternating single gradient (Adam) steps to update actor (policy) and critic (Q-function) by solving an approximation version of our objective (17). Same as the implementation of SAC and MEX (see their Section 7.2), we drop the second term in the expression of $L_t(f,\\pi)$ (c.f. Eq.(18)) and use a standard TD error. And we use $1/n\\sum_{i=1}^n Q_{f,1}(s,a_i)$ ($a_i\\sim\\pi(\\cdot|s)$) to approximate the value-incentivized regularization term $V_{f}^\\pi(s)$ (in our experiment, we set $n=1$, which is good enough). \n\n    - Non-linear FA: we use standard MLPs to parameterize both actor and critic, with 2 hidden layers of 256 neurons each, using the ReLU activation.\n\n- **Small theory-to-practice gap:** We'd like to highlight that VAC's theoretical formulation naturally yields an actor-critic algorithm, leading to a very small theory-to-practice gap. This can be contrasted with MEX, where the practical actor-critic implementation used in their experiments (see their Section 7.2) differs significantly from their proposed theoretical bi-level objective which could not be implemented end-to-end in deep RL frameworks for continuous environments in MuJoCo. Instead of using their proposed algorithm, they resort to an actor-critic framework in the experiments that completely circumvent the bilevel optimization.\n\n>**Question 1: I am still not really clear how the proposed method improves the bound in MEX from the order of each variable (e.g., d, H, and T)? Or could the authors provide more intuition for the improvement?**\n\nThank you for your question. As stated in our introduction, our contribution is not improving the regret bound of MEX, but to circumvent the intractable bi-level optimization problem and propose a provable sample-efficient algorithm that's easy-to-implement.\n\n- **VAC and MEX have the same near-optimal regret bound.** MEX doesn't explicitly provide a regret bound for the linear MDP setting, and assumes a finite function class. Adapting their Corollary 5.2 to linear MDPs, and through a covering number argument on the function class, their regret can be shown to have the same order as ours ($\\tilde{O}(dH^2\\sqrt{T})$) (in their Corollary 5.2, $B_l=O(H)$, $d_{GEC}(1/\\sqrt{HK})=\\tilde{O}(Hd)$, and $\\log(|\\mathcal{H}|)=\\tilde{O}(Hd)$). Both our regret is *near-optimal* up to a factor of $\\sqrt{H}$ compared to the minimax lower bound $\\tilde{\\Omega}(d\\sqrt{H^3T})$, as is stated in line 244-246 of our paper.\n\n- **MEX's bilevel optimization objective is hard/intractable to solve.** We want to stress that MEX objective is hard/intractable to solve, and this motivates us to design an easy-to-implement actor-critic algorithm.\n\n    - **The inner maximization $\\max_{a} Q(s,a)$ can be intractable itself.** The MEX objective in Eq.(7) requires computing max_{a}Q_{f,h+1}(s_{h+1},a') for every transition $(s_h,a_h,s_{h+1})$ in the dataset at every gradient step. This is a significant challenge in many settings:\n    - Large discrete action spaces: In domains like large language models, the action space (e.g., all possible tokens or sentences) is enormous. An exhaustive search for the maximum is computationally infeasible.\n    - Continuous action spaces: If $Q(s,\\cdot)$ is non-convex, finding the global maximum is an NP-hard problem. Even with convex Q-functions, this requires running a separate optimization procedure for every data point in the batch, which is computationally expensive.\n    - **The bilevel optimization problem is intractable to solve.**  To minimize the objective $L_t(f)$ given in our Eq.(7) through gradient-based methods, we need to compute $\\nabla_\\theta [\\max_{a} Q(s,a;\\theta)]$, which could be intractable and could not be handled by standard toolkits. Note that simply computing $a^\\star:=\\arg\\max_{a} Q(s,a)$ and computing $\\nabla_\\theta Q(s,a^\\star;\\theta)$ can lead to wrong gradients of the Q-function, because $\\nabla_\\theta [\\max_{a} Q(s,a;\\theta)]$ does not always equal to $\\nabla_\\theta  Q(s,a^\\star;\\theta)$, where $a^\\star:=\\arg\\max_a\\nabla_\\theta  Q(s,a;\\theta)$. A simple example is when \n    $$Q(a;\\theta)=\\begin{cases} a,\\quad\\text{when $a\\leq \\theta$},\\\\ \n    0, \\quad\\text{when $a> \\theta$}. \\end{cases}$$\nThen when $\\theta>0$, $\\nabla_\\theta [\\max_{a} Q(s,a;\\theta)]=1$, but $\\nabla_\\theta  Q(s,a^\\star;\\theta)=0$.\n\n   - **The original MEX Implementation sidesteps this problem.** Crucially, the authors of MEX themselves acknowledge this difficulty in their practical implementation, and circumvent the bi-level optimization entirely. Instead, they resort to an actor-critic framework, creating a significant disconnect between their theoretically analyzed objective and their practical implementation.\n    \nIn contrast to MEX, our VAC algorithm Value-Incentivized Actor-Critic (VAC) algorithm elegantly resolves these practical challenges, leading to a method that is both theoretically sound and straightforward to implement.\n\n---\n\nReference:\n\n[Haarnoja et al., 2018] T Haarnoja et al. Soft actor-critic: Off-policy maximum entropy deep reinforcement learning with a stochastic actorSoft Actor-Critic Algorithms and Applications. ICML 2018."}, {"review_id": "wpWrTVCedj", "reviewer": "Reviewer_rUfp", "summary": "The paper introduces VAC, a primal–dual actor-critic algorithm for online RL that merges exploration and exploitation into a single differentiable objective. It enforces data consistency and rewards high-value policies, achieving provably near-optimal regret in linear MDPs, while offering scalability to general function approximators", "questions": "Major:\n1. The robustness of the algorithm to the violation of assumptions. In particular, quality of linear approximation.\n2. Bellman consistency regularization is interesting but results in bi-level. If the regularizer is not useful in the first place, the entire work you did would not be so useful at the end. Please discuss benefits of the formulation that you simplied. \n\nMinor:\n1. In 1st paragraph of Sec 3: If f is a Q, what is Q_f?\n2: In Eq (10): Is this parameterization always possible?\n3. In Eq (10): what is \\delta_h(s,a)? I guess that is r()_maxQ in Eq (9).\n4. a possible typo: exploration-> exploitation in line 168", "limitations": "1. Works only with linear MDP, in which the quality of approximation can be arbitrarily bad with some features.\n2. Empirical validation is completely missing.", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths\n1. Avoids bi-level optimization via primal-dual approach\n2. Exploration as part of optimization via primal dual perspective; critic's value function serves as a dual variable incentivizing the actor's exploration.\n3. Theoretical results with sublinear regret bounds\n\n\nWeaknesses\n1. Limited to linear MDP and learning good features can be challenging. This is particularly concerning as the same features are used for linear approximation of reward and dynamics. I can take the reward but dynamics model has a high complexity. Finding the same features for reward and dynamics all together can be more challenging than just for dynamics. \n\nMinor: Abstract can be much improved (Introduction can be too): the first half of abstract is too general (you used valuable space for something not essential)", "was_revised": true, "final_justification": "Although the readability of the paper could have been improved, I like the dual perspective on the problem. After the rebuttal, I would like to keep the same rating as is.", "rebuttal": "## Response to Reviewer rUfp\n\n>**W1: regarding feature learning of linear MDP**\n\nThank you for your comment. While we agree that the assumption of a joint linear representation for both rewards and dynamics (Assumption 1) is a significant one, we would like to offer a few points of clarification:\n\n- **validity and flexibility:** In the tabular setting where the state and action spaces are finite, the assumption holds as we could set the features $\\phi_h(s, a)$ to be one-hot vectors,  demonstrating that our framework is a valid extension of a fundamental RL scenario. More discussion on the linear MDP examples can be found in [Jen et al., 2020].\nNote that despite being linear, the Markov transition model $P_h(·|s, a)$ can still have infinite degrees of freedom as the measure $\\mu_h$ in (20) is unknown.\n\n- **Standard assumption for theoretical analysis:** As we remark around Assumption 1 in our paper, this is a standard and widely-used assumption in the theoretical analysis of online RL with function approximation, as established in seminal works like [Jin et al., 2020].\n\n- **Extension to general FA:** We want to highlight that our framework is not fundamentally limited to linear MDPs. Our analysis can be readily extended to general function approximation settings, similar to the approach in MEX [Liu et al., 2024]. By replacing the linear MDP assumptions with more general conditions—namely, realizability and Bellman completeness of the Q-function class, and a bound on the Generalized Eluder Coefficient (GEC)—our VAC algorithm achieves a similar $\\tilde{O}(\\sqrt{T})$ regret. More details about this can be found in our response to W4/Q3 of Reviewer bBXP. \n\nWe'll add more discussions to our revised paper. Thank you for raising this point.\n\n>**W2 (minor): abstract and introduction can be improved**\n\nThank you for your valuable feedback. We will revise the abstract and introduction to be more direct in our updated paper.\n\n>**Q1-major: The robustness of the algorithm to the violation of assumptions. In particular, quality of linear approximation.**\n\n- Our analysis can be extended to handle the misspecification scenario, where the true rewards and dynamics are only approximately linear. The key is to analyze how this approximation error propagates through our algorithm and affects the final regret following a similar idea as in [Xie et al.,2021] or [Yuan et al.,2023].\n\n- As we mentioned in our previous response, Our analysis is readily extended to the general function approximation setting under similar assumptions made in MEX. See also our response to W4/Q3 of Reviewer bBXP for more details on this.\n\n>**Q2-major: Bellman consistency regularization results in bi-level...discuss benefits of the formulation that you simplified.**\n\nThank you for this insightful question. Below is our clarification on the motivation and advantages of our approach.\n\n- **The \"Bellman consistency regularization\" is a principled data-fitting loss.** First, we'd like to clarify the role of the term in question. While our derivation in Section 3 frames it as a penalty term in a Lagrangian, in the final objective (Eq. (17)), it functions as a data-fitting loss term, not an exploration regularizer. This loss term ensures that the learned Q-function $f$ remains consistent with the observed environment dynamics. The actual term that incentivizes exploration is the value-incentivizing term $V^\\pi_f(\\rho)$ in Eq.(17). \n\n- **The benefit of our simplification: from intractable bilevel to tractable saddle-point optimization.** We want to stress that this loss is actually standard and commonly used in the literature, see  [Xie et al.,2021], [Dai et al., 2018] for example. Notably, unlike MEX's the bi-level loss function (EQ.(7)), where $\\max_a Q(s,a)$ is inside the square and the maximum needs to me computed for all states in the dataset, which could be intractable, our loss $L_t(f,\\pi)$ in (18) leads to a tractable saddle-point problem. To see this, we could write $L_t(f,\\pi)$ as $\\sup_{g\\in \\mathcal{Q}} \\tilde L_t(f,\\pi,g)$ for some function $\\tilde L_t$. Then our optimization objective (17) becomes\n$$\\sup_{f,\\pi}\\inf_{g}\\{V_f^\\pi(\\rho)-\\alpha \\tilde{L}_t(f,\\pi,g)\\}.$$\nThis problem is well-studied in the RL literature. For example, Algorithm 1 in [Dai et al., 2018] gives a feasible mirror descent type of method to solve this.\n\nWe'll add more discussion on this in our revised paper. Thank you for raising this.\n\n>**Q1-minor: In 1st paragraph of Sec 3: If $f$ is a $Q$, what is $Q_f$? 2: In Eq (10): Is this parameterization always possible?**\n\n- As defined in lines 163, $Q_f=\\{Q_{f,h}\\}_{h\\in[H]}$ with $Q_{f,h} = f_h$, i.e., $Q_f=f$.\n\n- Yes, the reparameterization in Eq (10) is always possible. This is a constructive reparameterization trick (following [Baird, 1995] and [Dai et al., 2018], as cited on line 185). For any $\\lambda_h$, one can define a corresponding $g_h$ via $g_h(s,a) = Q_{f,h}(s,a) - \\beta\\lambda_h(s,a)$.\n\n>**Q2-minor: In Eq (10): what is $\\delta_h(s,a)$? I guess that is r+maxQ in Eq (9).**\n\nThere's no $\\delta_h$ in (10). We guess you mean $\\delta_h$ apprearing in 187-189, where we specify (11) holds for any $\\delta_h(s,a)$, and be setting $\\delta_h(s,a)=r_h(s,a)+\\max_{a}Q_{f,h+1}(s',a)$ in (11), we obtain (12).\n\n>**Q3-minor: a possible typo: exploration-> exploitation in line 168.**\n\nThank you for your careful reviewing. Here \"exploration\" is indeed the correct term, and we see how this point connects to your insightful question in Q2-major about the role of the objective's components. Specifically, line 168 describes the two distinct parts of the MEX objective in Eq. (6):\n\n- The first term, $\\sup_{f\\in Q} E_{s_1\\sim \\rho} [\\max_a Q_{f,1}(s_1,a)]$, promotes exploration. By optimizing over the function f to find an optimistically high Q-function, the objective incentivizes visiting states and actions that could have high value. This is the core principle of \"Maximize to Explore.\"\n\n- The second term, $-\\alpha L_t(f)$, is the data-fitting loss derived from the regularization term of the Lagrangian (9). Its role is to ensure the optimistic Q-function remains consistent with the observed data transitions, as discussed in our response to Q2-major.\n\n>**Limitation 1: works only with linear MDP, in which the quality of approximation can be arbitrarily bad with some features.**\n\nThank you for raising this point. We agree the performance of any method using linear function approximation is fundamentally tied to the quality of the chosen features. Meanwhile, we want to emphasize that the VAC algorithm itself is not restricted to linear models, and our algorithm is compatible with general function approximation. Furthermore, as we mention in our previous responses, we can relax the linear MDP assumptions and obtain a $\\tilde{O}(\\sqrt{T})$ regret bound for general function approximation setting under similar assumptions as MEX. We plan to write this extension as a section in the appendix in our revised paper. Thank you for your comment.\n\n>**Limitation 2: Empirical validation is completely missing.**\n\nWe conducted experiments on two difficult MuJoCo continuous control tasks: Walker2d and Ant. We benchmark VAC against the state-of-the-art Soft Actor-Critic (SAC) algorithm [Haarnoja et al., 2018]. The average return and standard deviation of the algorithms over 3 random seeds after 1000,000 training steps are summarized in the following table:\n\n| env / alg | SAC | VAC (ours, $\\alpha=1000$) | VAC (ours, $\\alpha=500$) |\n|---|---|---|---|\n| Ant-v4 | 3163.86 $\\pm$ 268.90 | 3974.44 $\\pm$ 390.95 | **5134.55** $\\pm$ 424.42 |\n| Walker2D-v4 | 4394.68 $\\pm$ 181.42 | **4609.53** $\\pm$ 333.98 | 4434.75 $\\pm$ 117.34 |\n\nThe results demonstrate VAC outperforms the strong SAC baseline.\n\n- **Implementation details**: we use a SAC style implementation with a different Q-learning objective. To be specific:\n\n    - We perform alternating single gradient (Adam) steps to update actor (policy) and critic (Q-function) by solving an approximation version of our objective (17). Same as the implementation of SAC and MEX (see their Section 7.2), we drop the second term in the expression of $L_t(f,\\pi)$ (c.f. Eq.(18)) and use a standard TD error. And we use $1/n\\sum_{i=1}^n Q_{f,1}(s,a_i)$ ($a_i\\sim\\pi(\\cdot|s)$) to approximate the value-incentivized regularization term $V_{f}^\\pi(s)$ (in our experiment, we set $n=1$, which is good enough). \n\n    - Non-linear FA: we use standard MLPs to parameterize both actor and critic, with 2 hidden layers of 256 neurons each, using the ReLU activation.\n\n- **Small theory-to-practice gap:** We'd like to highlight that VAC's theoretical formulation natrually yields an actor-critic algorithm, leading to a very small theory-to-practice gap. This can be contrasted with prior work like MEX, where the practical actor-critic implementation used in their experiments (see their Section 7.2) differs significantly from their proposed theoretical bi-level objective. \n\n---\n\n[Jin et al., 2020] C. Jin, Z. Yang, Z. Wang, and M. I. Jordan. Provably efficient reinforcement learning with linear function approximation. In Conference on learning theory, PMLR 2020.\n\n[Liu et al., 2024] Z. Liu, M. Lu, W. Xiong, H. Zhong, H. Hu, S. Zhang, S. Zheng, Z. Yang, and Z. Wang. Maximize to explore:\nOne objective function fusing estimation, planning, and exploration. NeurIPS 2024.\n\n[Xie et al.,2021] T Xie, CA Cheng, N Jiang, P Mineiro, A Agarwal. Bellman-consistent Pessimism for Offline Reinforcement Learning, NeurIPS 2021.\n\n[Yuan et al.,2023] R Yuan, SS Du, RM Gower, A Lazaric, L Xiao. Linear Convergence of Natural Policy Gradient Methods with Log-Linear Policies."}, {"review_id": "ndbhDwl98A", "reviewer": "Reviewer_2BfU", "summary": "This paper presents a method for online reinforcement learning called Value-incentivized Actor-Critic (VAC). The paper starts with revisiting the recent Maximize-to-Explore (MEX) framework, demonstrating how it can be derived from a primal-dual Lagrangian perspective. Motivated by this interpretation, they introduce VAC, an actor-critic algorithm optimizing an objective that integrates policy optimization and Q-function estimation without requiring complex bilevel optimization. \n\nTheoretically, the paper provides rigorous guarantees, demonstrating that VAC achieves near-optimal regret of order $O(d H^2 \\sqrt{T})$ in the finite-horizon linear Markov decision process (MDP) setting, as well as regret guarantees for the infinite-horizon discounted setting. Here, $T$ is the number of episodes, $H$ is the length of each episode and $d$ is the dimension of the feature map", "questions": "- Initially, the dual variables $\\lambda_h$ introduced in Equation (10) (and correspondingly the functions $g_h$) are unrestricted (for the sake of intuition). Later, in the transition from Equation (11) to Equation (12), you explicitly constrain these dual functions $g_h$ to belong to the function class $\\mathcal{Q}_h$. Could you elaborate on why this particular restriction on the dual variables is appropriate? \n\n- You say that \"MEX only admits an actor-critic implementation for $\\alpha=0$,\" which implies that a conceptual actor-critic structure suddenly emerges at $\\alpha=0$. However, even at $\\alpha=0$, MEX still optimizes only a Q-function without explicitly introducing an actor (policy). Could you clarify explicitly what you mean by \"admits actor-critic implementation\" at $\\alpha=0$? Does this statement imply explicitly adding a separate actor policy component at $\\alpha=0$? If not, how does the $\\alpha=0$ setting alone introduce an actor-critic structure conceptually?", "limitations": "As far as I concern, the authors have adequately addressed the limitations of their work, and the paper does not have any potential societal impact.", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "**Strengths:**\n\n- The paper presents a novel algorithm for online RL that does not require bonus computation for exploration nor nested optimization. Thus, it naturally extends to practical function approximation.\n- The paper rigorously shows that their algorithm achieves optimal regret up to a factor of $\\sqrt{H}$.\n- The paper is well-organized, provides proper background, gives clear intuition for the MEX approach, explicitly explains its drawbacks, and shows how the proposed method overcomes these challenges.\n\n**Weaknesses**\n- In terms of theoretical guarantees, the paper does not present fundamentally new results. Near-optimal (and better) regret bounds have already been established for stochastic linear MDPs (He et al., 2023). With that being said, I do believe there is value in an algorithm like the proposed one, which shows greater potential for practical use.\n\n- Lemmas 3 and 4, which are central to the analysis, are presented without sufficient intuition or explanation regarding how their results are derived\n\n- At least to me, the paper does not provide sufficient intuition or explanation regarding what explicitly drives exploration in the proposed method", "was_revised": true, "final_justification": "- The authors' rebuttal clearly addressed my main concerns, particularly regarding intuition for exploration and the main ideas behind Lemmas 3 and 4.\n- Although the theoretical regret result does not improve upon the state-of-the-art, I place significant weight on the practical potential and simplicity of the proposed method.\n\nI believe this is a good paper that should be accepted, and I have updated my score accordingly.", "rebuttal": "## Response to Reviewer 2BfU\n\nThank you for your insightful comments and positive feedback! If our clarifications below address your concerns, we'd appreciate your consideration of increasing your score.\n\n> **W1: In terms of theoretical guarantees, the paper does not present fundamentally new results. Near-optimal (and better) regret bounds have already been established for stochastic linear MDPs (He et al., 2023). With that being said, I do believe there is value in an algorithm like the proposed one, which shows greater potential for practical use.**\n\nWe fully agree with your assessment. Our primary goal was not to establish a new state-of-the-art regret bound, as near-optimal rates for linear MDPs are indeed known. Instead, our main contribution is the design of the Value-Incentivized Actor-Critic (VAC) framework, which we believe exploration without explicit bonus estimation can be widely applicable to any nonlinear function, therefore, holding significantly greater practical promise than prior methods that achieve similar guarantees.\n\n> **W2: Lemmas 3 and 4, which are central to the analysis, are presented without sufficient intuition or explanation regarding how their results are derived.**\n\nThank you for raising this point. We'll add the following discussion in our revised paper:\n\n- Lemma 3 bounds the \"one-step regret\" within the loss function itself: $L_t(f^\\star, \\tilde\\pi^\\star) - L_t(f_t, \\pi_t)$. The proof strategy is to bound $-L_t(f_t, \\pi_t)$ and $L_t(f^\\star, \\tilde\\pi^\\star)$ separately. The key tool for proving both parts is Freedman's Inequality (Lemma 5) --- a concentration inequality for martingales. Freedman's Inequality tells us that when summing up a sequence of random numbers where the expectation of the next number, given the past, is zero (this is a martingale difference sequence), the sum is unlikely to be very large. The bound it provides depends on the sum of the variances of these random numbers.\n\n    We construct specific random variables $X$s (Eq.(52)) and $Y$s (Eq.(76)) for bounding $-L_t(f_t, \\pi_t)$ and $L_t(f^\\star, \\tilde\\pi^\\star)$, resp., and show $-L_t(f_t, \\pi_t)$ and $L_t(f^\\star, \\tilde\\pi^\\star)$ are sums of $X$s and $Y$s, reps. We then prove $X$s and $Y$s form two martingale sequences, bound their variance, and then apply Freedman's inequality, leading to the results in (75) and (97). Lemma 3 follows from combining these two results.\n    \n- Lemma 4 bounds the sum of $V_{f_t}^{\\pi_t}(\\rho)-V^{\\pi_t}(\\rho)$ --- the estimation errors of critic $f_t$ for the current policy $\\pi_t$, over all episodes $T$. \n\n    - Step 1: Decomposing the value difference into single-step errors (Eq.(99)-(103)). We first rewrite $V_f(\\rho)-V^\\pi(\\rho)$as the sum of the expected one-step Bellman errors $\\mathcal{E}_{h}(f,s,a,\\pi)$ over $H$ steps.\n    \n    - Step 2: using linearity to turn errors into inner products (Eq.(104)-(107)). We leverage the linear MDP assumptions to rewrite the Bellman error $\\mathcal{E}_{h}(f,s,a,\\pi)$ as the inner product of the feature vector $\\phi_h(s,a)$ and a \"weight error\" vector $W_h(f,\\pi)$ that captures how far off our learned parameters are from the \"true\" parameters that would make the Bellman error zero.\n    \n    - Step 3: bounding the sum of inner products.The above reformulation converts our problem to a classic problem in online learning and linear bandits, and allows us to bound $\\sum_{t=1}^T |V_{f_t}^{\\pi_t}(\\rho)-V^{\\pi_t}(\\rho)|$ with the classic self-normalizing technique [Abbasi-Yadkori et al., 2011].\n\n\n> **W3: the paper does not provide sufficient intuition or explanation regarding what explicitly drives exploration in the proposed method.**\n\nThank you for your comment. The term $V_f^\\pi(\\rho)$ in our objective (17) -- $\\sup_{f\\in \\mathcal{Q}, \\pi\\in\\mathcal{P}} \\{V_f^\\pi(\\rho)-\\alpha L_t(f,\\pi)\\}$ -- incentivizes exploration. This exploration mechanism is conceptually inherited from the reward-biasing framework [Kumar and Becker, 1982]. Below is an intuitive explanation on it.\n\n- **The exploration driver (the value-incentivized term) $V_f^\\pi(\\rho)$:** This term, which we aim to maximize, encourages the agent to find a joint policy-critic pair $(\\pi,f)$ that promises the highest possible expected return. This is the \"optimism\" principle at the heart of our method.\n\n- **The exploitation driver (the loss term) $L_t(f, \\pi)$:** $L_t(f, \\pi)$ is the Bellman consistency error calculated on the data collected so far. It penalizes any Q-function $f$ that is inconsistent with the observed transitions and rewards. It acts as a \"reality check\", pulling the Q-function towards values that are grounded in the data.\n\n- **The interplay between these two terms.** The Bellman error $L_t(f, \\pi)$ doesn't put much supervision on under-explored state-action pairs. This gives our algorithm freedom: to maximize the overall objective, the critic ($f$) tends to hypothesize an optimistically high Q-value for under-explored state-action pairs, which incentivizes the actor ($\\pi$) to increase the probability of selecting under-explored state-action pairs in order to maximize the overall expected value $V_f^\\pi$, leading to exploration. If the optimistic guess was wrong, the newly collected data will create a large Bellman error in the next iteration, and the $L_t$ term will pull the Q-value back down to reality. If the guess was right, the high value is confirmed, and the agent has successfully found a better policy.\n\nWe'll add this discussion to our revised paper. Thank you for your feedback.\n\n>**Q1: regarding restriction on the dual variables from (11) to (12)**\n\nThank you for your insightful question. \n\n- To answer your question, our interpretation begins with the MEX objective. From Eq.(9) we can directly compute that the optimal $\\lambda_h^\\star$ is $$\\frac{Q_h(s,a)- (r_h(s,a)+E_{s'\\sim P_h}[\\max_{a'} Q_{f,h+1}(s',a')])}{\\beta}.$$ Comparing this and (10), we immediately know that the corresponding optimal $g^\\star_h$ is $$g^\\star_h(s,a)=r_h(s,a)+E_{s'}[\\max_{a'} Q_{f,h+1}(s',a')],$$ the Bellamn optimality target. This indicates that the approximation error incurred by restricting $g_h\\in\\mathcal{Q}_h$ is fundamentally linked to the inherent Bellman optimality error of the function class $\\mathcal{Q}_h$. Particularly, MEX assumes $\\{\\mathcal{Q}_h\\}$ satisfies Bellman completeness in their Assumption 3.1, which guarantees the $g^\\star_h\\in\\mathcal{Q}_h$, and this approximation error becomes 0.\n\n- Moreover, the same logic extends directly to our proposed VAC method. Following an identical derivation for the Lagrangian in Eq. (14), the optimal dual function in our case becomes the Bellman consistency target for the policy $\\pi$, where the max operator is replaced by an expectation: $$g_h^\\star(s,a)=r_h(s,a)+E_{s'\\sim P_h, a'\\sim\\pi_{h+1}}[Q_{f,h+1}(s',a')].$$\nTherefore, the parameterization for $g_h$ is also highly reasonable for VAC because it ties the quality of the dual approximation to a core property of the function class: its ability to represent Bellman updates. Especially, under our assumptions, $\\mathcal{Q}_h$ satisfies Bellman completeness (see our Lemma 10), and this approximation error is guaranteed to be 0.\n\nWe'll add the above discussion to our updated paper. Thank you for your comment.\n\n>**regarding the meaning of \"MEX only admits an actor-critic implementation for $\\alpha=0$\"**\n\nThank you for this very insightful question and for your careful reading of our paper. We agree that our statement in lines 222-224 is confusing and inaccurate. \nWe appreciate the opportunity to clarify our meaning and correct the text.\n\n- Our intention with the $\\alpha=0$ case was based on a mathematical equivalence. When $\\alpha=0$, the MEX objective becomes $\\sup_f [E_{s\\sim\\rho} \\max_a Q_{f,1}(s,a)]$, which is equivalent to $\\sup_f \\sup_{\\pi} [E_{s\\sim\\rho} Q_{f,1}^\\pi(s,a)]$. This admits an actor-critic implementation, and the actor is the greedy policy.\n\n- We found our original characterization of $\\alpha=0$ was incorrect. When $\\alpha=0$, the Bellman consistency loss term Eq.(7) is completely ignored, which encourages finding a Q-function with the highest possible values, unconstrained by data. This corresponds to pure optimistic exploration, not \"no exploration\". We'll replace line 222-224 with the following revised text:\n\n    >*In contrast, MEX does not admit an actor-critic implementation for any $\\alpha>0$ since their data loss term requires the optimal value function, while the data loss term $L_t(f, \\pi)$ is policy-dependent in VAC.*\n\nFinally, we also want to stress the implementation challenges of MEX that motivate our work. The core difficulty lies in the bilevel optimization structure of the MEX objective (Eq.(7)), which may be intractable for both solving $\\max_a Q(s,a)$ and computing the gradients. MEX acknowledges the difficulty, and their practical sidesteps its own theoretical objective by resorting to an actor-critic framework.\n\n---\n\nReferences:\n\n[Abbasi-Yadkori et al., 2011] Abbasi-Yadkori, Y., Pál, D., & Szepesvári, C. Improved algorithms for linear stochastic bandits. NeurIPS, 2011.\n\n[Kumar and Becker, 1982]  Kumar and A. Becker. A new family of optimal adaptive controllers for markov chains. IEEE Transactions on Automatic Control, 1982."}, {"review_id": "lw4UbOev1h", "reviewer": "Reviewer_bBXP", "summary": "The paper addresses the need for sample efficient online RL algorithms in the presence of general function approximation. The authors first provide an alternate interpretation of the Maximize-to-Explore (MEX) algorithm (the model-free variant) as the Lagrangian of a constrained optimization problem with the Bellman optimality equation as the constraint. By changing the constraint to the Bellman consistency equation, they develop an actor-critic algorithm which is more versatile than the inner-loop subroutine of MEX. The authors prove theoretical regret guarantees of their VAC algorithm for linear MDPs, including finite and infinite horizon. They do not provide experiments.", "questions": "My questions follow from the above comments so please feel free to respond to related points at the same time.\n1. Can you compare your theoretical guarantees with the results of existing algorithms?\n2. Can you provide additional details explaining why the MEX subproblem cannot be implemented easily with standard toolkits?\n3. Can you explain how the results in the linear MDP setting can be extended to broader settings?\n\nSmall edits:\n* Line 207: incomplete sentence\n* Line 246: \"but with practical implementation generalizable to arbitrary function approximator\" I am not sure what this means.\n* Line 49: The paper argues that MEX uses the *optimal* value function in the loss term. However, this terminology is confusing as MEX is not using $V^*$ (line 149), but rather $\\max_{a \\in \\mathcal{A}} Q_{f, h} (\\cdot, a)$, i.e., the state value function derived from $Q_{f, h}$.", "limitations": "yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 2, "significance": 1, "originality": 2, "strengths_and_weaknesses": "Strengths\n1. The interpretation of MEX as a constrained optimization problem is useful and opens avenues for potential future algorithmic innovation.\n1. An actor-critic algorithm is more versatile and potentially easier to implement than a double-loop algorithm.\n2. The paper is well-organized and clearly written.\n\nWeaknesses\n1. The paper lacks comparison with theoretical guarantees of other methods. \n2. Since the main advantage of VAC lies in its algorithmic practicality, it would be appropriate to provide experiments and implementation details to strengthen this claim. This is especially since we do not have theoretical guarantees about its performance in nonlinear (neural network) settings compared to existing algorithms.\n3. The paper is not clear about the weaknesses of MEX and why it requires nonstandard implementation. While I understand that MEX has a double-loop structure, I do not see why the inner-loop would be computationally intractable (line 194).\n4. The biggest weakness is that the theoretical analysis applies only to linear MDPs, for which we already have good methods for balancing exploration and exploitation, whereas the work is motivated by developing practical solutions for RL settings with general function approximation. For example, the original MEX paper considers low-GEC MDPs, a broader class of problems that include linear MDPs, linear mixture MDPs, MDPs of low witness rank, MDPs of low Bellman eluder dimension, and MDPs of bilinear class. While I recognize that an actor-critic method can be more challenging to analyze than the original double-loop method, the results of this paper would be significantly strengthened if a broader theoretical setting were considered.", "was_revised": true, "final_justification": "The paper makes a meaningful contribution by providing an actor-critic formulation of the MEX algorithm, which is computationally tractable and theoretically backed. While their initial work only considered the linear case, in the rebuttal they show that it can be extended beyond this setting.", "rebuttal": "## Response to Reviewer bBXP\n\nThank you for your time reviewing our paper. If our responses resolve your questions, we'd appreciate your consideration in raising the score. \n\n>**W1/Q1: The paper lacks comparison with theoretical guarantees of other methods...Can you compare your theoretical guarantees with the results of existing algorithms?**\n\nThank you for your question.\n\n- **Our regret bound is near-optimal.** As stated in line 244-246 of our paper, our $\\tilde{O}(dH^2\\sqrt{T})$ regret bound, compared to the minimax lower bound $\\tilde{O}(dH^{3/2}\\sqrt{T})$, is *near-optimal* up to a factor of $\\sqrt{H}$. \n\n- **We have the same regret bound as MEX under linear MDP.** MEX doesn't explicitly provide a regret bound for the linear MDP setting, and assumes a finite function class. Addapting their Corollary 5.2 to linear MDPs, and through a covering number argument on the function class, their regret can be shown to have the same order as ours ($\\tilde{O}(dH^2\\sqrt{T})$) (in their Corollary 5.2, $B_l=O(H)$, $d_{GEC}(1/\\sqrt{HK})=\\tilde{O}(Hd)$, and $\\log(|\\mathcal{H}|)=\\tilde{O}(Hd)$). \n\n- **Extending to general FA setting, our regret also matches MEX.** Under similar assumptions as in MEX, we can give a regret bound same as MEX under general funcion approximation. See our response to Weakness 4/ Question 3 you arise for more details.\n\nWe'll add these discussion on our revised paper. Thank you for your suggestion.\n\n>**W2: regarding experiments and implementation details**\n\nThank you for your suggestion. First, We conducted experiments on two difficult MuJoCo continuous control tasks: Walker2d and Ant. We benchmark VAC against the state-of-the-art Soft Actor-Critic (SAC) algorithm [Haarnoja et al., 2018]. The average return and standard deviation of the algorithms over 3 random seeds after 1000,000 training steps are summerized in the following table:\n\n| env / alg | SAC | VAC (ours, $\\alpha=1000$) | VAC (ours, $\\alpha=500$) |\n|---|---|---|---|\n| Ant-v4 | 3163.86 $\\pm$ 268.90 | 3974.44 $\\pm$ 390.95 | **5134.55** $\\pm$ 424.42 |\n| Walker2D-v4 | 4394.68 $\\pm$ 181.42 | **4609.53** $\\pm$ 333.98 | 4434.75 $\\pm$ 117.34 |\n\nThe results demonstrate VAC outperforms the strong SAC baseline.\n\n- **Implementation details**: we use a SAC style implementation with a different Q-learning objective. To be specific:\n\n    - We perform alternating single gradient (Adam) steps to update actor (policy) and critic (Q-function) by solving an approximation version of our objective (17). Same as the implementation of SAC and MEX (see their Section 7.2), we drop the second term in the expression of $L_t(f,\\pi)$ (c.f. Eq.(18)) and use a standard TD error. And we use $1/n\\sum_{i=1}^n Q_{f,1}(s,a_i)$ ($a_i\\sim\\pi(\\cdot|s)$) to approximate the value-incentivized regularization term $V_{f}^\\pi(s)$ (in our experiment, we set $n=1$, which is good enough). \n\n    - Non-linear FA: we use standard MLPs to parameterize both actor and critic, with 2 hidden layers of 256 neurons each, using the ReLU activation.\n\n- **Small theory-to-practice gap:** We'd like to highlight that VAC's theoretical formulation natually yields an actor-critic algorithm, leading to a very small theory-to-practice gap. This can be contrasted with prior work like MEX, where the practical actor-critic implementation used in their experiments (see their Section 7.2) differs significantly from their proposed theoretical bi-level objective. \n\n>**W3/Q2: regrading MEX's implementation difficulty**\n\nThank you for pointing out the implementation gap in MEX. Below we elaborate on why the inner “maximize over actions” sub‐problem in (7) is not readily handled by off‑the‑shelf toolkits, and how in practice the authors end up sidestepping it in their code.\n\n- **The inner maximization $\\max_{a} Q(s,a)$ can be intractable itself.** The MEX objective in Eq.(7) requires computing $\\max_{a}Q_{f,h+1}(s_{h+1},a')$ for every transition $(s_h,a_h,s_{h+1})$ in the dataset at every gradient step. This is a signficant challenge in many settings:\n    - Large discrete action spaces: In domains like large language models, the action space (e.g., all possible tokens or sentences) is enormous. An exhaustive search for the maximum is computationally infeasible.\n    - Continuous action spaces: If $Q(s,\\cdot)$ is non-convex, finding the global maximum is an NP-hard problem. Even with convex Q-functions, this requires running a separate optimization procedure for every data point in the batch, which is computationally expensive.\n\n- **The bilevel optimization problem is intractable to solve.** To minimize the objective $L_t(f)$ given in our Eq.(7) thourgh gradient-based methods, we need to compute $\\nabla_\\theta [\\max_{a} Q(s,a;\\theta)]$, which could be intractable and could not be handled by standard toolkits. Note that simply computing $a^\\star:=\\arg\\max_{a} Q(s,a)$ and computing $\\nabla_\\theta Q(s,a^\\star;\\theta)$ can lead to wrong gradients of the Q-function, because $\\nabla_\\theta [\\max_{a} Q(s,a;\\theta)]$ does not always equal to $\\nabla_\\theta  Q(s,a^\\star;\\theta)$, where $a^\\star:=\\arg\\max_a\\nabla_\\theta  Q(s,a;\\theta)$. A simple example is when \n    $$Q(a;\\theta)=\\begin{cases} a,\\quad\\text{when $a\\leq \\theta$},\\\\ \n    0, \\quad\\text{when $a> \\theta$}. \\end{cases}$$\nThen when $\\theta>0$, $\\nabla_\\theta [\\max_{a} Q(s,a;\\theta)]=1$, but $\\nabla_\\theta  Q(s,a^\\star;\\theta)=0$.\n\n- **The original MEX Implementation sidesteps this problem.** Crucially, the authors of MEX themselves acknowledge this difficulty in their practical implementation, and circumvent the bilvel optimization entirely. Instead, they resort to an actor-critic framework, creating a significant disconnect between their theoretically analyzed objective and  practical implementation.\n    \n    We'll include the above discussion in our revised paper. Thank you for your comment.\n\n>**W4/Q3: regarding extending the theory to the general FA setting**\n\nThank you for your question. Our analysis is readily extended to the general function approximation setting under similar assumptions made in MEX.\n\n- Assumptions: \n    1. (Assumption 3.1 in MEX) The Q-function class $\\mathcal{Q}$ satisfies $Q^\\star\\in\\mathcal{Q}$ (realizability), and for any $\\pi\\in\\mathcal{P}$, $f\\in\\mathcal{Q}$, $P^{\\pi} f\\in\\mathcal{Q}$ (Bellman completeness). \n    \n    From Lemma 10 in our paper we can see that Assumption 1 here holds under linear MDPs.\n    \n    2. We set policy class $\\mathcal{P}$ as\n    $$ P_h :=[\\pi_h:\\pi_h(s,a)=\\frac{\\exp(BQ_h(s,a))}{\\sum_{a'}\\exp(BQ_h(s,a'))}, \\forall Q_h\\in\\mathcal{Q}_h]$$\n    with some constant $B>0$.\n    \n    3. (Generalized Eluder coefficient (GEC), Assumption 4.2 in MEX) Given any $\\lambda>0$, there exists $d(\\lambda)\\in R_+$ such that for any sequence $f_t$ in  Q and $\\pi_t$ in P ($t=1,...,T$), we have $$\\sum_{t=1}^T (V_{f_t}^{\\pi_t}(\\rho)-V_{f_t}(\\rho))\\leq \\inf_{\\eta>0}\\eta\\sum_{t=1}^T\\sum_{i=1}^{t-1}\\sum_{h=1}^H E_{(s_i,a_i)\\sim d_{\\rho,h}^{\\pi_i}}\\ell_h(f_t,s_i,a_i,\\pi_t)+d(\\lambda)/\\eta +\\sqrt{d(\\lambda)HT}+\\lambda HT$$ for each $\\lambda>0$, we denote the smallest $d(\\lambda)$ that makes the above hold as $d_{GEC}(\\lambda)$.\n\n    From Lemma 4 we can see that under linear MDPs, Assumption 3 here holds with $d_{GEC}(\\lambda)\\lesssim Hd$.\n    \n    4. $\\mathcal{Q}$ has finite $\\epsilon$-covering number.\n    \n    MEX directly assumes $|\\mathcal{Q}|$ is finite. Under linear assumptoins, we bound the covering number of $\\mathcal{Q}$ in the proof of Theorem 1.\n    \n- Results: under the above assumptions, setting $\\alpha =\\tilde{O}\\left(\\frac{d_{GEC}(\\sqrt{H/T})}{TH^3}\\right)$, $B=T\\log|A|/H$, with high probability, the regret of Algorithm 1 satisfies\n$$\\text{Regret}(T)=\\tilde{O}\\left(H^{3/2}\\sqrt{Td_{GEC}(\\sqrt{H/T})}\\right).$$\n\nUnder linear MDPs, the above regret reduces to (22) in our Thorem 1. Besides, this bound also matches (is slightly tighter than) the bound given in Corollary 5.2 of MEX.\n\n- Proof idea: note that the assumptions we make here (and in MEX) are verified under linear MDPs in our paper in the proof of Theorem 1. We could give the above result following the same logic of the proof of Theorem 1  without the need to prove the parts guaranteed by the new assumptions.  \n\nWe'll write the extended results as a section in the appendix of our revised paper if we were accepted. Thank you for raising this point.\n\n> **Small edits (line 207,246,49).**\n\nThank you for your careful review. \n\n- We'll correct the imcomplete sentence in line 207. \n\n- For line 246, we apologize for the unclear phrasing. We meant that while our theoretical analysis is provided for the linear setting, the VAC algorithm itself is compatable with general function approximation, unlike most other works guided by the principle of optimism in the face of uncertainty (see our discussion in Section 1). We will clarify this in the text.\n\n- In line 49, our \"optimal value function\" refers to the value function derived by acting greedily with respect to the current Q-function estimate (i.e., $\\max_a Q_{f,h}(\\cdot, a)$), not the true optimal value function of the MDP. We will revise the terminology throughout the paper.\n\n---\n\nReference:\n\n[Haarnoja et al., 2018] T Haarnoja et al. Soft actor-critic: Off-policy maximum entropy deep reinforcement learning with a stochastic actorSoft Actor-Critic Algorithms and Applications. ICML 2018."}]

Author rebuttal:

Meta-review: The authors study a setting that is standard in RL theory (linear MDPs). Although their regret bounds exhibit no improvement over existing ones (in fact, statistically optimal algorithms for this setting are known), they achieve so with an algorithm that has a primal-dual structure (this allows to draw connections with practical actor-critic algorithms) *and* is computationally efficient. The reviewers agree on the value of this contribution. The reviewers' suggestions and the new experiments should be included in the final version.
Decision: Accept (poster)