Actor-Critics Can Achieve Optimal Sample Efficiency
Authors: Kevin Tan
Wei Fan
Yuting Wei
Venue: ICML 2025 poster (2025)
Keywords: actor-critic
policy gradient
strategic exploration
optimism
reinforcement learning
sample efficiency
Primary area: theory->reinforcement_learning_and_planning
TL;DR: Actor-critic algorithms with general function approximation can achieve $\sqrt{T}$ regret and $1/\epsilon^2$ sample-complexity without assuming reachability or coverage.

Abstract: Actor-critic algorithms have become a cornerstone in reinforcement learning (RL), leveraging the strengths of both policy-based and value-based methods. Despite recent progress in understanding their statistical efficiency, no existing work has successfully learned an $\epsilon$-optimal policy with a sample complexity of $O(1/\epsilon^2)$ trajectories with general function approximation when strategic exploration is necessary. We address this open problem by introducing a novel actor-critic algorithm that attains a sample-complexity of $O(dH^5 \log|\mathcal{A}|/\epsilon^2 + d H^4 \log|\mathcal{F}|/ \epsilon^2)$ trajectories, and accompanying $\sqrt{T}$ regret when the Bellman eluder dimension $d$ does not increase with $T$ at more than a $\log T$ rate. Here, $\mathcal{F}$ is the critic function class, and $\mathcal{A}$ is the action space. Our algorithm integrates optimism, off-policy critic estimation targeting the optimal Q-function, and rare-switching policy resets. We extend this to the setting of Hybrid RL, where we show that initializing the critic with offline data yields sample efficiency gains, and also provide a \textit{non-optimistic} provably efficient actor-critic algorithm, addressing another open problem in the literature. Numerical experiments support our theoretical findings.

Actor-Critics Can Achieve Optimal Sample Efficiency
Kevin Tan 1
Wei Fan
Yuting Wei
Abstract
especially in the presence of function approximation CCai
Actor-critic algorithms have become corner- stone in reinforcement learning (RL), leverag- ing the strengths of both policy-based and value- based methods. Despite recent progress in un- derstanding their statistical efficiency, no existing work has successfully learned an c-optimal policy with sample complexity of O(1/E²) trajecto- ries with general function approximation when strategic exploration is necessary. We address this open problem by introducing a novel actor- critic algorithm that attains a sample-complexity of OdH) 5 log [A/e² + dH log [F)/²)) trajecto- ries, and accompanying vT regret when the Bell- man eluder dimension d does not increase with T at more than a log T rate. Here, F is the critic function class, and A is the action space. Our algorithm integrates optimism, off- off-policy critic estimation targeting the optimal Q-function, and rare-switching policy resets. We extend this to the setting of Hybrid RL, where we show that ini- tializing the critic with offline data yields sample efficiency gains, and also provide non-optimistic provably efficient actor-critic algorithm, address- ing another open problem in the literature. Numer- ical experiments support our theoretical findings.
al. 2024 Zhong and Zhang 2023 Sherman et al. 2024
Liu et al. 2023b) which is required in real-world applica- tions with prohibitively large state and action spaces.
However, much existing work (Abbasi- Yadkori et al. 2019
Neu et al. 2017: Liu et al.
2023a Bhandari and Russo
2022 garwal et al. 2021 Cen et al.) 2022 Gaur et al. 2024 on the convergence of actor-critic methods requires assumptions on the reachability of the state-action space or on the coverage of the sampled data. [iu et al. (2023b) remark that this implies that the state-space is either well- explored or easy to explore. This allows the agent to bypass the need to actively explore the state-action space, making learning significantly easier easier[[herefore Therefore, these approaches analyze actor-critic methods from an optimization perspec- tive and do not address the problem of exploration (Efroni et al. 2020 salient problem that we seek to tackle, hence the need for strategic exploration.
Without reachability assumptions, policy gradient methods
struggle due to lack of strategic exploration? ? A recent line of work utilizes optimism address this, Efroni et al. (2020); Wu et al. (2022) and Cai et al. (2024) achieve vT regret within the settings of tabular and linear mixture MDPs respectively, with Wu et al.] (2022) attaining the minimax- optimal rate. Still. Zhong and Zhang (2023) remark that these analyses do not generalize to more general MDPs due to the need to cover an exponentially growing policy class.
1. Introduction
Within linear MDPs, (Sherman et al. (2024) and Cassel and Rosenberg (0024) have very recently been able to obtain the optimal rate of vT regret or 1/e² sample complexity. They do so via methodological advancements (specific to linear MDPs) that let them overcome the growing policy class issue. However, the problem is unresolved with general function approximation - the best known algorithm from Liu al. (2023b) requires at least 1/c² samples, increasing to 1 1/e² when the policy class grows exponentially.
Actor-critic algorithms have emerged as a foundational ap- proach in reinforcement learning (RL), mitigating the defi- ciencies of both policy-based and value-based approaches
(Sutton and Barto 2018 Mnih et al. 2016 Haarnoja et al.] 2018). These methods combine two components: an actor, which directly learns and improves the policy, and critic, which evaluates the policy's quality. Given their popularity, significant recent progress has been made in understand- ing their theoretical underpinnings and statistical efficiency,
Under coverage/reachabiiity assumptions, the linear conver- gence of policy-based methods (Lan) 2022 Xiao 2022 Yuan ct al..
Equal contribution 'Department of Statistics and Data Science, The Wharton School, University of Pennsylvania, USA. Corre- spondence to: Kevin Tan <<kevtan@ wcharton.upenn.com
2023) and the gradient domination lemma (Kumar et al. 2024 Mei
2022 allow natural actor-critics to learn c-optimal policy within I/e- samples, although vanilla policy gradient methods can take (super) exponential time to converge ct 2021
et al.
Proceedings of the 42nd International Conference Machine Learning, Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).
"To illustrate, this was not solved until Agarwal ct al. 2020 who required 1/c" samples do so in linear MDPs

---

Actor-Critics Can Achieve Optimal Sample Efficiency
Algorithm
Sample Complexity
Regret
Remarks
Agarwal et al.
2020
H log [A
None
Zanette al.
2021
I1* log Alfe d pp log LAye
Vor A loR LATT V
Zhong und Zhang
2123
&' I1 log je + d'Il'fe je
V& log [AT VI
Linear MDPs only
Sherman et al. 21144
d' H" log [A|/2
Va' log IAT
Casscl and Rosenbery
X024
dH 9 log, [AI/ + d//2
V aa log [AT + VaSHUT
Zhou et al. 2023
(lug A| + C A Can log //
Linear
Requires offline data "Good" case only. 1/e* generally
Liu et al.
20236
dlog [A] log F [ fe)
None
DOUHUA (Algorithml
H² lug [AIfe dH' log 157//"
H log LAIT vaH log DF[T
"Good" case only, vacuous generally
NORA (Algorithm
aH log [AI/ + dhr log FFVe
Val LAT lof LF
Holds generally
Table 1. Comparison of our work to existing literature. Algorithm S achieves the best known bound for actor-critic methods with general function approximation, and resolves an open problem on whether VT regret or 1/e² sample complexity is achievable in this scenario.
An open problem. No actor-critic algorithm with general function approximation is currently known to achieve 1 l/² sample complexity or VT regret in this more challenging setting where strategic exploration is necessary. [Zhong and Zhang (2033) and Liu et al.] (2023b) remark that way forward to achieve the desired 1/c² sample complexity remains unclear, and raise the open problem:
setting of hybrid RL
(Nakamoto et al., 2023 Amortila et al.)
2024 Ren et al.
2024;
Wagenmaker and Pacchiano 2023), )
where Song et al.
(2023) show that using both offline and on- line data allows one to achieve /T regret without optimism. However, the claimed /T regret bound in Zhou et al. 20223)
requires on-policy sampling of O(T) samples per timestep that does not contribute to the regret, leading to sample complexity of 1/e². Their algorithm cannot achieve sublin- ear regret in the more common setup where each sample contributes to the regret, while requiring bounded occupancy measure ratios of the optimal policy to any policy.
Can actor-critic or policy optimization algorithms achieve 1/e² sample complexity or VT regret with general function approximation and when strategic exploration is necessary?
This paper. We resolve this open problem in the affirma- tive. As a warm-up, we first consider an easy case where the complexity of the class of policies considered by the pol- icy optimization procedure does not increase exponentially with the number of (critic) updates Then, simple modifi- cation to the GOLF algorithm [Ji et al. (2021) allows one to achieve regret of / H log [A line with the results of (Efroni et al. 2020; Cai et al. 2024
We demonstrate that these issues can be mitigated. Specifi- cally, extend our optimistic algorithm to leverage both offine and online data, and show that actor-critic meth- ods can benefit from hybrid data and achieve the provable gains in sample efficiency as observed in (Li et al.) [023] Tan and Xu, 2024; (Tan et al., 2024). We also provide a non-optimistic provably efficient actor-critic algorithm that only additionally requires Nott 2 (F, (F,)), /22 offline samples (with bounded single-policy concentrability) in ex- change for omitting optimism. This, along with the result in Theorem sample efficiency gains with optimistic algorithms and com- putational efficiency gains with non-optimistic algorithms.
d log [
T, in
for tabular and linear mixture MDPs respectively.
However, this is not the case in many practical scenarios for example, where one uses linear models, decision trees, neural networks, even random forests for the critic. In this much harder setting, Al Algorithm[ [ does not achieve sublinear regret. We address this by introducing an algorithm, NORA (Algorithm 2. which leverages three crucial ingredients: (1) optimism, (2) off-policy learning, and (3) rare-switching critic updates that target Q* and accompanying policy resets. Algorithm 2 achieves / vdH log F[T + / dHH log |A[T regret, requiring only factor of d.H log T more samples than Algorithm 1 even in the best case for the latter.
4 shows that hybrid RL therefore allows for
Notation. NA(p)) denotes the p-covering number of a set A, and (p) that of A U B. We use standard asymptotic notation: f(n) = Ogg(n) if (n) grows at most as fast as g(n); f(n) = (()))) if it grows strictly slower; f(n) = ((g(n)) if it grows at least as fast; and fn) = (g((n) if it grows at the same rate.
2. Problem Setting
Extensions to hybrid RL. Zhou et al. (023) use both of- fline and online data to bypass the need to perform strategic exploration in policy optimization. This corresponds to the
Markov decision processes. This paper focuses on finite horizon, episodic MDPs, represented by a tuple
M = (S, H, where S is the state space, A is the action space. H is the horizon, Th : S + [0, 1] is the reward function at step
(ra)
Zhong and Zhang 2023) showed that the log-covering number of the policy class increases in the number of actor and critic updates. We sharpen this bound to the number of critic updates.
2

---

Actor-Critics Can Achieve Optimal Sample Efficiency
h and Pr, : A ((S) is the transition kernel for step h. A policy (m ) is set of H functions, where each Th S (AA) maps from a state step h to a probability distribution on actions. Write II for the class of all policies, and क (s) as shorthand for the random variable a ~ x x-16))- Given a policy {Th J and reward function {r the state value function is defined as
Assumption 2 (Generalized Completeness). There exists an auxiliary function class 9 = 91 ... x Gn, where each Ih E Gh satisfies yh S x A - [0, H). that is sufficiently rich such that it contains all Bellman backups of f E F..
This auxiliary function class is (T")TF= = (Ta(7)
T / I E F, 711) (11) E [I] for Algorithm D and TF = [TS I E F} for Algorithm [ The former is far larger than the latter, with exceptions that we highlight in Section 3 We write (p)(p) for the p-covering number of a function class F F To learn ʃ E F that approximates the Q-function of a policy π (we say that f targets T), it is common to minimize the temporal difference (TD) error over a dataset D, as an estimate of the Bellman error: c((,x)) (Sn, c In+1)
(s) E
Σ
Th (sw, ss =
where the expectation is taken over the randomness of ane ~ Th (sw) and 51'+1 ~ Prx(]sww any) for any h' 2 h. The action value, or Q function is defined as
(s. = E
Σ h=
(sw, (eow;aw))sss 1ss 8, 0 =
(Jh(s,a) (o,0.T,e)ED
Σ
- r --nrr--n+i6 Sn+ild', Th+1 (n+1(6,,T+ (1)
where the expectation is taken over the similar randomness of action and state transition, with the only difference that the action randomness is only random h' 2 h h-1 1.
Measures of complexity. The complexity of online learn- ing in the presence of general function approximation is governed by complexity measures such as the Bellman rank (Jiang et al. 2016)) which corresponds to the intrinsic dimen- sion in tabular, linear, and linear mixture MDPs. Another the Bellman eluder dimension (Jin et al. 2021). which sub- sumes the Bellman rank and additionally characterizes the complexity of kernel, neural, and generalized linear MDPs. We use the squared distributional version:
Without loss of generality, write $1 for the initial state. The optimal policy is x² = argmax, V (s1). Correspond- ingly, we denote V* = V and Q = Q" as the optimal value and Q-functions. The Bellman operator with respect to the greedy policy and any policy x is given by
Th ThQN+1 a) = (n((s, a) + Ed
a'EA Qu+rls', a')]
max
Definition 1 (Squared Distributional Bellman Eluder dimen- sion (Jin al. 2021 Zhong al. 2022 Xiong al., 2023); ). Let F be function class. The distributional Bellman Eluder dimension is the largest d such that there exist measures (d ,....dhh ddd-1)) }, d,a Bellman errors (6 , 0 ((d11).
Th (8, a) = (s, + Eg ,5,,(+2
The optimal Q-function Q' uniquely determined as the so- lution to the Bellman equation: Q7 = Th (s, a). Our goal is typically to learn an e-optimal policy म, such that (s1) (s1) S or to obtain sublinear regret over 7 rounds while playing (I(())T)
,.... 8/()) aand some e' 2 e, such that for all t = 1,....c, d.
E Roe 16621
(t) and
E (( S E
Reg Reg(T) - Σ (vi()))- - (si)) =(T).
(Jin et al., 2021) primarily consider two types of distribu- tions: (1) distributions Dy- induced by greedy policies Tf, and Dirac delta measures over state-action pairs DA. They suggest an RL problem has low Bellman eluder dimension if either variant is small. Examples include tabular MDPs, where this is the cardinality of the ilate-action space, and linear MDPs, where this is the corresponding dimension.
RL with function approximation. Under general function approximation, we approximate Q-functions with a function class F= (Fi hne(m), where each fn : S x A - [0, H). The Bellman error with regard to f E F is fn Tn. Tn and additionally with regard to π E II as fn - TV fM+1- Addi- tionally, we write TH (a|s) = 1 (a' E arg a Jn (8. a)) for the greedy policy that plays the best action under f. We make the following routine assumptions on the richness of
The sequential extrapolation coefficient (SEC) of et al. (2022) subsumes the Bellman eluder dimension: Definition 2 (Sequential Extrapolation Coefficient (SEC). SEC(F, II?) = max kE(M] fOT (()) (T
F (Jin et al. 2021 Xie et al. 2022 Rajaraman et al. 2020 Rashidinejad et al. 2023):
sup
sup
Assumption 1 (Realizability). The function class F is rich enough such that for all h E [H] the function class Fi contains the optimal action value function Qú: Q7, E Fi-
"The p-covering number of class corresponds to the smallest cardinality of of points, such that every point in the class is least p-close to some point in that set. See (Wainwrigh 2019).
3

---

Actor-Critics Can Achieve Optimal Sample Efficiency
B 1/ Tnsh+1] H V i-l By0 (1hh - -Th
Algorithm Double Optimistic Updates for Heavily Updat- ing Actor-crities (DOUHUA)
Input:
Function class F.
2: Initialize: F + F, h < 0. learning rate vj =
The SEC is always bounded by dllog T, but there exist MDPs that have a Bellman eluder dimension d on the order of vT, but constant SEC (Xie al. 2022). We shall use these measures of complexity characterize the regret. Algorithm scales with the SEC, which is more general and weaker than the Bellman eluder dimension. Algorithm 2 as presented, has a switching cost that scales with the Da -type Bellman eluder dimension. While this can be weakened to the more general le eluder condition of (Xiong et al.) 2023) with nothing more than change in notation, we present our results in the Bellman eluder dimension framework for familiarity and ease of presentation.
((ylog (AH--2--1, policy x(1) width / = (loog(HTT))
1, confidence (TTTT)))))
3: for episode = 1,2, , do
4: (s, argmax JEFU I, (.- 11 11 fn (s, as, a,
5: Play policy T(t) for one episode, update dataset D/
6: Compute confidence set F(t,(!))
F(lea!)) + { 2/ ((( (fhr fh+22)
c(eral)) (shiJn+1) S H23 xh
min Cn
RREFF
f ((txxl)) (J,8'
Policy optimization and actor-critic algorithms. Policy optimization approaches optimize directly in the space of policies, enabled by the policy gradient theorem (Sutton and V (s1) = E, [QT (s. V log (T, a)]. This can be done with Monte-Carlo estimates of Q (s. a) (the REINFORCE algorithm), or a learned estimate of QT a) called a critic (actor-critic methods).
Σ
(f(s,a) (rs. (1b,,
7: Update Th
(++1) (alss) x nla
(als)
l (als) exp(nf (s.a)).
Barto 2018):
8:
end for
for actor-critic approache with only two (very natural) changes. The critic targets QT(() instead of Q" while per- forming optimistic planning at every 8, pair, and we main- tain a stochastic policy that is updated with Equation 2 Learning an optimistic critic off- off-policy achieves sample efficiency by reusing data while exploring efficiently
However, vanilla policy gradient methods can converge very slowly in the worst case (Li et al. 2221). It is often prefer- able to use other optimization algorithms, such as a second- order method in natural policy gradient (NPG) [Kakade] 200T), KL-regularized gradient ascent in trust region policy optimization (TRPO) from Schulman al. (2017). or proxi- mal policy optimization (PPO), which performs a similar, but easier to compute, update. These methods are closely related in the limit of small step-sizes, and are approximate
Algorithm maintains confidence sets F((,z(()) that contain all / E F where the TD error ch c(t,z())
with respect to the Bellman operator T,r(() is H #123-additiive approximation
versions of mirror ascent (Schulman et al. 2017 Neu et al. 2017 Rajeswaran et al. 2017).
of the minimizer minger, e.F, < c(t,x(')) fn+1). Upon the start of each trajectory' f, Algorithm [ maximizes among all functions in the confidence set to play fh (s, a) = sup / 1) (s, for all 8, a. This is exactly
One instance in which the NPG, TRPO, and PPO up- dates coincide is with softmax policies (Cai al. 2024
Cen et al. 2022; Agarwal et al. 2021): T[a
exp(g( s,
A explg(s, a)) for some function :
in line with GOLF, except that the critic targets QT(" in- stead of Q", and we perform optimistic planning with regard to every state and action like Liu et al. (023b)) We then perform a mirror ascent update Th 1F+1)) o Thh (1) exp(nfh")
S x A + R. In this case, the update has a closed form:
(++1) n
(als) x m (2) (als) exp(nsh" a)), S EF. (2)
((t) This algorithm instead of playing the greedy policy T satisfies the following regret/sample complexity bound:
As mirror ascent, this update is identical to the multiplica- tive weights or Hedge algorithm. Like (Cai al. 2024
Zhong and Zhang, 2023 Liu et al. 20236). we exploit this equivalence to prove our desired regret bounds.
Theorem (Regret Bound for DOUHUA). Algorithm 7 achieves the following regret with probability at least 1 - 8:
3. Optimistic Actor-Critics The Easy Case
Reg(T) = O (v (/ log AA (BIITTEEC(FFLL.)
We now present an optimistic actor-critic algorithm, DOUHUA (Algorithm []. with provable guarantees un- der general function approximation. DOUHUA is a nat- ural derivative of the GOLF algorithm of Jin et al. (202))
where 8 θ (log (TT
To learn
'Or completely off-policy version of Liu et al. 2023b "Similarly to Cai et al. 2024) in linear mixture MDPS.

---

Actor-Critics Can Achieve Optimal Sample Efficiency
an e-optimal policy, it therefore requires:
A Good Case. However, within certain cireumstances, it is possible to have (0) = O(log. happens, for instance, when there exists low-dimensional representation of the sum of clipped Q-functions such as when the sum of clipped Q-functions is a scaled Q-function: Definition 3 (Closure Under Truncated Sums). FF closed under truncated sums if for any T E N and f()) ,-., ((.))(())) F.T E min fiin(me |max f()), H,,
(ollgg.N7()) (p)). This
N 2 (17 |A// + F (1,
Proof. We provide proof sketch here, leaving the full proof to Appendix A We decompose the regret with Lemma 3
(Tg(T) T -Σ'E, B h=
(sh,)) (sh,)), o (-1 8h)) Th (0) (.1 sh))
As such, this is an interesting case where the log-covering number of the policy class does not blow up, with down- stream implications for the regret of Algorithm []
Tracking of (7()
waL x², bounded by mirror ascent arguments.
T H
Lemma 2 (Policy Class Growth). Let F be a function class that satisfies Defimition S i.e. it is closed under Iruncated sums. Then, log.N =(p) = OOlog (p² /T)H²T)).
[1m -h "h (ht)) (sh, ]n)]
Em
1=1
h=11
Negative Bellman error under ", bounded by optimism.
Corollary (Regret of DOUHUA, The Good Case). I is closed under truncated sums, then with probability at least - 5, Algorithm 2 Jaciives a regret of:
T
[1% Th shil) (sh, as))
Reg (T) = 0 (v Ho IA + VSHHTSEC(F.II.T)
Bellman crror under current policy occupancy, bounded by critic orror.
where B @(log(HT, (H/ log |A)) To learn
By a mirror ascent argument in Lemma 4 and our choice of learning rate 7 = O(v -HH-2T-- the first term is bounded by v HH log AA.
e-optimal policy, it therefore requires:
2 Ω (H log LA//2 + H (I,,C(F,I,,T)CC"
Lemma establiihhss optimism: SA 2 Th (t-1)) (t) see in Lemma
h- So we
We defer the proof of Lemma 2 to Appendix A.5.3 Al- gorithm [ Ihen achieves a regret in line with the results of
5 that the second term decomposes into non-
positive term
1=
h=1
If B.g
Th (1-) (!))
and h+1 J/ (1)
(Efroni et al. 2020; Cai et al.) 2024) for tabular and linear mixture MDPs respectively. However, closure under trun- cated sums is very strong condition that is not fulfilled by many function classes, although tabular classes fulfill it. It is not fulfilled by linear models due to the clipping operator, requiring Sherman et al. (2024) and Cassel and Rosenberg (2024) to develop bespoke algorithms to get around this in the setting of linear MDPs 8 With trees, random forests, boosting, and neural networks, without further assumptions, one needs to increase the size of the function class perhaps even on the same order as the increase in Lemmal
ΣL Σ H R= B
(00) T++1
(t) h Jht1 S TH
Bounding the Bellman error under the (+) occupancy mea- sure in Lemma 6 by /BHATS II, TYT, where / = @ (log (HTNE))T yields the result. O
A Vacuous Bound. The form of the above regret bound is appealing at first glance. However, the log-covering number of the policy class increases linearly with the number of critic updates by default, as we show below in Lemma 7
Lemma 1 (Bound on Covering Number of Policy Class, Modified Lemma B.2 from Zhong and Zhang (023)). Con- sider the policy class ITTT) obtained by performing T up- dates of the mirror ascent update as in Eq. 2 where the critics (( e F are updated at times t1, tK- Then, the covering number of the policy class at time T is bounded by
This prompts us to explore the possibility of algorithmic modifications to Algorithm I in order to achieve the optimal regret rates in the harder, more general case where the log- covering number of the policy class may increase linearly in critic updates. We do so in the next section.
4. Optimistic Actor-Critics - TThe Hard Case
N Yugr)(p/211 S II N ( 116///KH1TT
Given what we have seen in our analysis of Algorithm | can we simply modify Algorithm [ to include rare-switching critic updates? If we can perform only O(HH log T*) critic updates as in (Xiong et al. (023), perhaps it may be possible to obtain a similar regret bound to Corollary
The proof is deferred to Appendix A.5.2
Within Algorithm
I this implies that log Nyr (p) = OT log)N=(p)) in general, making the bound in Theorem I vacuous.
It was previously thought in Zhong and Zhang (2023) that the log-covering number of the policy class increases in the number of actor and critic updates. We sharpen this bound to the number of critic updates in Lemma [ which may be of independent interest.
Thhese avoid truncation by using reward-agnostic exploration and feature shrinkage respectively. The moving target issue bypassed with rare-switching bonus (but not critic) updates.
5

---

Actor-Critics Can Achieve Optimal Sample Efficiency
Vt
up to the critic updates. To address this issue, we introduce policy resets every critic update, allowing us bound this with the standard mirror descent regret bound as in Lemma The total tracking error scales with the number of critic updates, which is then resolved with rare-switching critic updates in line with (iton et al. (223). Lastly, we increase the learning rate to reduce the regret incurred by the policy resets. This makes more aggressive policy updates catch up with the sudden, rare, and large critic updates.
8r
V
Vi
12
W/ VM
plin
T
1
1
1
Summary. Algorithm combinees optimism for strategic exploration and off-policy learning for sample efficiency, While rare-switching critic updates are a-priori appealing, they are unstable when the critic targets T(1,, due to lim- ited optimism and the challenge of tracking moving pol- icy (as we describe below, and further show in Appendix F These are resolved by largeling n² and re-introducing rare- vare-switching critic updates respectively. However, this introduces additional error, as the agent has to effectively unlearn the policy after each rare critic update. We there- fore introduce policy resets to the uniform policy after each critic update- incurring minimal cost due to their rarity (as there are only OdH log T) updates). A more aggressive learning rate (by a factor of vdH log T') mitigates some of the additional regret incurred, and can be seen making more aggressive updates to make up for lost ground from policy resets. See Appendix B for more details.
Figure 1. Illustration of tracking error in policy optimization, with a rare-switching critic ((t) that targets x². The (blue and pink, pink) area depicts the tracking error of {-" to ( (0 to (")). Both incur vT regret. In contrast, f(t,=(()) is rare-switching critic that targets x(1), and so insufficiently optimistic as (6) changes. The blue, pink, and rust area depicts the tracking error of r to x (fux) from insufficient optimism, which yields linear regret.
4.1. Challenges and algorithm design
However, this is not the case. Intuitively, if the critic targets a rapidly changing T(1), the Bellman error with regard to the policy n (Pan) at the last update will not be close to the Bellman error with regard to (t),, Although the former is what the critic/ f(1m)) = f(t) targets, we evaluate the latter when considering a switch at time t. Therefore, the critic updates far more often when we target QT(() rather than Q"
4.2. Regret bound for NORA
as it tries to hit a moving target.
To control the switching cost with the framework of Xiong et al. (2023), we concern ourselves with function classes of low Da-type Bellman Eluder dimension (Jin et al. (021): Assumption 3 (Bounded Dtyt Bellman Eluder Di- mension). Let DA := {DamhhetH where Da (Ō(s.a)()) s S,a A}. That is. we only consider distri- butions that are Dirac deltas on single state-action pair. We assume that d == dRr(F, Da,1/vT) < x0.
Furthermore, this results in insufficient optimism. In Lemma| 7 we can only guarantee optimism with respect to the Bellman operator at the last critic update time tlatt elt)
(t)) fA 2 "TT 1- But we require f/ 2 Th." JA+1 At- tempting to work with this form of limited optimism results
<(f)
in the tracking error relative to x²" becoming
(1uxe) Re- [1 (5, ()(()))))))))))) T/h =1 (116))]
This can be weakened to the more general &2 eluder condi- tion of (Xiong et al. (023) with nothing more than a change in notation. However, we present our results in the Bell- man eluder dimension framework for familiarity and ease of presentation. We now show the following:
incurring linear regret. This is the shaded area in Figure I
A way forward. Having the critic target Q* instead of Q=") provides a solution. This ensures sufficient optimism, as we show in Lemma 14 that f(()) TTT (0) sh+1- Fur- thermore, we do not need to control log. N =())) as max, Qh+1 (s, a) is contraction and it suffices to control log (p), which is often approximately (op)
Theorem 2 (Regret Bound for NORA). Algorithm achieves the following regret with probability at least 8:
Reg(T) = ( log A + +/BIITSEC(F,11.7))
+ +dH log T
However, this introduces an additional term we need to control the deviation of the current policy z!() from the greedy policy (t))) depicted as the pink area in Figure 1
where 3 = O(lg ( This implies a sample complexity (ignoring lower order terms) of
This term is difficult to control, as T0 changes with every critic update, and the actor requires sufficient time to eatch
N 2 (dH' log |Alg/ + H' (T,TEC(FF
6

---

Actor-Critics Can Achieve Optimal Sample Efficiency
Algorithm 2 No-regret Optimistic Rare-switching Actor- critic (NORA)
ing Q" yields sufficient optimism to assert that S/ T (2) p(t) JA+1 in Lemma 14 and we argue that second term for the negative Bellman error under x² is non- positive in Lemma 10 The third term is bounded by V3H II, T) via a standard argument from Xie ct al. (022) in Lemma 11
1: Input: Function class F.
2: Initialize: F(O) + F,
@( @(ydlog log |AH- h t 0, vh E [H]. n
(1)) & 1, confidence width 3 = (
3: for episode t = 1,2..... do
Instead of directly bounding the first and fourth terms right away, consider the critic switch times ,,,,., Lx. Then,
4: Set (s. a) E mngmajjerta Sn (8, a) Vs, a. h.
5: Play policy I(() for one episode, obtain trajectory, update dataset D(²
tx+1
H
Σ (0))
= (112(11))))
6: if (19) sh+1) 2 ming,en ch (he (hh 11
+1h=1
3 for some h then
is bounded by O(1H - + + H log |AI/ H2) in Lemma 12 We exploit the fact that we reset the policy after the episode is collected at every lx in doing so. We then do the same for the other term in Lemma 9
7: Compute confidence set Fl!:
F() + {1EF: 1h (Jh. Ju+1))
min c (fhofo+1) $ H2 1P REF
To conclude, bound the number of critic updates in Lemma 13 13 dHf log T with the techniques of Xiong et al. (023) Summing over all L,, 4x lets us bound the first and fourth terms by vdH1 log I log [A| + dH log I by our choice of learning rate. We modify the learning rate ") = O /olg 7 log (AH--T-T to mitigate the switch cost, shaving off factor of dH log T in the final sample complexity. Putting everything together yields the result.
(h (f,f))
2
Σ
[((s,a) r max ('s' (6'' (d) a'EA
8:
Reset policy (1) X
Set time + t, updates + 1 + 1.
9:
updates
10:
else
11: Set 12((0)
"updates + v((11) F(t) + F(1-1). updaaess
12: end if
Quality of the regret bound. Even compared to the "good case" for Algorithm iin Corollary [ Iggoritmm@requieee only dH log T more samples to learn an c-optimal policy, This is exactly the same as the switch cost, in line with what Cassel and Rosenberg (202)) observe for linear MDPs.
13: Update Th ((+11) x (t) (als) (xp())) (s, (s)
14:
end for
Proof. We provide a proof sketch here, and defer the full proof to Appendix B By Lemma 8] we have slightly different regret decomposition than usual:
The Bellman eluder dimension can scale poorly with T (e.g.. dFF(FF Da, 1/ l/VT)= R(vT) in rare cases), and so we primarily rely the SEC Xie et al. (0022). which is always at most Oddlo T) though our result still depends on d due to the switch cost. Still, function classes with low Bellman eluder dimension are ubiquitous, and so Algorithm 2 achieves /T regret on a large class of problems including linear and kernel MDPs (Jin et al., 202I). We can use the weaker fg eluder condition of (Xiong et al. 2023) with only a change in notation, but we present our results in the language of the Bellman eluder dimension for clarity.
Reg(T")
T
H
[1 (sho ) m (. sh) - 2h (- (1)s))
E.
Tracking error of (0) want nt, bounded by mirror ascont arguments.
T
( -
(2) (Bh: an)
E
The
A=1
Nogative Bollman error undernder "," bounded by optimism.
Comparison with other work. The only other method claiming VT regret with policy optimization and general function approximation is Zhou et al. (2023). However, they allow themselves to collect Q(TT) samples at every timestep without incurring any additional regret. This incurs a sample complexity of 1/c², while Algorithm [ enjoys 1/e² gurarantee in comparison. Their regret bound is not sublinear in the more common setup where this sampling contributes to the regret. Liu et al. (2023b) achieves 1/c² complexity with batched critic updates but do not quantify the potential growth of the policy class.
H
[ Thish11) ()) (sh, an)
E
Bellman error under current policy occupancy, bounded by critic error.
(c) (s ) (+1s)) 1 (1s))
(=
Tracking errer of (f) weL. of (0) bounded by mirror ascent and policy resets.
We take care of the second and third terms first. Target-
7

---

Actor-Critics Can Achieve Optimal Sample Efficiencc
Extension to other policy updates. We are able to accom- modate other policy optimization updates other than the multiplicative weights update, if they satisfy the following:
When Sa (F, IT) is the single-poliey concentrability coef- ficient defined in Definition 4 these enjoy the following guarantees (with proof deferred to Appendix D.I::
Theorem 3. Algorithms 3 and achieve an ad- ditional regret of Olv B H of (F. FIT.IITT// and
Corollary 2. If there exists some policy optimization oracle x04+1) t- (O( f(0), ,n), and some OPT", OPT such
O( 3 ca (F)T2/Nous respectively over Algorithms and 2 where 8 = O (log (HTNE,
that En.e E. (s, (T (18)) T/22 (+1s)) OPT", (15 (s, ), Th (-|s) - ( (+ss) & OPT Ene Bgzc [
- (log (HTT:N.Tx(O/TT/0))
then Algorithm with this updete obtains a regret of
Reg(T) O (v /HHTTSEC(FF,,, T) + OPT* + OPT!
In exchange for omitting optimism, we incur an additional /BH (F)T2 etror term, which amounts to vT regret as long as Non = (((T). This shows that the prov- able efficiency achieved without optimism by hybrid FQI- type methods (Song et al. 2023) also extends to actor-critic methods - resolving the issue within Zhou et al. (2023) of needing collect ((T) samples at every timestep t. We
4.3. Further comments on the design of NORA
Targeting Q' We are not the only ones who consider critic that targets Q" instead of Qa(") For example, Crites and Barto (994)) propose an actor-critic algorithm that mim- ies Q-learning via critic that targets Q", Similarly, popular methods like DDPG (Lillicrap et al., 2019) and TD3 (Fu- 2018) alternately update a deterministic pol- icy approximately maximizing its own Q-function estimate (thus indirectly targeting Q"), combined with stochastic exploration to track the evolving policy.
achieve sample complexity of 1/c², in contrast to the 1/c8
sample complexity Zhou et al. (2023)
jimoto et al.
5.2. Sample efficiency gains with hybrid RL
The extension, found in Algorithm 5 appends the offline data to the online data and minimizes the TD error over the combined dataset when constructing the confidence sets, This yields the following guarantee:
Similarity to deep deterministic policy gradients (DDPG). Algorithm shares similarities with DDPG (Lil- licrap et al., 2019), which alternates updates between deterministic policy (*) (s) RV arg max, f(0 (s, (s
Theorem (Hybrid RI. Regret Bound for NORA), Let Yott, Non be an arbitrary partition over X' = S x A x [H]. Algorithm 5 satisfies with probability at least 5:
a) and a critic minimizing the TD error, using slowly updated targets reminiscent of our rare- sare-switching updates. DDPG explores via Gaussian perturbations around its deterministic policy, indirectly targeting Q* This suggests that DDPG and its successor TD3 (Fujimoto et al. 2018) may be useful back- bones for adapting algorithmic insights garnered from the design and analysis of Algorithm 2 for practical RI.
Reg( (Non) = O ( inn
(VBHACoH(FLa) Xx Non /oot
Kon
11,7) + VdHls log A1))
+V
where 3 C'log (H.NN,,T(L/N)))) for some constant C.N = Nott Non. 1x 11 1x,,, are indicator variables for whether s,a E Xoof or Xon and con (Flx xxax) is the partial all-policy concentrability coefficient Tan and Xu 2024).
5. Extension to Hybrid RL
Here, we demonstrate two benefits of hybrid offline-online data in actor-critic algorithms. With optimism, these algo- rithms achieve improved sample efficiency. Alternatively, offline data enables one to omit optimism, simplifying im- plementation and improving computational efficiency.
We defer the proof Appendix D.3 Broadly, the critic error splits into offline and online terms, bounded by of- fline coverage and online exploration respectively. Algo- rithm 5 is completely unaware of the partition, but the regret bound optimizes over all partitions of the state- action space. With sufficient high-quality offline data, the regret is approximately N,,
5.1. Computational efficiency through hybrid RL
II, T) + / d.. log AA for some small Xon. yielding improve- ments over Theorem 2 This shows that actor-critic methods can benefit from hybrid data, achieving the provable gains in sample efficiency compared to offline-only and online-only learning observed by Li al. (2023) Tan et al. (2024)
Song et al. 22023; : Amortila et al. (0224): ; Zhou et al. (0023 show hybrid RL can avoid optimism altogether given of-
fline data with sufficient coverage. Following this idea,
provide non-optimistic variants of Algorithms [ [ndd]] 2 in Algorithms 3 and 4 These achieve vT regret without optimizing over confidence set, detailed in Appendix C
6. Numerical experiments
Thiis provides insight on why DDPG/TD3 are more sample-
efficient than on-policy PPO. Algorithm 2 needs 1/c² samples, while on-policy sampling needs at least 1/e" [Liu et al. 2023b)
We provide two numerical experiments to empirically verify our findings, with details deferred to Appendix H
8

---

Atto-Crittis Can Achieve Optimal Sample Efficiency
Median Irs-Fpisodd Reward Online Timestops
Aigrtten Mlpriher2
300
0.4
300
000
sbp
1000
-00
Cumulative Regret
600
24 36 Deg
14
26
34
13002
5003
Figure 3. Comparison of Cal-QL (Nakamoto et al. 2023). Alg. 1H. and Alg. 2H1 the antmaze tettmazz--ediiu--divvie
task. Alg. 2H outperforms both Cal-QL and Alg. 1H, suggesting that hybrid RL enables efficient exploration without pessimism. Eval- uation plots show offline pretraining in the first 1000 steps. All plots are exponentially smoothed.
2003
6
Orhre
Figure 2. Per-episode reward and cumulative regret of Algorithms I and 2, compared to a rare-switching version of LSVI-UCB (Jin et al. 2019) on a linear MDP tetris task. Algorithm outperforms LSVI-UCB, and Alg. 2 catches up after some time. though all achieve v V regret. Results averaged over 30 trials.
7. Conclusions and Future Work
We resolve an open problem in the online RL literature by designing an actor-critic method in A with general function approximation that achieves 1/e² (and matching VT regret) without making any reachability or coverage assumptions. This was achieved through several key in- gredients in the algorithm design. By (1) performing opti- mistic exploration, (2) learning critic off-policy without throwing away any data, (3) having the critic target Q" instead of Qm(() to ensure sufficient optimism and enable rart-switching critic updates, and (4) performing policy re- sets to control the deviation of the current policy from the greedy policy, we achieve the desired result in Theorem 2
Optimism in linear MDPs. The first experiment exam- ines Algorithms T and 2 in linear MDP setting, in or- der to validate if they indeed achieve vT regret in prac- tice. Accordingly, we implement optimism with LSVI-UCB bonuses (Jin et al. 2019) instead of global optimism as in GOLF. We compare our algorithms to a rare-switching" [T version of LSVI-UCB on linear MDP tetris task (Tan et al. 2024 Tan and Xu 2024). The condition required for Algo- rithm 1 to work holds here, as we do not clip the Q-function estimates. Figure shows that Algorithm [] (surprisingly) performs better than LSVI-UCB, and empirically illustrates that Algorithm
We resolve another open problem in hybrid RL with a non- optimistic, provably efficient actor-critic algorithm requiring Not 2 E I)dHI+ /e" offline samples. Together with Theorem 4 this shows hybrid RL enables sample efficiency via optimism and computational efficiency without it.
2 also achieves vT regret even though it performs slightly worse than LSVI-UCB.
We compare variants of Algorithms 3 4nd that we call Algorithms IH and 2H respectively, to Cal-QL (Nakamoto et al. 2023). The differences are follows. Algorithms 1H and 2H employ offline pretraining of both the actor and the critic, and the actor employs the soft actor-critic (SAC) update from (Haamoja et al.) 2018)) Additionally, Algorithm 2H omits the policy resets. Like Cal-QL, and unlike Algorithm IH, Algorithm 2H takes maximum over 10 randomly sampled actions from the policy to enhance exploration approximately targeting n..
Deep hybrid RL.
While Algorithm 2 is generally computationally inefficient, the insights gained are promising for empirical applications. Optimism, crucial for strategic exploration, can be imple- mented via linear bonuses (Agarwal et al., 2020), count- based methods (Martin et al. 2017), randomized value func- tions (Osband et al. 2019), or random latent exploration MMahankali et al. 2024). An off-policy critic can lever- age DDQN (van Hasselt et al., 2015), updating only on high TD error. Optimistic TD3 (Fujimoto et al. 2018) with rare-switching updates and resets is particularly promising. Further numerical experiments would be valuable.
Algorithm 2H outperforms Cal-QL, which in turn slightly outperforms A Algorithm IH. These results suggest that Al- gorithms IH and 2H remain highly competitive, and may perform just as well as the state of the art in hybrid RL (Cal-QL)- - even without the use of pessimism. Our results support our theoretical findings that hybrid RL allows for computationally efficient actor-critic algorithms.
One might incorporate rarely-updated bonus functions (Agarwal et al. [022 Zhao et al.) 2023), updating the base critic each episode. This may achieve optimism without targeting Q' if sums of Q-functions approximate scaled Q-functions. Extending He et al. (2023) to study minimax- optimal policy optimization in linear MDPs as Wu et al. (002)) did for tabular MDPs, is another valuable direction.
Immleemenedd with the doubling determinant method used in He al. 2023). This incurs at most dH log T switching cost.

---

Actor-Critics Can Achieve Optimal Sample Efficiency
Impact Statement
Crites, R. and Barto, A. (1994). An actor/critic algorithm
that is equivalent q-learning- In Tesauro, G., Touretzky, D., and Leen, T., editors, Advances in Neural Information Processing Systems, volume 7. MIT Press.
This paper presents work whose goal is to advance the field of Machine Learning. There are many potential societal consequences of our work, none which feel must be specifically highlighted here.
Efroni, Y., Shani, L.,, Rosenberg, A., and Mannor, S. (2020). Optimistic policy optimization with bandit feedback.
Acknowledgements
Fujimoto, S., van Hoof, H., and Meger, D. (2018), Address- ing function approximation error in actor-critic methods.
The authors are supported in part by the NSF grants CCF-2106778, CCF-2418156 and CAREER award DMS- 2143215.
Gaur, M., Bedi, A. S., Wang, D., and Aggarwal, V. (2024). Closing the gap: Achieving global convergence (last iter- ate) of actor-critic under markovian sampling with neural network parametrization.
References
Yadkoi,,adkori, Y., Bartlett, P., Bhatia, K., Lazic, N., Szepesvari, C., and Weisz, G. (2019). POLITEX: Re- gret bounds for policy iteration using expert prediction. In Chaudhuri, K. and Salakhutdinov, R., editors, Proceed- ings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learn- ing Research, pages 3692-3702. PMLR.
Haarnoja, T., Zhou, A., Abbeel, P., and Levine, S. (2018). Soft actor-critic: Off-policy maximum entropy deep rein- forcement learning with stochastic actor.
He, J., Zhao, H., Zhou, D., and Gu, Q. (2023). Nearly min- imax optimal reinforcement learning for linear markov decision processes.
Agarwal, A., Henaff, M., Kakade, S., and Sun, W. (2020). Pe-pg: Policy cover directed exploration for provable policy gradient learning.
Jiang, N., Krishnamurthy, A., Agarwal, A., Langford, J., and Schapire, R. E. (2016). Contextual decision processes with low bellman rank are pac-learnable.
Agarwal, A., Jin, Y., and Zhang, T. (2022). Vogl: Towards optimal regret in model-free rl with nonlinear function approximation.
Jin, C., Liu, Q., and Miryoosefi, S. (2021). Bellman eluder dimension: New rich classes of rl problems, and sample- efficient algorithms.
Agarwal, A., Kakade, S. M., Lee, J. D., and Mahajan, G. (2021). On the theory of policy gradient methods: Opti- mality, approximation, and distribution shift. Journal of Machine Learning Research, 22(98):1-76.
Jin, C., Yang. Z., Wang, Z., and Jordan, M. (2019). Prov- ably efficient reinforcement learning with linear function approximation.
Kakade, S. M. (2001). A natural policy gradient. In Diet- terich, T., Becker, S., and Ghahramani, Z., editors, Ad- vances in Neural Information Processing Systems, vol- ume 14. MIT Press.
Amortila, P., Foster, D. J., Jiang, N., Sekhari, A., and Xie, T. (2024). Harnessing density ratios for online reinforce- ment learning.
Bhandari, J. and Russo, D. (2022). Global optimality guar- antees for policy gradient methods.
Kumar, N., Agrawal, P., Ramponi, G., Levy, K. Y., and Mannor, S. (2024). Improved sample complexity for global convergence of actor-critic algorithms.
Cai, Q., Yang, Z., Jin, C., and Wang, Z. (2024). Provably efficient exploration in policy optimization.
Lan, G. (2022). Policy mirror descent for reinforcement learning: Linear convergence, new sampling complexity, and generalized problem classes.
Cassel, A. and Rosenberg, A. (2024). Warm-up free policy optimization: Improved regret linear markov decision processes.
Li, G., Wei, Y., Chi, Y., Gu, Y., and Chen, Y. (2021). Soft- max policy gradient methods can take exponential time converge. In Conference on Learning Theory, pages 3107-3110. PMLR.
Cen, S., Cheng, C., Chen, Y., Wei, Y., and Chi, Y. (2022). Fast global convergence of natural policy gradient meth- ods with entropy regularization. Operations Research, 70(4):2563-255 2578.
Li, G., Zhan, W., Lee, J. D., Chi, Y., and Chen, Y. (2023). Reward-agnostic fine-tuning: Provable statistical ben- efits of hybrid reinforcement learning. arXiv preprint arXiv:2305. 10282.
Chen, Z., Li, C. J., Yuan, A., Gu, Q. and Jordan, M. (2022). A general framework for sample-efficient func- tion approximation in reinforcement learning.
10

---

Actor-Critics Can Achieve Optimal Sample Efficiency
Lillicrap, T. P., Hunt, J. J., Pritzel, A., Heess, N., Erez, T., Tassa, Y., Silver, D., and Wierstra, D. (2019). Continuous control with deep reinforcement learning.
Schulman, Levine, S., Moritz, P., Jordan, M. I,, and Abheel, P. (2017). Trust region policy optimization.
Sherman, U., Cohen, A., Koren, T., and Mansour, Y. (2024). Rate-optimal policy optimization for linear markov deci- sion processes.
Liu, B., Cai, Q. Yang, Z.,, and Wang, Z. (2023a). Neural proximal/trust region policy optimization attains globally optimal policy.
Song, Y., Zhou, Y., Sekhari, A., Bagnell, J. A., Krishna- murthy, A., and Sun, W. (2023). Hybrid rl: Using both offline and online data can make rl efficient.
Liu, Q.. Weisz, G., György, A., Jin, C., and Szepesvári, C. (2023b). Optimistic natural policy gradient: simple efficient policy optimization framework for online rl.
Sutton, R. S. and Barto, A. G. (2018). Reinforcement Learn- ing: An Introduction. The MIT Press, second edition.
Mahankali, S., Hong, Z.-.., Sekhari, A., Rakhlin, A., and Agrawal, P. (2024). Random latent exploration for deep reinforcement learning.
Tan, K., Fan, W., and Wei, (2024). Hybrid reinforcement learning breaks sample size barriers in linear mdps. In Advances in Neural Information Processing Systems.
Martin, J., Sasikumar, S. N., Everitt, T., and Hutter, M. (2017). Count-based exploration in feature space for reinforcement learning.
Tan, K. and Xu, Z. (2024). A natural extension to online algorithms for hybrid RL with limited coverage. Rein- forcement Learning Journal, 1.
Mei, J., Xiao, C., Szepesvari, C., and Schuurmans, D. (2022). On the global convergence rates of softmax policy gradient methods.
van Hasselt, H., Guez, A., and Silver, D. (2015). Deep reinforcement learning with double q-learning.
Mnih, V., Badia, A. P., Mirza, M., Graves, A., Lillicrap, T. P., Harley, T., Silver, D., and Kavukcuoglu, K. (2016). Asynchronous methods for deep reinforcement learning.
Wagenmaker, A. and Pacchiano, A. (2023). Leveraging offline data in online reinforcement learning.
Munos, R. and Szepesvári, C. (2008). Finite-time bounds for fitted value iteration. Journal of Machine Learning Research, 9(77)8155-877
Wainwright, M. J. (2019). High-dimensional statistics: A non-asymptotic viewpoint, volume 48. Cambridge univer- sity press.
Nakamoto, M., Zhai, Y., Singh, A., Mark, M. S., Ma, Y., Finn, C., Kumar, A., and Levine, (2023). Cal-qi: Calibrated offline rl pre-training for efficient online fine- tuning.
Wu, T., Yang, Y., Zhong, H., Wang, L., Du S. S., and Jiao, J. (2022). Nearly optimal policy optimization with stable at any time guarantee.
Xiao, L. (2022). On the convergence rates of policy gradient methods.
Neu, G., Jonsson, A., and Gómez, V. (2017). A unified view of regularzzed markov decision processes.
Xie, T., Foster, D. J., Bai, Y., Jiang, N., and Kakade, S. M. (2022). The role of coverage in online reinforcement learning. arXiv preprint 1rX1v:2210.04157.
Osband, I., Roy, B. V., Russo, D., and Wen, Z. (2019). Deep exploration via randomized value functions.
Rajaraman, N., Yang, L. F., Jiao, J., and Ramachandran, K. (2020). Toward the fundamental limits of imitation learning.
Xiong, N., Wang, Z., and Yang, Z. (2023). A general frame- work for sequential decision-making under adaptivity constraints.
Rajeswaran, A., Kumar, V., Gupta, A., Vezzani, G., Schul- man, J.. Todorov, E., and Levine, S. (2017). Learn- ing complex dexterous manipulation with deep rein- forcement learning and demonstrations. arXiv preprint 17Xiv:1709.10087,
Yuan, R., Du, S. S., Gower, R. M., Lazaric, A., and Xiao, L. (2023). Linear convergence natural policy gradient methods with log- lin-linear policies.
Zanette, A., Cheng, C.-A., and Agarwal, A. (2021). Cau- tiously optimistic policy optimization and exploration with linear function approximation.
Rashidinejad, P., Zhu, B., Ma, C., Jiao, J., and Russell, S. (2023). Bridging offiine reinforcement learning and imitation learning: A tale of pessimism.
Zhan, W., Huang, B., Huang, A., Jiang, N., and Lee, J. D. (2022). Offline reinforcement learning with realizability and single-polic concentrability.
Ren, J., Swamy, G., Wu, Z. S., Bagnell, J. A., and Choud- hury, S. (2024). Hybrid inverse reinforcement learning.

---

Actor-Critics Can Achieve Optimal Sample Efficiency
Zhao, H., He, J., and Gu, Q. (2023). A nearly optimal and low-switching algorithm for reinforcement learning with general function approximation.
Zhong, H., Xiong, W., Zheng. S., Wang, L., Wang. Z., Yang, Z., and Zhang. T. (2022). Gec: A unified framework for interactive decision making in mdp. pomdp, and beyond. arXiv preprint arXiv:2211.0196.
Zhong, H. and Zhang, (2023). theoretical analysis of optimistic proximal policy optimization in linear markov decision processes.
Zhou, Y., Sekhari, A., Song, Y., and Sun, W. (2023). Offline data enhanced on-policy policy gradient with provable guarantees.
12

---

Actor-Critics Can Achieve Optimal Sample Efficiency
Contents
Introduction
Problem Setting
Optimistic Actor-Critics The Easy Case
Optimistic Actor-Critics The Hard Case
5
Challenges and algorithm design
6
4.2
Regret bound for NORA
4.3
Further comments on the design of NORA
Extension to Hybrid RL
Computational efficiency through hybrid RL
5.2
Sample efficiency gains with hybrid RL
8
Numerical experiments
8
Conclusions and Future Work
Proofs for Theorem
15
Regret decomposition
15
A.2
Bounding the tracking error
15
A.3
Asserting optimism
17
A.4
Bounding the Bellman error under the learned policies
18
A.5
Auxiliary lemmas
19
A.5.1
Showing optimism for crities targeting Q
19
A.5.2
Bound on covering number of value function class (Proof of Lemma
21
A.5.3
Closure under truncated sums limits policy class growth (Proof of Lemma
21
Proofs for Theorem
22
B.
Regret decomposition
22
B Bounding the tracking error
23
B.3
Asserting optimism
25
B.4
Bounding the Bellman error under the learned policies
25
B.5
Auxiliary lemmas
28
B.5.1
Bound on rare-switching update frequency
28
B.5.2
Showing optimism for crities targeting Q"
30
13

---

Actor-Critics Can Achieve Optimal Sample Efficiency
Extension of Algorithm 2 to hybrid RL
31
D Proofs for Regret Guarantees of Hybrid RL
32
D.1 Proots for Theorem
Algorithm
32
D.2 Proofs for Theorem
A Agorithm
34
D.3 Proofs for 4
36
D.4 Auxiliary lemmas
37
Concentration of the Empirical Loss
38
What If We Target Qa Instead of Q'?
41
But can we bound the number of critic updates?
41
F2
But can we control the negative Bellman error?
43
Miscellancous Lemmas
45
Further Experiment Details
46
14

---

Actor-Critics Can Achieve Optimal Sample Efficiency
A. Proofs for Theorem 1
prove a regret bound for Algorithm| There. This algorithm achieves sublinear regret only when the covering number of the function class does not increase linearly with the number of critic updates.
A.1. Regret decomposition
We first work with the following regret decomposition below, This is the same regret decomposition as that of of et al. (2024) and Zhong and Zhang (2023). and we provide the proof for completeness.
Lemma (Regret Decomposition For Q" -Targggtnn Actor-Critics), The regret at time T yields the following decomposition
(shy , 8h)) -h (.1 saa) (1h
ΣΣ F [11 -Tw" -T''shh shit) (8h, an) h=1
Reg(7) (T)
T
Ex) [1h
- -Th
Th fhit1) (sh, an)
1=1
Proof. By adding and subtracting
(s
(2) (1) (s( we obtain
T
(T) Σ
(5 17rl0 (s)
T (5 - (- + Σ (10 Σ
r
(s7))
(3)
We can now apply the value difference lemma/generalized policy difference lemma in Lemma 23 Cai et al. et al. 2020) with f(t) as the Q-function, n' = TT, and π = 7(1) to find that
2024 Efroni
T
( (9
ΣΣnn Ex (1 (sh, , (. 8n) mh (6) (. (sn))
Σ>>,,... Ex- [1120 Th 1nf1)) (on, an)
(4)
Another application of Lemma 23 with n' (()) and with f()) as the Q-function yields
Σ (1) (5)
(0())) Vir( (0(1))
T
H
T H +
Eitt (11a)) (t)) (sh, -)
,,m (1)
sn)
Th
(8) (-1 sh))
[1 Th" s1.))) (sh, an)
1=11
I=
h=1
B [1 -Th" s (sh, an)
(5)
1=1 h=1
Plugging 4
and 5p into
3 concludes the proof.
A.2. Bounding the tracking error
The first term is bounded by / H- [A], as we see in the following lemma. This lemma the standard mirror descent regret bound, and is similar argument to lemmas found in Liu et al. (2023b) and Cai al. 2024).
15

---

Actor-Critics Can Achieve Optimal Sample Efficiency
Lemma (Mirror Descent Tracking Error for Algorithm D.. Let (11) and consider updating policies with respect to of Q-function estimates f()), m. f(T) by
1 (-15') exp(nnnti(ss
(1)
(++ " #k+1 (115)
= =-- (+t1(+ss)) exp(nfh4116
(6)
Ened " "ht1 (als') exp(n (
(2)
The tracking enror with respect the optimal policy is then bounded by:
H (1h (sh, . ( st)) Th (1) (- (1sh)) s SnH +
H log (A]
E
n
Proof. Rearranging 6 yields
n (8'.)) = llo 7 + log hh1 (-1s') log (1)
(2+1)
where log Z is
log 2 = loo
Σ aEd
Th
(2) ( exp(nthiiieee exp(ntiit((('
We now bound, noting that EoEA ( (Th+1(118')
((++)((15))) (15*)) 0, that
"h+1
(nthi (8/, ()) TH x (.18) - m (+
= (log Z + log #+tl
(e+1) (-15)) - log n (-18)) (-11)) - *n+1 (((5))
= loo x m/ (1+1)
(-1s') - log (1) / (-15'), th (-1s') x/41 (-1s)) = KL (+h+1
|| T 1 (-15)) - KL T Thtz (++1(1166) || (1+1) (116)) - KL
(Th+1 ( || (0) m (7)
where the last line follows directly from Lemma 24 by setting क == Mh11 (-18"), mi = =mpt1(11) and के =m (1) a result, we can bound the desired inner product as follows,
(t+1)
= (115).
As
(nthiilss ()),))))))))))))))) 1
m- (118') ( (1s))
( (5/ ()), (-16) - #ht1 ((-1)) (116))
=1/6"1166) - (n (. (1+1)) =((+t)((ss)) (-151)
(1)
< KL (-15)) || ( - KL T (-1))) ll m (++")(11)) - KL
-KL (m(tt)) (-16/) || T -
(1)
+ nill (1-1) (-15)) (+1s))l)
(8)
where the last line follows directly from Summing up the inner product bounded in (8), we derive that
H Ey
(1 ). (-1()))) (000 =
T
Ex (n/hi (8', 1 - x(0
1= 1=1
KL 1 (2) (115)) - KL T (:15') 11 Th41
(ttt2((())) (-1s))
(t+1)
17
A=
KL
Tht1 (+|s)) ||
(+11) (++))
(10 (-1s)) + nH (++ (-1s/) - x00) -
(9)
16

---

Actor-Critics Can Achieve Optimal Sample Efficiency
Now apply Pinsker's inequality and note that
h-1 (15" 2
(++
| ( (-13)11))
(1)
(10)
and plugging
10
into (9)
yields that
T H
( (-1)) - -11)
Ex
h=1
E
KL (+1s)) || x - KLL (Th411115') || Tht1 (11s))
((+1)
1=1 h=1
-1|m - (- nH أー
(-1s") - - (-15)1l1) (++1) (-18²)
Σ
Ex
KI. KI. (T || (172(115)) KI. (+++))1))))))))) || *
- 12
(11)
A=1
where we use the fact that maxzER yields
{ (-x3/2+ n7² H2 2 in the last line. Continuing to simplify this expression
H Ex
KL. (1+1(116)) 11 1 (121(1 - KI. (#h+2(-15')) ||
(e+1) #+11 (116))
2//22/2 Ex-
"
t=1 h=1
H KL Th41(-15') || (1) =
KL (Th+ Th (-1s))
S/
7
h=1
H log |A|
S S
(12)
where the last inequality follows from the fact that the KL-divergence is non-negative as well as noting that (1) the uniform policy, so that the KL divergence can be bounded as
KL (115)))1') || (1) *=41(11)) = Σ th log (alss")
Σ
Th ( log म. / (als")
aEA
aEA
S Σ
(alss') log (1)
aEA
log |A].
(13)
A.3. Asserting optimism
Lemma (Negative Bellman Error, Algorithm D.. Within Algorithm 7
it holds that
T
H
T
H
((t))
Th
E
(Mtt))) The (it1)) - x 2 (+22(114422) + T
h=1
1=1 h=1
Proof. First, we decompose the negative bellman error as follows
T
T
T
H
Ex.
((())
Th
E
E
Th
Jh+1
T 1
1=1
1=1 h=1
1=1 hml
17

---

Actor-Critics Can Achieve Optimal Sample Efficiency
T
T
H
h
(()) J4+1
E
Th
((1)
h41
Th
(1-1)
Jo+1
p(()
t=
h=1
t=
h=
E
Th
Jh41
Th
shtt
(14)
(=1 h=1
Here, using the result from Lemma 7 that // 2 T-(0-1))"" Shit note that the first term is less than O. We employ Lemma
25 with 1 and 12 T to bound the second term by TT For the third term, note that
E, Thi Jht
Th "h" skia
[h(sn, an) + -ho (sn+1, Thti (9n+1)) - -Tassn, an) -hho (sn-1. Thi ((h1())
-x-h
B
(t(t) 11t1 (su+1. The (( (11) (sh+1 (1)
*ht1 (541(8411)
1=1 1=1
B
1/-1(115044 -ht -1 (1s44)))]
(t)
(15)
Replacing the last term in (14) with (15 concludes the proof.
A.4. Bounding the Bellman error under the learned policies
Lemma 6 (Bellman Error Under Policy Occupancy, Algorithm [.. Within Algorithm it holds that
H
ΣΣE, E [1h0 -To shet)) (sn, aw) VBH"TSEC(F,117 I1,T) S
with probability at least where B = e (log (TNNsTmI><(LTT)/
Proof. We first decompose the Bellman error
[115]
-Tr7'0 s1o (sn, (sn, and]
T H
T H
(1) [frtt] Thi T f/ll) (sh, ax)
+
E500))
[TT
sbt1 Th (
(()
Shtz) (sh: an)
[=1 1==1
1=1
h=1
E E2 (
(11a
Tht
(1-) s (sh, an) az))
+ +nHST
(16)
where the last line holds by Lemma will see that
25 We will further bound the first term by applying Cauchy-Schwarz inequality, and we
(1)) [11/0 -Tx 1 (sh an)
(5 The
(1-1) " p(1) 27
1/2
122 Σ(=1 B
T H
s
Σ
(1) [1 -Trr" ((t)) Sutt) (sh, [nh
(5 -Tr ()()
2
Emi 1=1
H2 v - By(0
18

---

Actor-Critics Can Achieve Optimal Sample Efficiency
Bx(t) (1 Thill
11 ((0)
) shtt)
T
H H
- -Th
[11
Trait- s ). (17)
Bx(()
- Byco (11 -Tr
(()
)21
H V
where the last step follows from Cauchy-Schwand inequality. Within the last inequality, the first term can be bounded by H times the SEC of Xie et al. (2022), by the very definition of the SEC Definition 2 The second term bounded by Lemma
14 where
+ log TGN (TN
Putting these bounds into (17) we obtain that
T ΣΣ
E (
(1)
Th Tha u fnt1) (sh. S S
33HTTSEC(F.177 II,
(18)
t=1
Plugging
into
we finally obtain that
m00 [1 Th
-T="" s (sh, an) S (3H +n
(19)
t=1 h=1
A.5. Auxiliary lemmas
A. SHOWING OPTIMISM FOR CRITICS TARGETING Q=
We prove the following lemma more generality than is needed for Algorithm accomodating critic updates that are rarer than in every episode, with the aim to use the more general result in future sections. This can be thought as an analogue of Lemma 15 in Xie al. 2022), which is also Lemmas 39 and 40 in Jin al. (202T).
Lemma 7 (Optimism and in sample error control for critics targeting Q=")). ). Let tias be the time of the last critic update With probability at least 1 - for all E [T],
before episode t. Consider critic targeting QT1)) as in Algorithm
have that for all h = 1..... H
(i) Th
((t) E Fh) and so ((1) 2 Th
(harr) e(t)
Jh+1
(1) 27 [11 -T 1utt )²} <H(P)))
(i))
E 201(6)
by choosing 3 = c1 (log HTN, (TT)) (p)//)) for some constant C1.
Proof. We note that it does not hold that Q" e (()), as our Bellman operator is given by the operator T (0 under policy (4) and not the greedy policy under (()), Furthermore, as we do not throw away samples not in the current batch as Liu et al. (203bb do, we do not enjoy the same conditional independence of dataset and next-step value functions. We therefore
take different approach, modifying the analysis of Xiong et al. (2023) to the policy gradient setting in order to do so.
By Lemma applied policy (()) for any h [H] and [T], we have with probability 1 1-6 that
0 $ ct( (1. (Th (TT, Th41
P (hi1) min ch (hhs s H²3.
(20)
f..
We construct the confidence sets only at timesteps tu where switches occur:
Ff Ml (ual)
{ fEF: F: -. Cfluee (tue)) (fr, fn+1)
c chturn (awi) (Thr fn+1) S 223 wh E 1m1)
min R.EFA
(21)
It must then follow that Th Th frtt E ((()) for any f E F and tg. Now, we want to establish that
Th" "se) Jhtl < sup fneF((uu
Sa (s) ,(())
(22)
19

---

Actor-Critics Can Achieve Optimal Sample Efficiency
Further recall that we have defined
Fllua) | FEF: ((ann)
L/ua) (Jr Ju+1) - min
( (sh fa+1) & H3B wh E (HT)
(
fiE
So we can apply Lemma 17 on Lust. h+r and xl0 to find that
0 S c/ (( (Tr (ten shit Shtr
min ReEn
c (fh: S H2
(23)
then holds that
Paad Th Jhtl E Fiuee and so T (ua
Sn (3,a) = -hh- f
Jutt
S sup
The second result can now be shown by Lemma 18 using similar argument to the proof of Theorem I in Xiong et al. (2023), which in turn takes inspiration from the proof's of Lemmas 39 and 40 in Jin et al. (2021). We elaborate accordingly. Consider two cases, one where we perform an update at episode / - and one where we do not. If we perform an update at episode / - 1, then by the construction of (T(11) must hold that
ch
ct--1, 1, D) (Jh Fitz)) min L 11 fEE
1y
(hh-thh
s H2B.
and by Lemma 17 it must also hold that
0 I ch
1, 11-1) (Th (Th(--)) (t)) (1itt)
min Ln EAEFA
((1-1,0(111)
(Bh 1133.
One can then see that
h
(1- 1,
(12
chhh
(
sh41 611
(t)
(24)
The same holds for the other case where we do not perform an update at episode t - 1. Observe that because we did not perform an update,
ch ((-1,7/(-11) (fi--1) s1i-11
(t
(Th ( S 51223.
min fiFF
Cn
From Lemma 17 it also holds that
c/ Thu 11-1)
Sh p((-1)
min c 11 E
( S H2B.
Putting the above two statements together and using that ((() = (1- again yields
c "1-1,- 1)
(10) (h9.shtt)) L/ 11 1)
Thp S s
(1)
c 11-11x (t-10 (5h (((-1) (((-1)) c/ ((1-1, (Tr" spt 1((-1) sh
< 2 3.
(25)
An application of Lemma 18 to both cases then yields in either case that
hh
(0)
T
10-1)
Snti) (5 (2 S SH2B,
(26)
and also that
(1 -To ") (1) )"
E
1htl)
< 7
(27)
20

---

Actor-Critics Can Achieve Optimal Sample Efficiency
A.5.2. BOUND ON COVERING NUMBER OF VALUE FUNCTION CLASS (PROOF LEMMA
The proof is similar that of Lemma B.2 in Zhong and Zhang 2023), but we strengthen the result show that the covering number increases only in the number of critic updates, policy updates. As in [Zhong and Zhang (2023). let
F(ta)
(166KTTTTT be minimal p²/ 111111KKHTTT of F((h) for all k. So for any я x exp(n E (t, 1-115h (()) with
14/16nK so Jh E ((t), there exists some ((() E FF(le)
((44)
p²
sup
(1)) (s, a) - P1. 1 (s.a)) -
for all i E [K]. H6T
8,0
then holds that
K Σ
sup 8,0
Σ
(4 li- 151 (11 (8.
(1: 11- 11
S
Σ 1=1
(4 4ا- (--1ssup (s, a) f(t)) (8,a) a)l
1=1
i=1
8,a
p²
7
sup
( (s, (8,a) - (s,a) 5
(28)
16H2
8,0
Now we invoke Lemma B.3 of Zhong and Zhang 2023). provided as Lemma
21 for completeness, to show that
K (4: 11-1) (s,
sup (+18)) x' (-1s)]1 2 sup 8,0
7 Σ (4 1, 1))
Σ
S P
(29)
2H
==1
then holds that
Ng (0/2H) S II geo HT)
(30)
The bound for (A(p/2H) follows from discretizing the action space A via covering number argument, and observing that the covering number of an N A dimmeniiiii probability distribution is on the order of (
A.5.3. CLOSURE UNDER TRUNCATED SUMS LIMITS POLICY CLASS GROWTH (PROOF OF LEMMA 2
Let F22 1/160T be minimal p² H -
nnet of F. Then, for all fn F, there exists some fr E F F/2/16GTH2 such that
Ø²
sup [/,(,, a) - Jn (8) S
16
As F is closed under truncated sums, it then holds that there exists some f' E F such that
T
T
Jh (s, a) - Σ a)) = sup s.a
m (s, H) - 7 Σ fa(s,a)
sup 8.a
7
7
1=1
sup
S 16H
(31)
8,0
The result then follows from Lemma 20 and Lemma 21
That is, Lemma 21 shows that
T ( (s, a) 7 Σ
sup (1=-ss - 7' (-1s) S 2,
sup 8.a
70 (s, 0)
S p
(32)
2H
1=1
it then holds that and the result directly follows from Lemma 20
N (mmn:///22 S Nx
(33)
21

---

Actor-Critics Can Achieve Optimal Sample Efficiency
B. Proofs for Theorem
2
Recall the motivation for this solution:
1. Optimism allows one to perform strategic exploration, addressing the issue of exploration vs. exploitation, and allowing us to avoid making reachability or coverage assumptions.
2. Off-policy learning avoids throwing away any samples, ensuring that no samples are wasted.
3. Do rare-switching critic updates work? A-priori, introducing rare-switching critic updates as in Xiong et al. (2023) offers an appealing solution to the covering number issuc. However, the Bellman operator with respect to n (*) has a very limited form of optimism. Furthermore, is difficult to control the number of rare-switching updates in the context of general function approximation, where we make an update when the Bellman error with respect to the current policy is large, as the current policy keeps changing and so we track a moving target.
4. Letting the critic target Q" and not Q" ensures sufficient optimism, the Bellman operator is now the same at every iteration. Further, as the critic targets Q", we do not need to control log (gg.N(TTy=>() as the Bellman operator for the greedy policy is a contraction.
5. Rare-switching critic updates now work. However, this introduces an additional term, where we need to bound the deviation of the current policy from its target, the greedy policy with regard to the current critic. Re-introducing rare-switching critic updates resolves this, as now we allow the actor sufficient time to catch up to the critic updates. Controlling the number of critic updates is not an issue when the critic targets Q", as the Bellman operator is now the same every iteration. This is reminiscent of the delayed target Q-function trick common in deep RI. (Lillicrap et al.) 2019 Fujimoto et al. 2018).
6. Policy resets. However, going through the mirror descent proof to control the additional error results in an additional term bounded by Eker log(1 (4+). This term can be controlled by resetting the policy to the uniform policy upon every critic update. As critic updates are rare, on the order of dH log the additional error incurred is very small. This trick was adopted independently by Cassel and Rosenberg (2024) for the same reason.
7. Increased learning rate. We increase the learning rate accordingly by a factor of /dH log T, exactly the square root of the number of critic updates/policy resets. This done mitigate the increase in regret incurred by the policy resets by factor of / HJH log T, This can be seen as making more aggressive updates to make up for the lost ground due policy resets when the critic makes rare but large update.
Given the above, we now in position continue analysis below.
B.1. Regret decomposition
We employ the following regret decomposition below. This is slightly different regret decomposition than that of Ca et al. (2024) and /Zong and Zhang 2202)), our critic targets Q" Lemma 8 (Regret Decomposition For Q* -Targeiing Actor-Critics).
T
T
H
Reg(T)= 1=1 h=1
=
Ex-
(1h0 (sh, "), o (: |8h) Th (1) (. (11n))]]
- Shti) (sh, ax))
TT
1=1
h=1
H
T
[1 -Tns((ht) (sh, and + Σ M
B
(1 -), (-11011) = (118h+z))
, . (4) (s(9)), we obtain
Proof. By adding and subtracting
T
Reg( (T) =
Σ
(1)) - Vir(0) (s19)
1=1
T
Σ - ((
+ 3Σ
(o 1m (=(0')))) (s1))
(34)
m=1
22

---

Actor-Critics Can Achieve Optimal Sample Efficiency
To further decompose the two terms in (34), we apply the value difference lemma/generalized policy difference lemma in
Lemma 23 can written as
Cai et al. 2024 Efroni et al. 2020 with f() as the Q-function, x' n,, and x+() to find that the first term
(s())
( 1)
H
Ex [ ( (shr-) Th (. sh) - m/ (-1 [1ss)]]
ΣΣ Bx [ Th Shitt) (sh. an)
(35)
t=
Another application of Lemma 23 with π = T = =7() and with f()) as the Q-function yields
Σ 11) (5f
(of VI (8)))
E (1)
(5h (shs) :) (1 sn)) T(0 (-1 (111s)))
+ Σ Σ
B,0
[(1
Th (1 s10) (11))1)))
(sp, an)
A=1
T
The slet)) (sh, an)
(36)
t=1
k=1
We now need to relate the Bellman operator with respect to the current policy T to the Bellman operator Tr. Observe that
Exit)
[1Fh]
Th
T slits) (sh, an)
T H1
T H
E Ex
-TwShi)) (shs and]
+
( (Tnn - Th"" Th""") smh.)) (sh, an)
(37)
t=1
h=1
1=1
h=1
We further decompose the second term in the following way
(
The Sh+1) (sh, an) (n an) + s14 (sh+1, 7I The (+t rh (sh, an) an)) -hi
((0)
= Ex10
(sht1, * (
= -E,00)
g(()) sht1 18441, Th+ (sh+1) 1 8ht1, T (1)
/ Th (8)-1)
(1441 (5h-1: Th (())
(-19)+1) (1) (-1 (-1s+t)))
(38)
Replacing the original terms in by (35). 37 and 38 concludes the proof.
Each term within the regret decomposition is dealt with differently. We bound the first term via the standard mirror descent analysis, the second term with optimism. the third term with the GOLF regret decomposition and the SEC of Xie al.) (2022). and the fourth term via modified mirror descent analysis.
The attentive reader will note that the Bellman enror is defined as f - Tf in our setup and that of Liu et al. (2023)), and Tf - f in that of Zhong and Zhang 2023).
B.2. Bounding the tracking error
Lemma (Mirror Descent Tracking Error for Algorithm 2. Let ty and 1,41 be switch times within Algoritim 2 where we use the convention that (ta) x 1 is post-policy reset and π. (1x12) o is pre-policy reset. The tracking error with respect to the optimal policy is then bounded by:
1 Σ
log LAI (1 (sh: :), T (11 (h) Th (. (1sss) I 2 t2)/2+ +
ΣE
Ex,
+ H²
n
+
23

---

Actor-Critics Can Achieve Optimal Sample Efficiency
Proof. Note that for any such that Es + St t++1 1, we do not reset the policy during these timesteps as the critic does not change, we have
(-1s') exp(ntnt (()
(s', exp(nnf(t(s('.))
(+ # A+t
(+1s')
=- 1 (+ss)) exp(nfhi1(5 1i (s
(39)
Eoed // (als)) exp(1) ( 1
Rearranging this yields
n (1) (5',)) = logg& Z + log t h+1 (-1s²) - log 1b+1 (-1s),,
(++2)
where log Z is
log 7 = llog
Σ MEE
T Tht mh (als') (xx())))s(((
(1)
We can now bound, noting that EoEA (11+)
-((+t)) *1+1 (115)) 0, that
Infifilss ,)), 1h+1 (-1s))
Th+1 (-15²)
(1+1)
= (log Z + log M1t1 (.15)) - log (t)
(++1)
n1t1 (-18 1s') ( - *ht1 (1151)
(1+1)
(log Aht1
(r+1) (((())())s))) (-1s)) - log Tog (1) (-15)), क (11s)) *h+1
(1+1) (11s))
KL (Th+2(11s") || T221(118) (116)) - KL (-14) || ग T (116))
(++2((116)) - KL (hh+ (1(')) (0) (1)))
(40)
where the last line follows from Lemma 24 with I (-1s', x2 =m (t)
T (+|s²) and Thit (+Is). So it must hold
that
(n (6..)) T 1-))((1)))))))) - (6) (1s))
(s/, ) The 1h (+411((155)) - ( 1 (s', 1 (1) (1f1(115)) Tht1 (c(ss((sss)
KL. ( (-1s') (1) f KI.
|| (442((16)) KI. (m/4H) (-15)) || [1
=//2((166)
(1)
+ H (t-11) (-16") (1) (1s'(1)
(41)
Summing up and h, we can then derive that
fv 1-1-1
Σ
ΣE,,
En.
(s
+1hm1
1 1-1-1
Σ Σ
Ex. (s', - x
(0)
11 1= h=1
1 H
1 Σ Σ
Bxx KI. (-++)-11s)) 11 (10 Kl. (Ti+ (-14) I| -
1= h=1
KL wht1
(1ss)) (-11(( (1| -22 (153(1))
(42)
Here, we apply Pinsker's inequality the last line of 42 it follows that
f-11-1 H
Σ Ex
[1 ()) (1ss)) 212 (1)
=ff2(1166)]
11==l
24

---

Actor-Critics Can Achieve Optimal Sample Efficiency
1++1 -1
Σ g-
KL
(++1(1155) ((ff((115)) KL 1 Th+1 (-15))
17 t=1
-11 -11 (-1s') - x + (:15)) - -1 (-1s'(1)))111
1 1 1
Σ Σ
B
KL Th+1 (-1s') x=22((115)) KL (- | (11s') 1ア - H 12
(43)
17 1=++11 1=1
where we use the fact that max
{-x2/2+ nH²) n1² /2 in the last line. Continuing simplify
43
yields
M 1
H
Σ
Σ
Er
-I *h+ (1161
(1)
1= h=1
1++1-1 H
KL mh 1h+1(118) (1/5)) |1 (8) (-((((11))) - KI. (Th+2(115') || #h+1 (-15))
((+1)
<
Σ
/2 Ex
11++1
H KL
Th+ (-15') || Th+1
(1 (-1s') KL ( (T)+)((s'") 11
(b2+1) Th+1 (-15²)
< (1H - 1
7
h=1
H log IA|
S 1 1
+ H?
(44)
7
where the last inequality follows from the fact that the KL-divergence is non-negative well as the policy reset of setting (tx) back to the uniform policy after the critic update. Note that we use the convention that Th. (tx) is after the reset, and (1x1) is before the reset. This means that Th
Th
exp(O) EaeA exp(1HH)
exp(ntfa) (s', exp(n!t)
exp(n)f
S Th+1 (-16')
A exp(nH)
Theeeexp(nfi (s', EacAexpil
|
and so we can conclude that
KL T (116) ||
Th+1
(2-11) " S log
((ttt)(-ss))) #h+1
s log |A| + +HH.
(45)
B.3. Asserting optimism Lemma 10 (Negative Bellman Error For Algorithm
Within Algorithm
we have that
T
Eg
(((
Th s4+1
0.
t=1 h=1
Proof. Applying Lemma we note that //0 2 Th" Sht The result then follows.
B.4. Bounding the Bellman error under the learned policies
We now turn our attention to the Bellman error with respect to Ta under the current policy's 's occupancy measure.
25

---

Actor-Critics Can Achieve Optimal Sample Efficiency
Lemma 11 (Sum of Bellman Errors Under Algorithm 2) under the occupancy measure of at ( can be bounded by:
Within Algorithm 2
the sum of Bellman errors with respect to T
T
Ex0 ((nh-Thhht) (sh, and) S V V3HT7EEC(E,1177)
where 3 @ (log (HTT):.))
Proof.
We can now perform the same Cauchy-Schwarz and change of measure argument in Xie al. (2022) to find that
H
Σ Bes [1
Thsltta (oh, an)
(
H
HP V E 2 ((6 }2]
1/2
1
(
11 1
- da 110% }2]
T H
10
H
H
E oo
H
1( E go
h=1
(46)
Within the last inequality, the first term can be bounded by H times the SEC of Xie et al. (0022) ), by Definition 2 The second term is bounded by Lemma I4 Therefore, (46) can be bounded as
T
H
[f -Thhhtt (sh, (sn.an) an) s /HSEC(F.IL.T) BHT S (BHTTSCC
B h=1
(47)
Lemma 12 (Greedy Policy Tracking Error For Algorithm 2. Let ba and f&+1 be switch times within Algorithm 2 where we use the convention that (t6)) x 1 is post-policy reset and 7 (le+1) * is pre-policy reset. The tracking error with respect to the greedy policy corresponding to the current critic is then bounded by:
4 Σ ΣE (1211166)))
(0) ((21(166)) S 11H1(1441
4x)/2
H log |A|
H²2
"
1
Proof. Again note that for any such that tx + +1sts tx+1, we do not reset the policy during these timesteps as the critic does not change. We therefore have
T22 (-1'') exxls'))xp(p)))) exp(pnff) (t)
(nfn+1 (s',.)
((+1) (116) h+1
= 2, (()) " (-|s') exp(n1 (1)
(48)
Ener Thtz (als') (als') exp(11 (
and rearranging this yields
(++1) log Z₁ log ग mh (-ls") log m 1 (-1s'),
(t)
where log Z, is
log 21 = log
Σ
T Th
(t)
(t) (alssaa)))e((iiit exp(ntiif((( = log π.
(I+1) T (-1s') - log ah+1 (-|s') + n (s', .-).
AEEA
Noting that Ened
(-))())))) 0 for any two policies n, T' 11, we can now bound (n The (:16") - (+16))
26

---

Actor-Critics Can Achieve Optimal Sample Efficiency
= log Z + log h+l (-15') - log log T (-15') p(0) (-1s - Tht1 (1s())
((+1)
= (log aht (11s)) - log x log 1 (-15)), m
((+1)
(-1s') - Thtz (11'))
= KL (Th (+16)) |I Th-1 (16')) KL Th+1 (-16') 11 Th+1
(4)
w (16')) - KL (Th+) (16)) 11 10 =221(11))
(49)
where the last line follows from Lemma 24
So it satisfies that
(nhhtilb' 1), Th - (1)
(1s))
= -nnfifi( (s)
1 1 (115) - x/+1 )15)) - (nshifiss (s', .)), (t1 ((4)))===#))((+++ (1s))
((tt))
S KL (1)42(11)) (115)) (2(2(11))) - KI. (110)
(-15') |I m
(15)) - KI. (mft) (-1s') || T (9772((15))
+ H | (-1s)) ( (1s'(l)
(50)
Sum up with and h, we can then derive
4+111
Σ
Σ
B
(S (. (aclss)-(fff) (22 (16111
1+41-1
dh (.) 12 =(22(166))
1 t= A=1
1++1-1
(TAfl(( |I + ((21((16))) - KI. (+14)(1)))) 1| Th1
B
KI.
1 1=++11==1
KL
Th+1
(+|s)) |I m (-s)) + n | | -
(51)
When applying Pinsker's inequality in the last line of (5T, we can show that
H
Σ
Σe
E
(e) (121(
1= +1 Am1
(4+1-1 1 H1
Σ
E (()
KL
p(0) (1b4)(-15)) 11 | ( KL (Th6)(116) Thtl (x+t)((1s)))
"1 Am 2
h=1
-11 (11 (-18²) - -T - (-Is |s))1| n (1 (+|s)) 1/2 --22(11
(52)
Here, we use the fact that max { + nHHx = 11² H and obtain that
-|| (1+ (-1s') - 1 (-1s n | (-1s") - - (4)
Tha (155)11 S 1//11//2.
We now continue through the following. Note that f((++1) (())())))))) ... f(tee1) due to rare-switching. With a direct calculation, we obtain that
4441-1 Σ B
KI.
( (-18/) |1 (2) (-15)) - KI. (-10)(110)) || #h41 (((PP((15))
11
1o41-1 1
KL T/-1 (-15") || कं (00 (12(())))) (1(=)))((1s)))
p(oxt))
KL (mpeitat
p(tz+1)) (-1s') || क / ((++1) (-1s')
17
t= +1
gleat1) (-15²) ||
T m (115') - KI. ( ( (+|s') || -
KL.
(T/+1
E (2)
(53)
7)
27

---

Actor-Critics Can Achieve Optimal Sample Efficiency
Furthermore, there exists some a² (5') for each s' such that
a" (s) = arg max (s', for all b + I st> & 14+1,
d'EA
hence that n/. (a'ls)
(a' arg max (n(s,a)). This yields
KL
Tht1
1 (-160) M+1
(1x (1ss)))))))))))))))))))))))))( KL
g(tk112 (-16") Th+1
Th+1 (-18²)
(fe+1) (-1s))
B
1
1
1
1)
- E (0))
1 1.log
Th+1
(1++1)
(ar (s)))ss))
1 log
(fu+1) #/+1
(a (s())s)))
Mh+1 (a* (s')15')
(f(-1)
- E
log
(54)
(fv+1) (s')ss))
"h41
For this term, we note that Th is back to the uniform policy after the critic update. Note that we use the convention that (bx) is before the reset, and Hh
(1++1) is after the reset. This means that
Th
exp(O)
(1x+t) (1x+))(-1s)= (-1s))
exp(nfifi(d'"" S EnExexp(ni) exp(nt/i120"'00) (6', EeEa exp(a) [
exp(nH)
exp(nH)
E.EA exp(n)f) S *h+1
A exp(n)))
and so can conclude that
KL The 11 T (9) (-15)) - KL (00) (-42)(1ss)) |1 (415)((15))
M+t1
E (1)
"
(=
(1x+1) (a" (8')l')
log
hh+
S
1
log
< < -log (A| + HH)-
(55)
hh+
(44
(a" (8'))=)))
"7
Th+1
(1++1) (s')))))
Therefore, obtain that
1 H
12+1-1 -1 H
H
Σ
Σ go
11 =122(1s/)
Σ
H /2)
(log |A4 + nH)
1= +1 hm
1=++1/mm
hm1
H log [A]
n1H
4x)/2 +
H
(56)
B.5. Auxiliary lemmas
B. BOUND ON RARE-SWITCHING UPDATE FREQUENCY
We bound the rare-switching update frequency via an argument similar to that Xiong et al. (202)).
Lemma 13 (Switching Costs). Consider a procedure where the critic is updated only when there exists some such that
c.0 (f(() (1) min REF.
1 (Ph 2 5/13..
This performs no more than Nupdatesh (T) S Oddoog(T) Q-function updates for each h E [H), and no more than N Nupdotes (T) < O(dH log(T)) Q-function updates in total.
Proof. To show this result, we control the number of switches induced by the Q-function class targeting x² by upper and lower bounding the cumulative squared Bellman error under the observed states and actions. Fix some h E [H] for now.
28

---

Actor-Critics Can Achieve Optimal Sample Efficiency
For simplicity, write Kn = Nupdatee,, & (T) for the total number of updates, and 11,bs--.,, 1un, h. the update times for S with to, O. By definition, at every tuc
( ,.
min claaa EFE
(Thohhtt 2 5113.
(57)
An application of Lemma 17 yields
0 - ch cltnnd
(Thflerr (ttma) shate))
min chimal (ParFittr)) - H2 REE
min chiua) ReF
(Fhr (hes)
2 (aain))
(ThehAt) (lbun))) -H2
clten)) (fhum))
(Trottta)) :hht1 2 4H2
Lhh
From the above, can obtain
C% lntlitt))
(fh (pllen) glleah)
.sht1 Lh
(Tnfhtt -s411
allaan) alle,a)
(Jh (flle-1a-1))
(llennat)) Lh
S (
Ln
Thiht1
plfe-ratt)
sfttl (lltraatt)
Sh
c
cle (Sha (fll--aat))
s/a sharuatt) + Elf clte-sih)
(Thshtt h+1 :14t1
(ll-aaat)
fh glenn (lbew)) - c(taa)) (Thiftti
h
clte 1,1) (Jhl iat!) plt unt!)) + cli 1mh
(Tusiits iut!)
sh )at!)))
h
2 4H - H²B = =3H23.
(58)
Therefore, for any & such that 1. < t S tu this argument and noting that fl ((fe-1,+11 yields
f((1)
(la.
fh
- c/t 1. 1itewn
(Thshel:s ((0) 2 332
(59)
An application of Lemma 19 while noting that (((e-11tt1)) (! = /
(Maca) leads
(1h Twshtt) (s) (0) (10))
(Fhhein) Tnilleei)) 2 (6) (s (())) 2H 3.
(60)
1
1
Now summing over all t1,h, yields
Σ ( Tntht1) 2 (5)
T
19
(0)
Σ
Ka
(1h -Tns(tt) (6% .a )
2 2(K, 1)H²3.
(61)
iitt
1.
By Lemma 14 we have that
Σ (1
- - -TTTh 9 (a < (
(62)
Invoking the squared distributional Bellman eluder dimension definition, as in Xiong et al. 2023). yields
Σ Jh T (8n (1) - OddI log T).
(63)
29

---

Actor-Critics Can Achieve Optimal Sample Efficiency
So have established that
T h - -TuPhith)) ) (5h", aa = O(dH2 Bog (5)²
2(KA -
- 1=1
(64)
The number of updates for each h must therefore be bounded
Kn d'oo' yielding Nswitch (T)) S dll log T.
B.5.2. SHOWING OPTIMISM FOR CRITICS TARGETING Q"
The following lemma applies Algorithms and 4 As Algorithm is optimistic, both properties apply to it, while only the second applies to Algorithm
Lemma 14 (Optimism and in-sample control for crities targeting Q*). With probability at least - 8, for all E [T].
we have that for all h l,..., H, an optimistic critic largeting Q" in the same way as defined in Algorithm Satorithm@achieee aachevees
Th (5) Jhtt E F.. and f 2 Th 5h+1 for all n
(i) Th
Similarly, critic targeting Q" as in Algorithms and accheves
t-1
2 )²} (0(333). (1 Th
(ii)
Σ
E gelos
by choosing 3 =1 c1 (log (D)))) for some constant ey.
Proof. By Lemma 17 applied to the greedy policy π t00 for any h E [H] and & E [T], we have with probability 1 8 that
5 th (Tn.hi1: (1f min
c/ (fh fh41) s H
(65)
R.F
We construct the confidence sets only at timesteps 4 where switches occur:
F(lune = - (( (frr fu+1) - min cl (Ph fu+1) S H&B wh (m]
fEF
RREF.
We now show the first result. As we defined f/() (s. = argmax,
fnE fh (s, a), for all m:
T (s) + E. [1if (d (ra(s,)) + Es
max f (s)) a')
a'EA 1i
(66)
We further note that Ts. Th. (s, S 1 (s) Tu Fellun) and by the definition of 1(0 (s,
The second result can now be shown using by Lemma 18 using similar argument to the proof of Theorem in Xiong et al. (2023), which in turn takes inspiration from the proofs of Lemmas 39 and 40 in Jin et al. (2021) We elaborate accordingly.
Consider two cases, one where we perform an update at episode /. - and one where we do not. If we perform an update at episode 1, then by the choice of f(() to be near-optimal (in fact, with Algorithm/ 4 hold that
is optimal and this zero) must
c((-1) 1)
(1) 11211) (
min (((-2) (Ih- & 5H?3 FEF,F
and by Lemma 17 it must also hold that
0 < -/ ((1)
(())
min ch ((1-1) (Ihs H23.. fe
30

---

Actor-Critics Can Achieve Optimal Sample Efficiency
One can then that
10 ( (Jh2 (iP.sht)) 1/(-1)
s22i 6H2
(67)
The same holds for the other case where we do not perform an update at episode / - 1. Observe that because we did not perform an update,
c (fh-1)) shttt)
min REFF
ch-11)
(Fh f S 5H23.
From Lemma 17 it also holds that
- (TuSh Th shit1"
ch-11) (fhs (fh- s S H²B.
min
f. E.F
Putting the above two statements together and using that f(t) f(1-1) again yields
<k- (1P. ch- (ThJh (1in ch (1h- (
((1-1) (Thih s14-11) s S6H2B. (68)
application of Lemma 18 both cases then yields in either case that
Tnifit)) (5)) a < 7H23,
(69)
and also that
E (0)) [1h
1ii9-Thii Thshit) )
(70)
C. Extension of Algorithm t hybrid RL
Before we proceed, it useful to introduce the single-policy concentrability coefficient tweaked from that of Zhan et al. (2022) and partial all-policy concentrability coefficient from Tan and Xu (2024):
Definition Single-Policy Concentrability Coefficient).
Eg- [fn Th 1n+1] AE(H) JEF xen E,, [[hn TØ" 1
Coft (Fr(F) = max sup En [fn Tnfn- hE(M] JEF [,,((Sh Tnsh+11)
Con (F, II = max sup sup
Definition 5 (Partial All-Policy Concentrability Coefficient). For a function class F and a partition on the state-action space X' S x A x [H] where we denote the offline and online partitions by Nall and Xoa. respectively, the partial all-policy concentrability coefficient is given by:
I1 Tafn+1) (.)) 1B..3 [I - Tn Twfnftnn (.,))x 112,00
Cofl (F1xa) max sup
JEF
where 1 X denotes the indicator variable for whether s, a,a Xon
We now present Algorithm Algorithm 4 and Algorithm 5 which the modified versions of Algorithm forr hybrid RL.
Algorithm 3 (NOAH-T) targets (1), and follows the very natural procedure of performing a critic update via Fitted Q- Evaluation (FQE) (Munos and Szepesvári] (0088) and an actor update in every episode. It therefore requires closure of the critic function class under truncated sums as in Definition to control the growth of the policy class as Lemma 2 A (NOAH-+), like NORA Algorithm 2 circumvents this by targeting '²" and performing rare-switching critic update. Both algorithms are fully off off-policy, utilizing offline data and all collected online data without throwing any away.
31

---

Actor-Critics Can Achieve Optimal Sample Efficiency
Algorithm 3 Non-Oppinn Von-Optimistic Actor-critic with Hybrid RL targeting π (*)) (NOAH-T)
1: Input: Function class
F.
2: Initialize: FF()) &- F. D t
0, vh [M) n (VVlo 2 x(1) x 1, confidence width
(log (
3: for episode ( 2,, do
4: Play policy (*) for one episode, obtain trajectory, update dataset D/y))
5: Compute critic f(++)) targeting (1)) via FQE:
/ arg mimiin c c(( Jn+1) for = 1,,,,,, 1,
/EF
Ln
() +
Σ
(0) (f(s,a) -r ('(s', " ( ())))
(san)))D Uuur
6: Update T (als) x Th (als) (x)(s))xp(nf""> (s)
7: end for
D. Proofs for Regret Guarantees of Hybrid RL
D.1. Proofs for Theorem 3
Algorithm
We start with the same regret decomposition as in Lemma 3
T
RTg(T)) = Σ
(v(()( - Vi (s{))
1=1
(11h) (Shr ,), 1 (.1 (1)))) - x/ (. sn))
>ΣΣ E, [1
-Ti" s1i11) (sh, an)
E
1=1
1=1
1=1 h=1
T
- shtt1) (oh,
(n)) an)
(71)
t=1 h=1
We control the first term with the same argument as Theorem by using Lemma 4 Controlling the third term follows by the same argument as in Lemma 6
remains tackle the second term, which bound with the offline data.
First, we decompose the last term of 71
H
E
E
Th
(() Jht1
ES
Th 1
(72)
t=
h=1
The latter term of (22) is bounded as:
E
The
(t)) Jht
" sk2]
T
(n(Sn, an) + /() (sh+1, th ( rh (Sh, an) -112 (sh-1,
(() Thtl (oh+1))]
Ey--
1=1 1=1
T
[11)] The - 1/0 1f
B
1=
Exr
( Th 1- (-192+1)
m (18h+t)))
(73)
==
32

---

Actor-Critics Can Achieve Optimal Sample Efficiency
Algorithm 4 Non-Optimistic Actor-critic with Hybrid RL targeting T" (NOAH-+*
1: Input: Function class F.
2: Initialize: F()) t F. // t 4, [H] = o(vdlogTlog AH I T()) x 1, confidence width
3: for episode & = (1/T)
B =
do 4: Play policy (1) for one episode, obtain trajectory, update dataset D/
5: if C (fh .1411) 2 min ch (fh s(t) fht11 + 5H2 3 for some h then
6: Compute critic f(++1) via FQE:
g + arg min ( (Jn,Sh-1 for = -H -1, 1,.,,,,
FEF
- (f,f)
Σ
([(s.0) - a'ed a')
(saan)))DD UDDH
7: Reset policy (t() x
Set liase < 1, ((11)
8:
uputates &-
updatess + 1.
9:
else
10:
Set (v(()
"udaates f 1((-1)
updates
f((+1) t f()).
11: end if
Update Th (1+1) (a|s) x Th (xps)) (x,))) (s,
end for
This yields what is essentially copy of the first term of (7I). For the former term, we use a similar argument to that of Theorem 4 Concretely, as long as ff E F for all f F,
B ((TT Sh+1 1/27 [n)
(Tr(())
(0) (())
sht1 110) 27
+ E 0
(T (1)
sh+t f((1) 2
1/2
T H
E (T p(() - [
1=1
k=1
Bn
(Trr(()
shtt -110) 2
(())
+ E (00)
(Tx (())
sh+1 5/(1
T H
Ex
( (9)
sht1
(1)
ΣΣ
1=1
By
(Trite)
Jh+1
p(t)
51(1) ] + - Ba
(T 1
- -51a)) ) 27
(Tx p(() - 51²²) )
(Tx(00) sh+1 )1(0) 9))
Ny
+ +E Eg
h=1
Ex
(
()) h+1 1// x(e)7²
27 (Tri"" ple) (((0) ) )
Ey
T H
By
(T=e!") 1,10 - -10) 2
)
+ Σ E
(TH. t0
(e)
1mm h=1
2m1
V cott (F, HYHT/No /BH3T
HAB (F, M))22/N..
(74)
33

---

Actor-Critics Can Achieve Optimal Sample Efficiency
Algorithm 5 No-regret Optimistic Rare-switching Actor-critic (NORA) for Hybrid RL
1: Input: Offline dataset Dotf which can be the empty set, samples sizes T,, Not. function class F and confidence width
B >>0 0
2: Initialize: F()) t F, D t Vh E [M], 7- = Φ(v doog Tlog A A Plog
x()) x 1.
3: for episode t = ...,,.... T do
4: Select critic f// (s,a) == argmax J. Jh (8, a) for all 8.a.
5: Play policy (9) for one episode and obtain trajectory (sf : ai .1 ..... (8 :H (t)
(t) (8)
6: Update dataset (( D [( 2 Th
(t) (1) ())1)) vh E [H.
; 7: if there exists some h such that Lh Uh) (() sh41)) minger. c (hh fh+1) 2 5 then
p(0)
8: Compute confidence set F()):
F(t) [EF: clt) (Jh-Su+1) - min ( (hh S H2B wh wh mm].
SRF,,
where c/2 (J,f):=
Σ
(I(,,a) - max
((oxx)---ueexll a'Ed'
((d, . NV E Fn+1
9:
Reset policy (1)) 1.
10: Set flast := t, increment number of updates (x(()
== (1(1-1
+ 1.
updates
updates
11:
else
Set (v((t) "upaates (-(-1) F(() F((-1). updates?
13: end if
(0) 14: Select policy Th (e+1) x Th exp(nff1)).
15:
end for
where for the penultimate line, the bound for the first term follows directly from the Definition sigle-policy conen- trability coefficient, and the second bound follows directly from Lemma 15 Note that the argument is similar to that of Theorem with the exception that we can the single-policy concentrability coefficient as the density ratio need to bound is
F
Th (1) (3)
Jht1
Ex [fh T fh+11
S max sup sup hE(H] sell E, [[hn Tn(n+1)
con (F, II),
(75)
(Th(1)) Jht1
s/:
27
where again the first inequality holds as long as f F for all F.
D.2. Proof' for Theorem 3
Algorithm
We start with the same regret decomposition in Lemma g
- 1i (o{)))
Reg (T)
t=1
T
H
T H ΣΣ
Eg- (1aa (sms )), क 6. (118) - nh (. sn))]
(.1s)))
Eyg [Thh
- To ((()
Sbii) (sn an)
1=1
k=1
1=1 h=
H
T'
E E200 [f -Tas((1) Torht1) (sh, and +
((t)
Σ
E [I Th -h ((18nt)))
h=1
(=1
h=1
T
(Tha ), ( (. (118)) - x/ (. (18nn))
Ex
H ΣΣ
T
T H
Ex [11h -Tns(thi) (sh, an) + >>ΣEE,.
Ex,
(1n22)) mi42(118641) Th (-184t11)
t=1 hml
(=1 Am1
34

---

Actor-Critics Can Achieve Optimal Sample Efficiency
H
T
E g
(1m (11)) -TnJtt) ((1)
(sh, an) +
Σ>
E
(0) (-1sp+1) (fff -) 1 Th+1 (15m+1))
[=1
1=1
[=
h=1
H
Es (1% 1, (11sh) - 7//²² (. (1ss)))
T
H
T H
Ex [11%] - -Thilita) (sh, an)
>>>>
ΣΣmn
Ex [ (1it2 1h+1 - - (196+)))
+
1=1 h=1
Ex
(1hf2(9nt2:)) (0)
Th+ (15(t1))))))
=1h=1
H1
T
ΣΣ
E 2
Tatbifi (sh, an) + [f/ -
ΣΣ k=1
( -), t (-11(1)))+1)-- -1(() ((18)+z))
(76)
where we break up the original second term corresponding to the negative Bellman error under of with a similar decomposi- tion as in the proof of Lemma [8] Now, observe that
H ΣΣ Ex 1=1
T Σ
hh (11o)) T (()) (1ow)) (J2
E
(2) (sw)) (0h
max aEA
1/ (sp. 5.. (77)
1=1 hmm
So the remaining regret decomposition is:
T
(s{))) - V/=" (o(
Reg(T)) =
1=1
T
H
T H ΣΣΣ Ex. [1T -Tnskti) (sh, an)
(1ta (s (, ), (11s)) Th (. (.1sh))
1=1
k=1
(=1 h=1
Ex
(Infa Th+ (-1sn+1) (t) (- ((1stt1))
T +
Exit) (1h²) - Th.bott) (on, an)
Exits (o
),
(t) - Th41 - (-1sn+1))
(78)
The proof then follows analogously to Theorem 2 for the first, third, fourth and fifth terms. Note that the proof' for Lemmas 18 19 and Lemma [3] still hold. Intuitively, this is because the first three lemmas deal with the generalization error of the empirical TD loss under the occupancy measure of the current policy, and the switch cost proof depends only on these lemmas and choosing some f()) with low enough training error. Choosing the minimizer as Algorithm fulfills this condition.
17
Unlike the analysis for Algorithm 2 we bound the second term with the offline data here. We use similar argument to that of Theorem 4 Concretely, as long as -f E F for all f E F.
H ((t) - 11o9) (sh, am>] [
Ex
(Thrle11 - 1/²))² 27
[Tusitt - -1(11) x10) 27
1/2
T H Ey (Thithii - [1o)]]
No
+ +Σ 1-1
i=1 (0
(Trshih pk:)
+ +Σ 1-1 E Ex0
(Th./h1) 1/1 )100) 27
1=1
35

---

Actor-Critics Can Achieve Optimal Sample Efficiency
T
Thshii -1hh |
(t)
(Tw )
27
A=1
Bo
+
+ Bd
N
(ThJoai1 - }
)1)0)
27
t-1
- -1a00) )
Bu
+ +Σ
E (
1=1
Tnihi11 - -1h0]²
T
H
Ex.
(Twiiihs ) 21
h=1
Rp
T H V Con (F) HT/NNH V BHOT
Bu (ThS }
27
+ +Σ
1-1
E g
[Th
-1)))
(00
110) )1)
1=
1=1
S H4Bct (F)T2 /Noft
(79)
where for the penultimate line, the bound for the first term follows directly from the Definition on single-policy conen- trability coefficient, and the second bound follows directly from Lemma 16 Note that the argument similar to that of Theorem 4 with the exception that we can use the single-policy concentrability coefficient as the density ratio we need to bound is
Tri (0)
8h ?1)
E.--
En [fr- Tnffht12 caft (F),
max sup
(80)
(Tnfli11 - f/.)) )
27
NEIH JEF En -n]n+1)
Ep
where again the first inequality holds as long as ff E F for all f f F.
We further note that it is possible to have the critic target QT(") with this framework, if the sum of truncated critics is critic. Fortunately, there is no need to deal with a rarely-updating bonus class like in (Sherman et al. 2024 Cassel and Rosenberg
2024), as we do not need optimism.
D.3. Proofs for Theorem 4
The proof follows analogously to that of the original online case, in line with the analysis and observations of Tan and Xu (0024). The only difference is that we will now bound the Bellman error under the current policy's occupancy measure as
T
H
T
H
T
h
ΣΣ
E
10
ΣΣ
E go
10% 1xaa
E
(es
16%
Lx.al.
(8
d=1
-=
t=1
For the online term, this is bounded with the same Cauchy-Schwart and change of measure argument as in Xie et al. (2022)
T H
T H
11 1P V 5/ (1) 2
1/2
E 10
10
1 Nmn
=
E
18
Ixmm|
H D 1- E
((5
(1)
) xoul
1=1 h=1
1=1
h=
E R
10
X 12
H
Σ
M
H2 v
Σ
B
22 x...
H2 V E
21 x
d
HSEC(Fon. II, T) BH3T
36

---

Actor-Critics Can Achieve Optimal Sample Efficiency
//H I),
(82)
Within the third-last inequality, the first term can be bounded by times the SEC of Xie et al. (2022). ) almost by definition of the SEC. The second term bounded by Lemma [4]
The offline term is bounded by the offline data. We perform similar Cauchy-Schwarz and change of measure argument Tan and Xu (2024) to see that:
T
H
Non 2
1xtt + + 18 de [(6% xxtr
1/2
E go
18)
E de
h
Lx
1(0%% ) 1xor + Ei=1 No 16, )2 x
h=1
t=1 1 h=
B 200 18% Lx 12
Nott J 100% ) 22 xoal Einn
B BBgoll [60 ) x
2-1
Nott 1,10 Xorl]
+ Σ g 1(5% )2 xand
T
H
1. 10 1xoe1 12
Non E )(
h=1
1(1 xx
E de (
2 xand
v Coff (F1 Nox HT/HH//NNN BHOT S v 3oot (FIx yT /Nott
(83)
Note that the first term of the penultimate line follows directly from Definition on the partial all-policy concentrability, and the second term term follows directly from Lemma 16
D.4. Auxiliary lemmas
We also require the following helper lemma:
Lemma 15 (Optimism and in-sample error control for critics targeting QT()) in hybrid RL). With probability at least 1 - 8, for all L E [T], we have that for all h = 1,..., H, critic largeting Q in the sume way as defined in Algorithm 3 achiives
- - )
Σ E
[11 -
) < <0
by choosing 3 c1
for some constant C1, where N = Nott + T.
Proof. The proof is analogous to that of Lemma Tan and Xu 2024). We apply property (ii) of Lemma 7 the following way: we append a sequence of functions generated from offline samples I,..., Nos to the start of the sequence of T online samples.
Let ((t) be sequence of critics in F, defined as follows. Arrange the offline samples in any order. For each [Nor),
define f(() to be any function in the confidence sets constructed by the first n offline episodes.
Now for each t = Notl + 1, ..., N,, define ((1) := f(- Nan) E F(t) As Lemma shows that property (ii) holds for all T E [N], must also hold for all r Non + 1,..., N.
Lemma 16 (Optimism and in-sample error control for critics targeting Q' in hybrid RL). With probability at least 1 5, for all E (T), we have that for all 1,..., H, a critic targeting Q" the same way as defined Algorithm achiives
(i) Th T (0) {( E Fh)),, and fl! 2 ( ((()
37

---

Actor-Critics Can Achieve Optimal Sample Efficiency
(1h--Thhhh) + B anlo)
-Th--hhhh (O(H²))
(ii) Non Epn
by choosing B = C1 (log HN (p)/6] + p) for some constant C1, where N Nou+II the critic is non-optimistic as in Algorithm only (ii) holds.
Proof. The proof is analogous to that of Lemma 1 in Tan and Xu (2024). We apply Lemma 14 in the following way: we append a sequence of functions generated from offline samples i.., Noff to the start of the sequence of online samples.
Let ((t) be a sequence of critics F, defined as follows. Arrange the offline samples in any order. For each vi E [Non]
define f(a) to be any function in the confidence sets constructed by the first n offline episodes.
Now for each t Noft I..... NN, define f(() f(t-Nou) E F(1), As Lemma 14 shows that (i) and (ii) hold for all [ they must also hold for all 7 Not + I.....N.
E. Concentration of the Empirical Loss
Lemma 17 (Modified Lemma G.1, Xiong et al. (023)). ). For any f FF 11, [H] and t S t2 E [TT, we have with probability 5 that
(brt2.=) Lh
(Th fut1, fut1) min R.F
(Fh, fh-1) S H2B.
where 3 = c1 (log (( + Np) for some constant et. Note that = TF if is the greedy policy with respect to f. and G TT otherwise.
Proof. The proof is for the most part similar the proof of Lemma G.I for Xiong al. 2023). which in turn an analogue of Lemma 40 in Jin al. (202T). However, we take into account the fact that the Bellman operator are concerned is the Bellman operator for policy æ. That is, we concerned with T not T. For completeness and thoroughness, we provide the full proof below.
Write ( (f.g, R) ga (1)
(6) ( ahp rr(
a fn+1(5 ( (6) 21 / mani (1 (f,g, m)] for its expectation over 8141
(1)
for the TD error at timestep h and trajectory
i for policy n, and 5% (( (5h a, (1)
(6)
(i) d= known as the
E
Bellman error between f and g.
Now write _ x) = 10th (f. T)² 1 (f. T2 for the difference in the squared TD error between fr. and gh
and the squared TD error between T/ fat1 and fn. Note that this is bounded by O (H2).. We can then show that
(9) [X (1) (f)
E 69) (
(1) (f.g.m) - -1, +
E
(0)
E (0) -o
c0
10, (f.g. (f.g.T)
(f
(84)
where the second-last equality follows from noting that (Chen et 2022)
2 (f.g. - E (9) 2 ~ant (f m) 9n (5% (t)
(2)
(s() (1)
11)
(1) + Th (" (aa) (1))
= Sh 4 ( _a f 0 (
(
(0) (1)
eh (.).
(85)
We use this property again in the fourth equality below to show that
E (1)
t 60 (x (f. m = E 10 to ((. (f.g.
- (1.T.
-
38

---

Actor-Critics Can Achieve Optimal Sample Efficiency
A ( mam ((, - (1,
(f.g.
gx)) , 00 (2)
E hef vdtll (x (J,, x)
(86)
We can then apply Freedman's 's inequality (Jin et al. 2021 class to see that for any f F and g E g.
Chen et al. 2022) and a union bound over the value function
E 50) (
(x (0) (J: ([,g
5 H.
E 10 # mdd-()) (x/ (J.y. m]] + H²
(87)
5=
holds with probability at least 6, where log (og(HT?Mg NT The result now holds by observing that
E cg S44
(an Narco (x) (f.g. 20
and that
l2
Σ
x (f.g.)) H) s H²8
for any f E F and g E g with probability at least
Lemma (Modified Lemma G.2, Xiong et al. 2023 ). Lel l1 S l2 E [T], a E II, and F. If holds with probubility least 20 that
Ch
(Sh, fb+1)
Cn
c(lrita)))
(Th fn+t, S CH²B,
then it also holds with probability at least 25 that.
(sh a (0)2 S 11113
Σ E 10(1)) i=t1
27
S C11133,
where C1 = CC E [00], or 2C for all constants C 2 2, and 8 = ci (log HN + Np) for some constant Cj. Note that g = TF if x is the greedy policy with respect to f, and G = (T otherwise.
Proof. The proof similar to that of Lemma G.2 in Xiong et al. (202)). By the same argument as in Lemma 17 we apply Freedman's 's inequality (Jin et al. 2021 Chen et al. 2022) and a union bound over 1/T- (or 1/N net the hybrid case) of (F,9) see that for any f E and g G.
l
(f,g,T)))
E 10) ( (F.
S H
E 10 )
(x (J.g. mT) + H²,
(88)
A=
1=t1
i=
holds with probability at least - 8. By assumption, we have that
Σ (f - &C SCHB..
(89)
If C E [1, 100] and therefore is relatively small bounded constant, we can choose ei large enough in the definition of 3 so that there is some f.g in the covering of (F, () such that
12
f2 SCH2
Σ x 0 (fff.))
Σ 1=4
x (F.g..))
s OHH), and
Σ i=
x
(90)
39

---

Actor-Critics Can Achieve Optimal Sample Efficiency
and consequently that
1/2
< and E
[X (f: & (C (C1+/))H38+0(H) & (C 1)H23.
h+
As Xiong et al. (023) and Jin et al. (2021), the argument for the case where 100 follows by accepting a
2-approximation where C 2C, and the argument for Σ E a7 (0x) 21 also follows analogously by taking expectations.
Note that taking 1 = 1, 02 = t- - 1, π = x((-1), f(() or t = 1,12 =t 1---,xx- 1,x n = f(t) gives results of direct importance to us.
Lemma (Modified Lemma G.3, Xiong et 2023 ). Lett S 12 E (T), π E II, and f E F. if holds with probability least 20 that
((1)22))))) (Shr fn+1)
Ln
(11
(Tht, CH²B,
then it also holds with probability at least 1 28 that:
Σ
(ff.m)
(8h oh
2
E aa Σ 1=h
( 27
2 C. CHH²3,
where C1 = C+ E [1. 100], or 2C for all constants C' 2 2. and 3 ci (log [N o
N)) for some
constant e₁. Note that = TF if n the greedy policy with respect to J. and G = (T (T otherwise.
Proof. The proof similar that Lemma G.3 in Xiong et al. (2023). By the same argument as Lemma 17 we apply Freedman's inequality (Jin al. 2021; Chen al. 2022) and union bound over 1 1/TT-ee (or 1/N net in the hybrid case) of (F,9) () to see that for any f E F and g TTF,
10 Σ X x=11
(f.g.n) - Σ E
10)
(X) (
(f.g.))
S H
10 She
(x/ (f.g H2
(91)
1=1
1=
holds with probability at least 8. 6. By assumption, we have that
Σ (U. Σ t=t
2CH' CH2B.
If C E [1, 100) and therefore is relatively small bounded constant, we can choose e1 large enough in the definition of B so that there some ğ in the covering of (F,9) such that
t2
12
x (f.f.))
x (F.g.
< OII), and x x)
(92)
and consequently that
f2
(C and >
[X ( (f.f.=)) 2 (CC--/21) 1/2 2 (C 1)H23.
c 30
(93)
As Xiong et al. (202)) and Jin et al.] (202I). the argument for the case where
100 follows by accepting a
2-approximation where C1 C/2, and the argument for Σ Bet( (0h²) 27
also follows analogously by taking
expectations.
Note that taking f = 1, 12 = - 1, n = (tt-1), f(t) or t = 1, =t - 1, = T5, = importance to us.
= ff(() gives results of direct
40

---

Actor-Critics Can Achieve Optimal Sample Efficiency
F. What If We Target Quit) Instead of Q*?
Algorithm 6 NORA-T
1: Input: Offline dataset Doff, samples sizes T, Nott, function class F and confidence width
2: Initialize: F()) <- F, D <- 0, vh E [H], @ -A x(1) x 1.
3: for episode / = ..,,..., do
4: Select critic 1/ (s, a) argmax, J In (s, a) for all s.a.
5: Play policy x() for one episode and obtain trajectory (sf ai :1 .....
(1) (1)
(9) 10) (1)
(S HH .TH
6: Update dataset ( D U {(s) "h Th (ntt), E [H]
(1)
(t) (1)
7: if there exists some h such that Cn Uh -h+11) EF, Ch c(t EF
(lt (t) ((t)
(sh (h11)+ 2 5H then
d(t)
8: Compute confidence set for Bellman operator
T
set F(t) t F((,
F(ttol))) { fEF F: fn
cllxxt))
(n+i))
min ((),x(1)) REE
(Th: Sh+1) S H23 wh vh e
where La (1,8):=
(1(
Σ
// e Fr. E Fr41-
(E. UDOMA
Set fimst := t, increment number of updates (r(t)
v-(--1 updates
9:
updates
10: else
11:
Set (V(()
"upaates updates F(() == F((-1).
12: end if
(1) (1+1) x "h exp(nf))).
13:
Select policy Th
14:
end for
F1. But can we bound the number of critic updates?
We attempt to show similar result to Lemma 13 for the Q-function confidence set F(t,x(1) targeting (1) However, will later see that we run into an issue.
Fix some h E [H] for now. For simplicity, write K₁ = A (T) for the total number of updates induced by updating the Q-function class targeting (*),, and t1,h & the update times for p((), with tu, = 0. By definition, at every tg have
hn chaaathhn (llan)) .sht1
plleen) min chaan dlaaatlin (Fh f1tt1 ploaah)) 2 5H23
(94)
F...F
An application of Lemma 17 yields
0 < Cn ((ant)hhh))) ( (Th
(tkin)) olteer)) o(beae)
(Phr Fht11 $ H23.
(lle,))
sht1 sh+1
min Cn Ei
ch (hlenntlial) (Tho slltae)) 2 ch (lamnolaan
Tr Toeeellenn
shtl i slet1 ) HH2
(leaa) ((aw))
min K,
Chaaetlleill (ffteun), slle c/ (leaattan
( (Trreltanl
plbaade pltual) s
2 4H2
From the above, we can now establish that
elfe-nantiieen (oanl) (flltaa) sllaaa)) (tu-na4tlte (OW ((le,)) (llew)
(TH shtt Sh+t1
.h+11
c/ ol + I:ly nn (2)))) (flt--natt) :hh41 ((4pinnt)) L ((e-ss-lidenn (To
(unn ( (111 plls-1att)
Sht1 s

---

Actor-Critics Can Achieve Optimal Sample Efficiency
Ch cllennn (Ea ( -hht
(Th (Tel"ka)) (lt--aatl) slltsaat)
Ln
c/ chansannian (Sh (J (flt-raat))
S142 (l41-aat)) + (le zastleeii (eplee ((be-1at)) Shit sitilaatt
(Th Jh11 15h41
C Ch (Shema) slepea)
(Th Thr gleen) pllenw))
Ln
c/ Ch (lln--ant)
shitt sitisaatl)
+ t coemeaa TTe (aallanh shtl shatl
(lon-rat)) sherlatt)
2 4H 3 3 3H² 3
(95)
We substitute p((uah) for // ((a-11++1 in the second equality, and obtain the last inequality via the inequality established in the previous argument and an application of Lemma 17 on le 1,1,, π = x((4,)), , = f(le- 1.a
Therefore, for any & such that 1 < S tu this argument and noting that f/. ((0x-1.1 1.1+1) yields
((una))
-hh
c/ clfe-1an tilt (nh:-ii c/
((--sttttttan Tha p(0) Jut1 Shtz) 2 3H2
(Tx"
(96)
An application of Lemma
19 while noting that f/ 1att))
((aa)) yields
f PE. (()
(1
Th"
h+t))
)²²²
2
(5 a = Σ
(f T
(ann) oltuaa)) 2 (5 (8/ 02 2H²3. (97)
Summing over all (1,br LK, yields
Ka t (1% -Th""
( The
(treat) v(())
1htt1
(5)
11t1)
c(() (0)
(s) (a 2 2(K, 1)H23 (98)
k=1 ii -
By Lemma 14 we have that
Σ
-
Th 11-1) 2 ( Sh+1)
(0) S (HH2B).
(99)
Invoking the squared distributional Bellman eluder dimension definition yields
T
Σ
(())
T "1 1/22) 2 (
(1)) (ddH? T).
(100)
t=1
So we have established that
2(Kr 1)H12
T
(1)
The
(tear) lnt2) ) 2 (5/0 ())
1=1
and Σ
(1()) Th
11 (()) )² (5 ;
2ddl111gg11 T).
1+t1)
However, it remains unclear how one can relate
Σ (110 Th (teea) (() )²
Sht1] (0/ (0l0 (1)
42

---

Actor-Critics Can Achieve Optimal Sample Efficiency
T
T. Jati) )² (5/ )
to
We would like the former to be no greater than the latter, but that does not necessarily hold, as 7((-1) is closer to the target by which F( was constructed, π (ftm),, than π (ffeeu), So if anything, it is likely that the Bellman error under the Bellman operator for (ftm)) is greater than that for x(t-1), therefore difficult to say anything with regard the number of updates for each h.
F.2. But can we control the negative Bellman error?
There is another obstacle. It is unclear how to control the negative Bellman error under the occupancy measure of the optimal policy, given the far more limited form of optimism in 7 This is because the more limited form of optimism only allows us show:
B (100
T
Jht1
(1)
Ex (. n//r (161))
(101)
h=1
t=1 h=1
To see this, observe that by Lemma
Th
Ju41 11 (s, a) S f Therefore,
p(1)
T H
T
H
Ex
((())
xx
10
p(1)
Ex-
a) + 110 (s' 12, (6)) (s.
h+1
tm h=1
T
The (10 ( (s,c))
Bxd
"T" (() [hfr(8,a) Thi (aa) ((t) (1.1
Eyg
(x( a) + (
(8', 1 (8)) (s 1 ( (
Ex (s 1 (5 (5))) f 1s' T (s'))
1=1
A=1
T
Σ
Ex-
(s) ), (0) - nht - (1161)
(102)
We can now continue to go through the mirror descent argument. Recall that
T (-155) ex (1( Ened 1 (als') exp(n (1) (s',
(++1) Aet
(+Is)
(-|s')
- (1) (-1s)) (xp(nnfi2(ss
and rearranging this yields
(++1) (1) (s',-) log 2, + log a+1 (+|s") - log ग m (-Is'),
where log Z, is
log Z, =log
Σ A
(t) (tlss))epptft77 ( (-Is') log म n ((++1) + nf122(s'')
Noting that EnEA (111) (+)))
(Ama+1) (115)) Th+1
O. we can now bound that
(n (6', )), (8)
Tht1 (116)) -Tht1 -14ttt1))1177)
43

---

Actor-Critics Can Achieve Optimal Sample Efficiency
(log Z₁ - log h+l
(1+1) (-1s²) - log " Mh+i 1++1(+ss (-1s"), Th h+1 (-1s²) - hh+l
(1)
(1 (-1s')
log (1+1)
hh1 (-|s) log h+1 (-1s'), - =
(hart (-1s))
mh-
KKL
(< h+ (-1s8))
(-1s") |I Mh+1 (-1s)) + KL
(-1ss |l
# (+1') KL
(-1s')
(103)
where the last equality follows directly from Lemma
24
This establishes the following telescoping sum
B
K
*h+1
11
-((+))(((ss))
[15)))
1=1
T
B
KKI.
(0(0) (*ata(1ss") || - (-15)) + KI.
(Th+1
(1(4at2)(-18))) m/44 (1s)) KL.
(Th+1
(-(s))
1)
E
KL
(+41(11s') |1 x/+1 (-15))
(2)
((+1)
KR
1
Fx
KI. Th+1 1) (.16') ( (115))
KI.
(Th+1
m (151))
H
Kn Ex.
Ex
7 KL.
(1) (-16")
11 Th1 (1)))
KI.
(1x+1) (-18") (h+1
|| (-1=')
(2212) 7+1
(16))]
(104)
To see this step, consider the example where we perform switches at step 1, 3, 6, and T 8. Note that we adopt the convention that x (T+1) (T)) The telescoping sum then becomes
(t + 1|lt 1) (t + 1|lt)
[=1
(2, - KL + (L (L 2) + KL 4) - K KL(4,4) + 6) - KI, 54) + KI,(7,7) (), + KI,(7,8) KL((77) + KL((7,)) KI((788)
(2,33 + KL 4, 6) + (L(7,9).
(105)
So the sum includes every 4 where a switch occurs:
H
Σ Exi
( (s.
- (itt (1151)
t=1 h=1
Kg
H
Ex
KL
(14- Th
(1-""()ss)) || Th+1
(12-11 (18))
Ex KL (+)
(11s))))))))))))))))))))())))( Th41
(15))
= H (m 1k).
The latter two terms cancel the TV distance, or any distance where the triangle inequality holds. is harder to see a relation with the KI. divergence, but in general, one may not be able to achieve sublinear regret. This is because, if we merge this term with the first term in the regret decomposition of Lemma
g we obtain
T H
T
ΣΣ Ex- (5
(i - 222 (122(166)]] + ΣΣ Ex
[f 10 (211ss))) ( (15)))
h=1
which evaluates to
T H
- (-1s))]
(txx)
E.
Th+1
1=1
44

---

Actor-Critics Can Achieve Optimal Sample Efficiency
G. Miscellaneous Lemmas
In this section, we collect some auxiliary lemmas that are useful in deriving our main results. Lemma 20 (Bound on Covering Number of Value Function Class, Lemma B.1 from Zhong and Zhang (2023)). Consider the value function class induced by a Q-function class F( and a class of stochastic policies IT given by
( = (in((,)), Sa E E 11
Then, the covering number of the value function class can be bounded by the product of the covering number of its components:
Nygo (p) S NN 500 Nngo (D/211)
Lemma 21 (Lemma B.3, Zhong and Zhang (023)) For nτ, x ((A) and Q, :A Rt, if(()) exp(Q()) and a-() x exp (Q), we have
T - ~ S 2 KL(T|T>) S 2 11Q Q'l
Lemma 22 (Adapted Version of Lemma D.2 of Xiong et al. (023
Let F be a function class with low Da-type Bellman E==00 (
Eluder dimension. Then, for any policy a E TI, if we have that and B 2 9, for any t' E [T] we also have that
(t) Th 11+1) 1 (8) ohh $ 3H2 for any t (T)
c(t)
(3)
Σ E T S (5h a0) So
S (Fs log logT).
Lemma 23 (Value Difference/Genneralized Policy Difference Lemma, (Cai et al. two policies and f be any R-function. Then for any E [T] we have
2024 Efroni et al. 2020 Let n, n' be
fi (81, (s1)) VT (si)
B (K/ (sh. -) ,), Th (1) - Th. ( 8n)) + Σ Ex [ (sn, an)
-Th sn+t (sn, an)
Lemma 24. For any probability distributions T(-), T1 and x2(+)) over space S. We have following relationship holds:
(m) (1)))-((),,og)))) r(-) log m2())) (K.(m)] (T(ml]] KL(TT|TT2)
Proof. Note that for the first equality, we have
(m)()) - (--), (-) log π2(-) = (-), (og, (-)) log T2 T²(+)) (x((), log x()) log 72 x2(-))
(m)()), log ((-) log m (:)) (TI (-), logm(()) log T2 T2))) -TT()), (()) log mog))()))
-KL(TI| (LL(mIII2)) KL [2)).
Lemma 25 (Policy Optimization Difference). Let Let ((), t 1,.... T be sequence of policies updated by:
Thti (. exp exp (10110) (s',-))
(0)
((+1) T #+1
(-1 (() = EaEA Thti (a ( exp (n (8',a)
= 2, (0()
ah+1 (-1 exp (nshi) (s'.-).
45

---

Actor-Critics Can Achieve Optimal Sample Efficiency
where ( E F. For any 11, l2 E [T], where pl is arbitrary of distributions,
Σ
( ( -
11l + 1).
Proof. We observe that
M++ (- (())
[t+1)
exp(0)
2
(: (-1 (8))
(0)
A A EnEd exp(n)H)
" h+1 (-1s')
(++1)
exp(ntnt1 (s',
cxp(nH)
exp(nH).
1/41 (-| s²)
(t)
(t) EPEA (- 5') exp(n exp(nnfiisstaa)) as)
| EnEA exp(0)
So establish that since e 2 2 - for all IR
Tt (-1b')
(1)
M+1 (-1s/) - - (-1s') - (+1s))
(1+1) (1)
(1s') (-ss)) exp(-nHH)
(1+1)
Th+1 (-1s)
(1+1)
Th+t
#h+1 (1- (1- S H HH hh+1 (-Is).
(1+1)
(106)
By the triangle inequality and the fact that s H for all f E F, it then follows that
t2x
Σ
Enco
(21) - -
Σ
Exce
(H,, (H, mHH (0+1) (est(((1s)))
max(ti.t2)
Σ
n112 s 2mll t1l + 1).
(107)
H. Further Experiment Details
Figure be reproduced by rumning actor critic ipynb within the following GitHub repository Figure can be reproduced by rumning scripts/ www.antmaazeeeeeeeaa sh within wttggghtwbb.ooooaoatooooooaaalla
The results for Cal-QL arise from running the script as-is. Algorithm 2H can be reproduced by adding the flags -enablllccaa = lss, cal=aa lse, and
the following GitHub repository
--online use cql=False. Algorithm IH can be reproduced with the same flags as Algorithm 2H, but additionally setting the config eql _ql_max__________eee max_taxtttt.. wawaxttaagettttaae backup argument within the ConservativeSae () object to False.
To implement the mirror descent update in Figure
store the sequence of past Q-functions fitted for Algorithm and (t) (s, for given h, s, a tuple, (ass).f (s, a)) for Algorithm To generate a sample from this density, the normalizing constant be computed exactly in the case where there is finite number of actions. Otherwise sample can be generated via MCMC, importance sampling, rejection sampling.
the last Q-function for Algorithm Upon receiving a query to evaluate or sample from Th
we compute exp(1) ΣTT fl( (s, a)) for Algorithm and exp(1)(t (ast)) f
46


Reviews:
[{"review_id": "O2P9jjEJOh", "reviewer": "Reviewer_TW2G", "summary": "This paper introduces the first provably efficient actor-critic algorithms utilizing general function approximation. For cases where the policy class does not grow rapidly due to critic updates (as mentioned by \"ease case\"), the authors propose a novel algorithm that combines the GOLF algorithm with mirror ascent from policy gradient methods. Under specific assumptions, the authors establish that the proposed algorithm achieves a sample complexity of $O(1/\\epsilon^2)$ and a $\\sqrt{T}$-regret guarantee. Furthermore, in scenarios where the policy class expands significantly with critic updates, the authors design an algorithm that limits critic updates to $O(\\log T)$ while still attaining the same $O(1/\\epsilon^2)$ sample complexity and $\\sqrt{T}$-regret bound. The paper also extends this approach to the hybrid reinforcement learning (RL) setting, demonstrating that initializing the critic with offline data can enhance sample efficiency compared to methods relying solely on either offline or online data.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for providing helpful comments and suggestions to our paper! We are glad that the reviewer  believes our theoretical justification to be well-supported. We have revised our paper and included numerical experiments based on the suggestions from the reviewer in this link (https://github.com/anonymoosemoose/actorcriticicml2025/blob/main/actor_critic_figs.pdf). \n\n**Comments**\nRegarding Corollary 2: $\\text{OPT}^*, \\text{OPT}^f$ are not formal definitions, but placeholders for user-defined bounds on error terms for their chosen optimizer. We’ll clarify this in the revision.\n\n**Response to Weaknesses and Questions**\n\n**W1: Lack of experiments and computational inefficiency.**\nThese are very valid concerns. We address them below.\n\n**Computational inefficiency.** Optimism is a powerful yet computationally expensive approach in RL. Recent work (Song et al., 2023) shows that in hybrid RL settings with good offline coverage, optimism isn’t necessary, and FQI suffices for provable efficiency. We extend this to the actor-critic setting with Algorithms 1H and 2H, corresponding to Algorithms 1 and 2 in our paper, but without computing confidence sets. When ERM is efficient, these become computationally practical. We show that:\n- Algorithm 1H achieves a regret of\n\n$$\\text{Reg}^\\pi(T)\n= O\\left(\\sqrt{H^4 T \\log|\\mathcal{A}|} + \\sqrt{\\beta^\\pi H^4 c_{\\text{off}}^*T^2/N_{\\text{off}}} + \\sqrt{\\beta^\\pi H^4 T\\text{SEC}(\\mathcal{F}, \\Pi, T)}\\right),\n$$\n- Algorithm 2H achieves a regret of \n\n$$\n\\text{Reg}^*(T)\n        = O\\left(\\sqrt{d H^5 T \\log T \\log|\\mathcal{A}|} + dH^3 \\log T + \\sqrt{\\beta^* H^4 c_{\\text{off}}^* T^2/N_{\\text{off}}} + \\sqrt{\\beta^* H^4 T  \\text{SEC}(\\mathcal{F}, \\Pi, T)}\\right)\n,\n$$\n\nwhere $c_{\\text{off}}^* $\nis the Bellman-type single-policy concentrability, $\\beta^\\pi$, and $\\beta^*$ are confidence set widths scaling with the log-covering number, and $N_{\\text{off}}$ is the number of offline samples. If $N_{\\text{off}} = \\Omega(T)$, we have $\\sqrt{T}$ regret, and we incur only an additional factor of $\\sqrt{c_{\\text{off}}^*}$ as a price to pay for omitting optimism. This improves upon Zhou et al. (2023), who required $1/\\epsilon^6$ samples.\n\n**Experimental results.**  \n1. **Optimism in linear MDPs.** We compare Alg. 1 and Alg. 2 to a rare-switching version of LSVI-UCB on a linear MDP tetris task. The condition required for Alg. 1 to work holds here, as we do not clip the Q-function estimates. We see that Alg. 1 performs better than LSVI-UCB (!), and Alg. 2 achieves sqrt(T) regret even though it performs slightly worse than LSVI-UCB\n2. **Deep hybrid RL.** We compare Algs. 1H & 2H (with offline pretraining) to Cal-QL (Nakamoto et al., 2023). Alg. 2H takes a max over 10 randomly sampled actions from the policy to enhance exploration as Cal-QL does (this can be viewed as a computationally efficient version of optimism, or alternatively as approximately targeting pi^*). It outperforms Cal-QL, which outperforms 1H. Neither uses pessimism. This supports the claim that hybrid RL can avoid both pessimism and full optimism while retaining strong performance.\n\n*Note: In the plots, the first 1000 evaluation steps correspond to offline pretraining. Alg. 1H and 2H naturally underperform initially before fine-tuning begins. All plots are smoothed following WandB defaults.*\n\nWe hope that these experiments address your concerns regarding real-world feasibility.\n\n**Q2: Why does the regret bound for Algorithm 2 still include the SEC term, despite assuming a bounded Bellman-Eluder (BE) dimension?**\n\nWe thank the reviewer for this remark, which allows us to realize a subtlety. We use SEC over BE because it is generally tighter. However, Xie et al. (2022, Prop. 14) show that SEC is upper bounded by BE under the greedy policy’s occupancy measure, but not the BE dimension for Dirac deltas (Jin et al., 2021, App. H). Still, we can use Xiong et al. (2023, Eqs. G.13–G.14) to bound the term containing the SEC with the Bellman eluder dimension for Dirac deltas. We’re happy to clarify or include this in the revision.\n\n**Q3: Can the number of critic updates be bounded more tightly when updates are small?**\n\nYes – thank you for this insightful question. One can use an $\\epsilon$-net and collapse nearby critics when $\\exp(\\eta(f - f’)) < \\epsilon/2$, which can reduce the bound significantly. This is a great observation that we would be more than happy to include in the paper.\n\n**Q4: When is Algorithm 1 preferable to Algorithm 2?**\n\nThough Alg. 2 often performs better, it may underperform when the Q-function sum has a low-dimensional structure (e.g., linear MDP Tetris). This is due to policy resets during rare-switching critic updates, which disrupt learning. Also, as shown in Table 1, Alg. 2 incurs an extra $dH$ factor in settings favorable to Alg. 1.\n\nWe truly appreciate the reviewer’s helpful and encouraging comments. **If our revisions address your concerns, we’d be grateful if you would consider raising your score.**", "claims_and_evidence": "The main claim of this paper is that an actor-critic algorithm can be designed using general function approximation for the value function class while achieving $O(1/\\epsilon^2)$ sample complexity or $\\sqrt{T}$-regret. The authors propose two algorithms and provide theoretical results to support their claims. While I have not rigorously verified all proofs, the theoretical justification appears well-supported. Notably, unlike prior actor-critic approaches that rely on coverage or reachability assumptions, this work achieves sample efficiency without such assumptions, making it a significant contribution. However, the computational cost of the proposed methods and the lack of empirical comparisons raise concerns about their practical feasibility and efficiency in real-world implementations.", "methods_and_evaluation_criteria": "The evaluation criteria used in this paper, regret and sample complexity, are well-established metrics in the reinforcement learning literature and are commonly used to assess an algorithm's sample efficiency. However, it would be beneficial to include numerical experiments to further validate the practical applicability of the proposed algorithm. Empirical results would help demonstrate its real-world feasibility and provide insights into its computational efficiency and performance in practical scenarios.", "theoretical_claims": "I have not rigorously verified the proofs, but the results appear to be reasonable and well-justified.", "experimental_designs_or_analyses": "This paper does not include any experimental results.", "relation_to_broader_scientific_literature": "From a theoretical perspective, the proposal of an actor-critic algorithm achieving $O(1/\\epsilon^2)$ sample complexity for general function classes is a highly promising result. Additionally, the extension to hybrid RL is particularly valuable, as it demonstrates the potential to leverage offline data to enhance sample efficiency in scenarios where interactions with the real environment are costly.", "essential_references_not_discussed": "I believe the authors have appropriately and thoroughly discussed the related work.", "other_strengths_and_weaknesses": "[Strengths]\n1. This paper introduces the first actor-critic algorithm that achieves $O(1/\\epsilon^2)$ sample complexity and $O(\\sqrt{T})$-regret under general function approximation settings. Notably, unlike prior works that rely on coverage and reachability assumptions, the proposed method does not require such assumptions while maintaining sample efficiency.  \n2. The paper effectively categorizes the problem into easy and hard cases, clearly outlining the potential challenges in each scenario and explaining how the proposed approach overcomes them.  \n\n[Weaknesses]\n1. The results are entirely theoretical, with no empirical validation to demonstrate how the algorithm performs in real RL environments. Including experimental results would strengthen the claims.  The proposed algorithm, while theoretically sound, appears to be computationally inefficient, which may limit its practicality for large-scale or real-world applications.", "other_comments_or_suggestions": "It appears that the definitions of $\\text{OPT}^*$ and $\\text{OPT}^f$ in Corollary 2 are missing. Could the authors clarify their precise definitions?", "questions_for_authors": "1. Unlike Algorithm 1, Algorithm 2 assumes a bounded Bellman-Eluder dimension for the Dirac delta distribution. Despite this, the regret bound still includes an SEC term. Could you clarify why this term appears, even under the bounded Bellman eluder dimension?\n\n2. For the policy class $\\Pi^T$, is there an intuitive explanation for the lower bound on the number of critic updates? If the critic does not change significantly, the current bound in Lemma 1 seems rather crude. Could a tighter bound be derived under such conditions?\n\n3. Algorithm 2 appears to be strictly superior to Algorithm 1 in terms of performance. What are the limitations of Algorithm 2 compared to Algorithm 1, if any? Is there a particular setting where Algorithm 1 is preferable?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "ywb8HMfjXc", "reviewer": "Reviewer_F5Vz", "summary": "This paper mainly concerns the theoretical analysis of the actor-critic type of algorithms in finite-horizon episodic MDPs. Beyond linear MDP scenarios, the work focuses on the regret and complexity analysis of general function approximation case. To begin with, an algorithm named Double Optimistic Updates for Heavily Updating Actor-critics (DOUHUA) is proposed, the regret and lower bound of sample complexity of which are shown. However, such bounds depend on some corresponding log-covering number that may linearly blow up. Motivated by such gap, a second algorithm named No-regret Optimistic Rare-switching Actor-critic (NORA) is proposed, which is shown to achieve $\\\\sqrt{T}$ regret, under a specific assumption (only considering distributions that are Dirac deltas on a single state-action pair).", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the helpful and insightful comments! We are glad you recognize our work as achieving \\sqrt{T}  regret for general function approximation under specific assumptions—extending beyond the linear setting considered in prior work. We’ve addressed your questions and incorporated suggestions into our revision. \n\n**Computational Efficiency and Numerical Experiments**\n\nWe have also constructed computationally efficient versions of Algorithm 1 and 2 that require only an offline dataset with good coverage, and have also conducted a set of numerical experiments on the request of reviewer TW2G. The guarantees for Algorithm 1H and 2H, as well as the summary of the numerical experiments, can be found in our response to reviewer TW2G, and the results of the numerical experiments can be found in this link (https://github.com/anonymoosemoose/actorcriticicml2025/blob/main/actor_critic_figs.pdf). \n\n**Response to Weaknesses and Questions**\n\n**Weaknesses**\n1. **W1: Assumption 3 – Dirac deltas as distributional candidates**\n\nThanks for this thoughtful observation. The Bellman Eluder (BE) dimension was introduced by Jin et al. (2021), who primarily considered two types of distributions:\n1. $\\mathcal{D}_{\\mathcal{F}}$: distributions induced by greedy policies  $\\pi^f$ , and\n2. $\\mathcal{D}_{\\Delta} $: Dirac delta measures over state-action pairs.\n\nThey suggest an RL problem has low BE dimension if either variant is small. Our work aligns with this perspective:\n- Alg. 1 does not require rare-switching and scales with the SEC, a more general and often weaker measure than BE dimension.\n- Alg. 2 currently assumes low BE dimension under  $\\mathcal{D}_{\\Delta}$, which is aligned with prior frameworks (e.g., Xiong et al., 2023). That said, this can be weakened to the $\\ell_2$ eluder condition (Xiong et al., 2023) with nothing more than a change in notation. We present results in the BE framework for familiarity and generality (capturing linear MDPs, low-Eluder-dimension classes, etc.).\nWe’ll clarify these distinctions in the revision, and are happy to make the generalization to the $\\ell_2$ eluder condition.\n\n2. **W2: Generalizability of regret bounds**\n\nWe appreciate this concern. While SEC can depend on  T , it typically scales better than the BE dimension and is more general. Importantly, BE dimension is known to scale as  \\sqrt{T}  at worst (not linearly), so the regret result for Alg. 1 remains meaningful. Though Alg. 2 assumes low BE dimension under  \\mathcal{D}_{\\Delta}, this can be relaxed to the \\ell_2 eluder condition with minimal modification. This class includes:\n1. tabular and linear MDPs\n2. low Eluder dimension classes\n3. linear mixture MDPs\n4. kernelized nonlinear regulators\n5. the SAIL condition\n6. undercomplete POMDPs\nIn all these settings, Alg. 2 achieves  $\\sqrt{T}$  regret.\n\n**Methods**\n1. **M1: Policy not derived from the current function**\nThis is mostly a notational choice for cleaner proofs. As in GOLF (Xie et al., 2022), the critic is chosen from the prior confidence set; in other works (e.g., Zhong & Zhang, 2023), the actor update is based on the current critic. We follow these conventions for simplicity, though users need not in practice.\n\n**Questions**\n\n1. **Q1: Assumptions on state and action spaces**\nThere are no specific assumptions here—the state and action spaces can be continuous or large. General function approximation accommodates this flexibility.\n\n2. **Q2: Superscript (t) in Equation 1**\nThanks for catching this! The summation should read $ (s, a, r, s{\\prime}) \\in \\mathcal{D}_h^{(t)}$, not  $\\mathcal{D}$. We’ll fix this in the revision.\n\n3. **Q3: Definition 1 – Bellman error and auxiliary function class**\nYes—the Bellman error $ f_h - \\mathcal{T} f_{h+1}$ , with $ f \\in \\mathcal{F}$, belongs to the auxiliary class $\\mathcal{G}$. We’ll clarify this in the text.\n\n4. **Q4: Covering number notation in Theorem 1**\nThe term  $\\mathcal{N}_{\\mathcal{F}, (T^{\\Pi})^{T} \\mathcal{F}}$  represents the covering number of the union of two function classes: $ \\mathcal{F}$  and  $(T^{\\Pi})^T \\mathcal{F}$ . We agree this should be stated more clearly and will revise accordingly.\n\nWe also thank the reviewer for the very thorough list of errata you have provided within your remarks on clarity, and will make the revisions requested. Let us know if further clarification is needed—we sincerely appreciate your thoughtful review! **If our responses have successfully addressed your concerns, we would be sincerely grateful if you considered adjusting your score.**\n\n1. Xiong et al. (2023), *A General Framework for Sequential Decision-Making under Adaptivity Constraints*.\n2. Jin et al. (2021), *Bellman Eluder Dimension: New Rich Classes of RL Problems, and Sample-Efficient Algorithms*.\n3. Zhong and Zhang (2023), *A Theoretical Analysis of Optimistic Proximal Policy Optimization in Linear Markov Decision Processes*.", "claims_and_evidence": "- Assumption 3: solely assuming Dirac deltas as the candidate for distributions can be a strong type of assumption.\n- Generalizability: as discussed in the part 'Quality of the regret bound', SEC is further bounded by the Bellman eluder dimension, which may scale with $T$. The main regret result of $\\\\sqrt{T}$ is not universal. Further evidence beyond linear/kernel MDPs is preferable to support the statement 'function classes with low Bellman eluder dimension are ubiquitous', as here the paper claims to solve general function settings.", "methods_and_evaluation_criteria": "> **Methods**\n- Algorithm 1: as pointed out in the paper, DOUHUA is an extension of the former algorithm GOLF. According to the reviewer's understanding, in GOLF, at episode $t$, the behaviour policy $\\\\pi\\^{(t)}$ is a greedy policy w.r.t. to $f\\^{(t)}$, which was calculated by the argmax throughout the confidence set. Then $\\\\pi\\^{(t)}$ is executed to collect online data. However, the order of updating policies and functions are different in DOUHUA. Especially, after calculating the current function approximation $f\\^{(t)}$, the policy is not updated. Instead, $\\\\pi\\^{(t)}$ was already derived using mirror descent idea with the last function approximation $f\\^{(t-1)}$. In a word, the current policy that helps collect new data is not derived from the current function. I wonder if this is a misspecification (due to asynchronous updates) or a specific design of DOUHUA for theoretical properties?", "theoretical_claims": "- Roughly checked the proof sketch in the main paper, while not the Appendix.\n- Given the confusion in several notations as mentioned below, the reviewer is not sure about the unchecked part.", "experimental_designs_or_analyses": "N/A", "relation_to_broader_scientific_literature": "- Compared to former work on linear MDPs, the paper tries to solve the setting with general function approximation.", "essential_references_not_discussed": "None.", "other_strengths_and_weaknesses": "> **Significance**\n- As mentioned in the above, 1) how ubiquitous are the function classes with low Bellman eluder dimensions and 2) whether the assumption of Dirac delta distributions are mild largely affect the significance.\n\n> **Clarity**\n- In the last sentence of Section 1.2, the citation format needs adjustment (similar issues appear several times).\n- In Line 140, it is recommended to explicitly point out that $t$ represents the index of episode.\n- Line 149: it can be confusing to use superscript $f$ to denote optimality, as it is just a generic function.\n- Line 149-150: such definition of greedy policy lacks for scaling due to existence of multiple optimal policies.\n- Page 3: the definition of covering number needs a metric that is not mentioned.\n- Definition 1: the $\\\\epsilon, \\\\epsilon\\^\\\\prime$ mentioned in the conditions never appear in the following inequalities.\n- Lemma 1 & Theorem 1: according to the reviewer's understanding, the term $\\\\mathcal{N}\\_{\\\\mathcal{F}\\_h\\^{(t\\_k)}}$ is never defined (although the $\\\\mathcal{N}\\_{\\\\mathcal{F}\\_h\\^{(t, \\\\pi\\^{(t)})}}$ is defined as part of the confidence set). In addition, although such lemma refers back to the Theorem 1, there $\\\\mathcal{N}\\_{\\\\mathcal{F}, (\\\\mathcal{T}\\^{\\\\Pi})\\^T\\\\mathcal{F}}$ is not defined either, making the insight of 'log covering number blowing up' (one essential observation and motivation throughout the paper) not fully accessible.\n- Assumption 3: $d\\_\\\\text{BE}(\\\\cdot, \\\\cdot, \\\\cdot)$ is not explicitly defined, if solely based on the description in Definition 1.", "other_comments_or_suggestions": "- It is recommended to include Algorithm 3 in the main paper.", "questions_for_authors": "- What are the assumptions for state and action spaces?\n- For Equation 1, is the superscript $(t)$ missing for functions?\n- Definition 1: is the sequence of Bellman errors some specific element of the auxiliary function class that is claimed to exist in Assumption 2?\n- Theorem 1: when there are two spaces in the subscript of the covering number, i.e. $\\\\mathcal{N}\\_{\\\\mathcal{F}, (\\\\mathcal{T}\\^{\\\\Pi})\\^T\\\\mathcal{F}}$, how is it defined?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "flTCEUm8w2", "reviewer": "Reviewer_CSzS", "summary": "This paper makes the following three key contributions in the analysis of actor-critic algorithms with general function approximation:\n\n1. Proposes an actor-critic algorithm, DOUHUA, which operates under the closure under truncated sum assumption. The regret bound is established as  \n   $$\n   O\\left(\\sqrt{H^4T\\log |\\mathcal{A}|} + \\sqrt{\\beta H^4T\\text{SEC}(\\mathcal{F},\\Pi, T)}\\right).\n   $$  \n\n2. Introduces an alternative actor-critic algorithm, NORA, which does not rely on the closure under truncated sum assumption. The regret bound is derived as  \n   $$\n   O\\left(\\sqrt{dH^5T\\log T\\log |\\mathcal{A}|} + dH^3\\log T +\\sqrt{\\beta H^4T\\text{SEC}(\\mathcal{F},\\Pi, T)}\\right).\n   $$  \n\n3. Extends NORA to the hybrid RL setting and establishes a regret bound that is slightly tighter than that in the online setting.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for helpful comments and suggestions on our paper! We also thank the reviewer for believing that our paper is well-structured and clearly presented, and note that we have provided detailed discussions in the appendix in addition to the main theorems. We have addressed your questions below. Please feel free to check and let us know for any additional questions!\n\n**Experiments**\n\nWe have revised our paper and included numerical experiments based on the suggestions from reviewer TW2G in this link (https://github.com/anonymoosemoose/actorcriticicml2025/blob/main/actor_critic_figs.pdf). Given the comments you’ve made on the effort to integrate theoretical analysis with experiments, we thought that you’d appreciate them. Here is a quick summary:\n\n1. **Optimism in linear MDPs.** We compare Alg. 1 and Alg. 2 to a rare-switching version of LSVI-UCB on a linear MDP tetris task. The condition required for Alg. 1 to work holds here, as we do not clip the Q-function estimates. We see that Alg. 1 performs better than LSVI-UCB (!), and Alg. 2 achieves sqrt(T) regret even though it performs slightly worse than LSVI-UCB\n2. **Deep hybrid RL.** We compare Algs. 1H & 2H (with offline pretraining) to Cal-QL (Nakamoto et al., 2023). Alg. 2H takes a max over 10 randomly sampled actions from the policy to enhance exploration as Cal-QL does (this can be viewed as a computationally efficient version of optimism, or alternatively as approximately targeting pi^*). It outperforms Cal-QL, which outperforms 1H. Neither uses pessimism. This supports the claim that hybrid RL can avoid both pessimism and full optimism while retaining strong performance.\n\n\n**Response to Weaknesses and Questions**\n\n**Q1:  One possible improvement would be to include discussions on lower bounds and provide more intuitive insights into the relationship between general function approximation and the linear case.**\n\nThanks for raising this point! Lower bounds are sparse for classes with general function approximation. To illustrate, both Agarwal et al. (2022) and Zhao et al. (2024) appeal to lower bounds for linear MDPs within their papers on online RL with general function approximation. The result of $\\sqrt{T}$ regret is optimal in both papers, as well as ours, even though in the linear case our algorithms have a worse dependence on $d$ and $H$ (though this is not our focus – our focus is on the dependence on $T$).\n\nThe linear MDP case is a special instance of general function approximation where the Q-functions are *almost* closed under truncated sums. This allows Sherman et al. (2024) and Cassel and Rosenberg (2024) to achieve $\\sqrt{T}$ regret via bypassing the truncation and applying rare-switching to account for the bonus functions not being closed under truncated sums. We will include this discussion within the paper.\n\n\n**Q2: Additionally, it would be helpful to clarify the key differences or connections between actor-critic algorithms and general online RL algorithms.**\nActor-critic methods are a specific subset of online RL algorithms that separately learn a policy (the “actor”) and a value function (the “critic”) in real time. In contrast, general online RL encompasses any algorithm that updates its learning parameters from streaming experience. These can have actor components, critic components, both, or neither.\n\n**Other Remarks**\nWe also appreciate that the reviewer read Appendix E and found it to be helpful. We wanted to include it in the main paper, but had to omit it due to a lack of space. Given your comments, it seems like that was a short-sighted decision, and we’ll include it in the main paper within the revision.\n\n**If you believe that these revisions and changes have improved the paper, we would greatly appreciate it if you decided to increase your score**\n\n1. Agarwal et al. (2022), *VOQL: Towards Optimal Regret in Model-free RL with Nonlinear Function Approximation*.\n2. Zhong and Zhang (2023), *A Theoretical Analysis of Optimistic Proximal Policy Optimization in Linear Markov Decision Processes*\n3. Zhao et al. (2024), *A Nearly Optimal and Low-Switching Algorithm for Reinforcement Learning with General Function Approximation*\n4. Sherman et al. (2024) *Rate-Optimal Policy Optimization for Linear Markov Decision Processes*\n5. Cassel and Rosenberg (2024) *Warm-up Free Policy Optimization: Improved Regret in Linear Markov Decision Processes*\n6. Nakamoto et al. (2023), *Cal-QL: Calibrated Offline RL Pre-Training for Efficient Online Fine-Tuning*.\n7. Song et al. (2023), *Hybrid RL: Using Both Offline and Online Data Can Make RL Efficient*.", "claims_and_evidence": "To the best of my knowledge, the claims in the paper are well-supported.", "methods_and_evaluation_criteria": "This paper is purely theoretical and therefore does not involve evaluation criteria.", "theoretical_claims": "I did not verify the proofs in the paper line by line, but after going through the proofs of the main theorems (Thm 1, Thm 2), I believe there are essentially no errors. The paper provides clear guidance on the proof ideas, making it easy to understand.  \n\nAs for the other parts, including the proof of Thm 3 and the related discussions, I have also reviewed them and find the reasoning to be correct. The mathematical derivations are solid.", "experimental_designs_or_analyses": "This paper is purely theoretical and therefore does not involve experiments or analyses.", "relation_to_broader_scientific_literature": "The primary contribution of this paper is establishing the complexity under the general function approximation setting, which closely aligns with the complexity under the linear MDP setting (with $\\log |\\mathcal{F}|$ corresponding to $d^2$), thereby filling a gap in this research area.  \n\nAdditionally, the paper introduces an analytical approach that constrains the overall complexity by limiting the number of critic updates, laying a solid foundation for future research.", "essential_references_not_discussed": "To my knowledge, no.", "other_strengths_and_weaknesses": "### Strengths:  \n1. The paper is well-structured. In addition to presenting the main theorems, it includes many insightful discussions, making it very reader-friendly.  \n2. The paper provides a proof sketch of the main theorems in the main text, with a clear presentation and well-structured reasoning.  \n3. Beyond purely theoretical discussions, the paper also attempts to use the main theorems to explain empirical results. Although no validation experiments were conducted for these inferences, the effort to integrate theoretical analysis with experiments is appreciated.  \n\n### Weaknesses:  \nFrom my perspective, there are no significant flaws in the paper as a theoretical study. One possible improvement would be to include discussions on lower bounds and provide more intuitive insights into the relationship between general function approximation and the linear case. Additionally, it would be helpful to clarify the key differences or connections between actor-critic algorithms and general online RL algorithms.", "other_comments_or_suggestions": "N/A.", "questions_for_authors": "As I mentioned in the weaknesses, could the authors attempt to discuss the estimation of the lower bound, potential estimation methods, or the connections between actor-critic algorithms and traditional online RL algorithms?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "vSNdiPjP6e", "reviewer": "Reviewer_DqAM", "summary": "Actor-critic algorithms have become a cornerstone in reinforcement learning (RL), leveraging the strengths of both policy-based and value-based methods. In this paper, the authors introduce a novel actor-critic algorithm that attains near-optimal sample-complexity and regret under MDPs with low Bellman eluder dimension. The algorithm integrates optimism, off-policy critic estimation targeting the optimal Q-function, and rare-switching policy resets. They also extend their algorithm to the setting of Hybrid RL, showing that initializing the critic with offline data yields sample efficiency gains compared to purely offline or online RL.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the comments and suggestions! We are glad that the reviewer thinks our study is well motivated and our paper is well written. We provide answers to the questions below. Please let us know if you have further questions or concerns!\n\n**Revisions**\n\nMoreover, we have revised our paper to mitigate the computational inefficiency issue by leveraging an offline dataset with good coverage to bypass the need for optimism, and included numerical experiments based on the suggestions from reviewer TW2G in this link (https://github.com/anonymoosemoose/actorcriticicml2025/blob/main/actor_critic_figs.pdf). \n\n**Response to Weaknesses and Questions**\n\n**Q1:  It will be better if there is some discussion about lower bounds. Is there any lower bounds for the setting? How large is the gap if comparing the upper bounds in this paper to lower bounds?**\n\nUnfortunately, it does not seem like there exist lower bounds for general function approximation. This has impacted other works in a similar way, as for example both Agarwal et al. (2022) and Zhao et al. (2024) appeal to lower bounds for linear MDPs within their papers on online RL with general function approximation. The result of $\\sqrt{T}$ regret is optimal in both papers, as well as ours, even though in the linear case our algorithms have a worse dependence on $H$ by a factor of $H^2$ (though this is not our focus – our focus is on the dependence on $T$).  Achieving a rate that is minimax-optimal in the case of linear MDPs can be done via adapting the algorithm of Zhao et al. (2024) and making the necessary adjustments, though this is challenging and best left for future work.\n\n**Q2: The algorithm is not computationally efficient.**\n\nThanks for raising this concern! We have managed to address this within the hybrid RL setting. More specifically, recent work (Song et al., 2023) shows that in hybrid RL settings with good offline coverage, optimism (which can often be computationally inefficient)  isn’t necessary, and FQI is provably efficient. We extend this to the actor-critic setting with Algorithms 1H and 2H, corresponding to Algorithms 1 and 2 in our paper, but without computing confidence sets. When ERM is efficient, these become computationally practical. We show that:\n- Algorithm 1H achieves a regret of\n\n$$\\text{Reg}^\\pi(T)\n= O\\left(\\sqrt{H^4 T \\log|\\mathcal{A}|} + \\sqrt{\\beta^\\pi H^4 c_{\\text{off}}^*T^2/N_{\\text{off}}} + \\sqrt{\\beta^\\pi H^4 T\\text{SEC}(\\mathcal{F}, \\Pi, T)}\\right),\n$$\n- Algorithm 2H achieves a regret of \n\n$$\n\\text{Reg}^*(T)\n        = O\\left(\\sqrt{d H^5 T \\log T \\log|\\mathcal{A}|} + dH^3 \\log T + \\sqrt{\\beta^* H^4 c_{\\text{off}}^* T^2/N_{\\text{off}}} + \\sqrt{\\beta^* H^4 T  \\text{SEC}(\\mathcal{F}, \\Pi, T)}\\right)\n,\n$$\n\nwhere $c_{\\text{off}}^* $\nis the Bellman-type single-policy concentrability, $\\beta^\\pi$, and $\\beta^*$ are confidence set widths scaling with the log-covering number, and $N_{\\text{off}}$ is the number of offline samples. If $N_{\\text{off}} = \\Omega(T)$, we have $\\sqrt{T}$ regret, and we incur only an additional factor of $\\sqrt{c_{\\text{off}}^*}$ as a price to pay for omitting optimism. This improves upon Zhou et al. (2023), who required $1/\\epsilon^6$ samples.\n\n**Experimental results.**  (https://github.com/anonymoosemoose/actorcriticicml2025/blob/main/actor_critic_figs.pdf)\n\n1. **Optimism in linear MDPs.** We compare Alg. 1 and Alg. 2 to a rare-switching version of LSVI-UCB on a linear MDP tetris task. The condition required for Alg. 1 to work holds here, as we do not clip the Q-function estimates. We see that Alg. 1 performs better than LSVI-UCB (!), and Alg. 2 achieves sqrt(T) regret even though it performs slightly worse than LSVI-UCB\n2. **Deep hybrid RL.** We compare Algs. 1H & 2H (with offline pretraining) to Cal-QL (Nakamoto et al., 2023). Alg. 2H takes a max over 10 randomly sampled actions from the policy to enhance exploration as Cal-QL does (this can be viewed as a computationally efficient version of optimism, or alternatively as approximately targeting pi^*). It outperforms Cal-QL, which outperforms 1H. Neither uses pessimism. This supports the claim that hybrid RL can avoid both pessimism and full optimism while retaining strong performance.\n\nWe thank the reviewer for their comments. **If you believe that the revisions we have made have improved the paper, we would greatly appreciate it if you decided to increase your score**\n\n1. Agarwal et al. (2022), *VOQL: Towards Optimal Regret in Model-free RL with Nonlinear Function Approximation*.\n2. Zhao et al. (2024), *A Nearly Optimal and Low-Switching Algorithm for Reinforcement Learning with General Function Approximation*.\n3. Song et al. (2023), *Hybrid RL: Using Both Offline and Online Data Can Make RL Efficient*.\n4. Nakamoto et al. (2023), *Cal-QL: Calibrated Offline RL Pre-Training for Efficient Online Fine-Tuning*.", "claims_and_evidence": "Yes.", "methods_and_evaluation_criteria": "Yes.", "theoretical_claims": "The proof looks correct.", "experimental_designs_or_analyses": "NA.", "relation_to_broader_scientific_literature": "This paper is the first to achieve near optimal sample complexity and regret for actor critic algorithms under MDPs with low Bellman eluder dimension.", "essential_references_not_discussed": "NA", "other_strengths_and_weaknesses": "Strengths:\n\n1. The motivation for actor critic algorithms under general function approximation is strong.\n\n2. The paper is well-written in general.\n\nWeaknesses:\n\n1. It will be better if there is some discussion about lower bounds. Is there any lower bounds for the setting? How large is the gap if comparing the upper bounds in this paper to lower bounds?\n\n2. The algorithm is not computationally efficient.\n\nOverall, I think the strengths outperform the weaknesses. I lean towards acceptance.", "other_comments_or_suggestions": "NA", "questions_for_authors": "NA", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper addresses a central and long-standing open problem in reinforcement learning: the design of provably efficient actor-critic algorithms with general function approximation. It introduces two theoretically grounded methods—DOUHUA and NORA—that demonstrate sample efficiency and low regret under carefully stated assumptions, and significantly, without relying on traditional reachability or coverage conditions. The work is theoretically deep, builds on contemporary complexity measures like the Bellman-Eluder dimension and SEC, and offers rigorous proofs supported by supplementary discussions. While initially limited by a lack of empirical results and computational practicality, the authors have responded thoroughly in the rebuttal, offering both efficient variants and meaningful experimental comparisons. Reviewer concerns were addressed in depth, with clarification on theoretical assumptions, notation, and regret guarantees. Overall, this submission makes a substantial theoretical contribution to the RL literature, pushing the frontier of sample efficiency in actor-critic methods.
Decision: Accept (poster)