Optimistic Natural Policy Gradient: a Simple Efficient Policy Optimization Framework  for Online RL
Authors: Qinghua Liu
Gellért Weisz
András György
Chi Jin
Csaba Szepesvari
Venue: NeurIPS 2023 spotlight (2023)
Keywords: Theory of reinforcement learning
policy optimization

Abstract: While policy optimization algorithms have played an important role in recent empirical success of Reinforcement Learning (RL), the existing theoretical understanding of policy optimization remains rather limited---they are either restricted to tabular MDPs or suffer from highly suboptimal sample complexity, especial in online RL where exploration is necessary. This paper proposes a simple efficient policy optimization framework---Optimistic NPG for online RL. Optimistic NPG can be viewed as simply combining of the classic natural policy gradient (NPG) algorithm [Kakade, 2001]  with optimistic policy evaluation subroutines to encourage exploration. For $d$-dimensional linear MDPs, Optimistic NPG is computationally efficient, and learns an $\epsilon$-optimal policy within  $\tilde{\mathcal{O}}(d^2/\epsilon^3)$ samples, which is the first computationally efficient algorithm whose sample complexity has the optimal dimension dependence $\tilde{\Theta}(d^2)$. It also improves over state-of-the-art results of policy optimization algorithms [Zanette et al., 2021] by a factor of $d$. For general function approximation that subsumes linear MDPs, Optimistic NPG, to our best knowledge, is also the first policy optimization algorithm that achieves the polynomial sample complexity for learning near-optimal policies.

Optimistic Natural Policy Gradient: a Simple Efficient Policy Optimization Framework for Online RL
Qinghua Liu" Princeton University Langhual@princesn edu
Gellért Weisz Google DeepMind
András György
Google DeepMind
gellert@deepmind.c com
agyorgyddeepmind com
Chi Jin
Csaba Szepesvári
Princeton University thij@prinee inceeonooonn...ommmm.oommomoo.ce edu
Google DeepMind and University of Alberta szepesva@ualberta.co
Abstract
While policy optimization algorithms have played an important role in recent empirical success of Reinforcement Learning (RI., the existing theoretical under- standing of policy optimization remains rather limited-they are either restricted to tabular MDPs suffer from highly suboptimal sample complexity, especially in online RL where exploration is necessary. This paper proposes a simple efficient NPG for online RL. OPTIMISTIC NPG can be viewed as a simple combination of the classic natural policy gradient (NPG) algorithm [akade 2001] and optimistic policy evaluation subroutine to encourage exploration. For d-dimensional linear MDPs, OPTIMISTIC NPG is computationally efficient, and learns an e-optimal policy within Õ /e²) samples, which the first computationally efficient algorithm whose sample complexity has the optimal dimension dependence (d²). It also improves over state-of-the-ar results of policy optimization algorithms [Zneett et al. 2021 by a factor of d. For general function approximation that subsumes linear MDPs, OPTIMISTIC NPG, our best knowledge, is also the first policy optimization algorithm that achieves the polynomial sample complexity for learning near-optimal policies.
policy optimization FramewrkkOOTTMMISI
Introduction
with neural network function approxi- mation have played an important role in recent empirical success reinforcement learning (RL), such robotics [Finn al. 2016), games [Berner et al. 2019 and large language models [OpenAl| 2022 Motivated by the empirical success, the theory community made a large effort to design provably efficient policy optimization algorithms that work in the presence of linear function approximation
Policy optimization algorithms (Schulman et al. 2017 2015
[Agarwal et al. [202]] Bhandari and Russo, 2019 Liu et al., 2019 Neu et al., 2017 (oboi//bbbs--iee |Abbasi-Yadkori al. | | Agarwal al.] 20200] Zanette et al. 2022 Shani al., 2020 Cai al. | [020]] Harly works
focused on proving that policy optimization al algorithms are capable to learn near-optimal policies using polynomial number of samples under certain reachability (coverage) assumptions. [e.g..
Agarwal et al.) 2021 Bhandari and Russo 2019 Liu et al. 2019 Neu et al. [2017] Abbasi-Yadkori al. [019]. While this was good for laying down the foundations for future work, the reachability assumptions basically imply that the state space is already well-explored or rather easy to explore, which avoids the challenge of performing strategic exploration - one of the central problems in both empirical and theoretical RL.
"This work was done when QI interned DeepMind.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

Table 1: A comparison of sample-complexity results for linear MDPs.
Computationally Efficient
Policy
Algorithms
Sample Complexity
Optimization
Zanette ct al.
2020
((d+/2)
x
Jin al.
He 2022
Agarwal ct al. 2022
(00/22d224/)
X
Vagenmaker el al.
2022
Agarwal et al.
2020
O(poly(d1/ct))
V
Zanette et al.
2021
Ö((9/62)
v
Optimistic NPG (this work)
((P2/(2
To address this limitation, later works [Agarwal ct al. 2020 Zanette et al., 2021] proposed policy optimization algorithms that enjoy polynomial reachability assumption, but at the cost of either complicating the algorithm design (and analysis) with various tricks or getting highly suboptimal sample-complexity guarantees. For example, the PC-PG algorithm [Agaraal et al.) 2020), which, to our knowledge was the first policy optimization algorithm samples to learn an e-optimal policy for d-dimensional linear MDPs. That ((1/E")) samples were necessary for this task is highly unlikely. Indeed, Zanette et al. 202T] greatly improved this sample complexity to (dd (e)) at the cost of considerably complicating the algorithm design and the analysis. Moreover, are not aware of efficient guarantees of policy optimization for generic function approximation, which is rich enough to subsume linear MDPs. This motivates us to ask the following question:
guarantee without making any
for learning linear MDPs without reachability assumptions, requires (poly
Can we design a simple, general policy optimization algorithm with sharp sample-complexit guarantces in the exploration setting
In particular, we aim to achieve sharper sample complexity than Zanette et al. (202T) in the linear MDP setting, and achieve low-degree polynomial sample complexity in the general function approxi- mation setting. This paper answers the highlighted question affirmatively by making the following contributions:
Sharper rate. We propose computationally efficient policy optimization algorithm- OPTIMISTIC NPG with sample complexity
for learning e-optimal policy in an online fashion while interacting with d-dimensional linear MDP. This result improves over the best previous one [Zanette et al., 2021] in policy optimization by factor of d. Moreover, to our knowledge, this is the first computation- ally efficient algorithm to achieve the optimal quadratic dimension dependence. Before moving on, remark that previous FQI-style algorithms [Zanette et al. 2020 Jin et al.) 2 achieve the optimal sample complexity 0(d2/e" (Zanette et al. 2020 but they computationally inefficient due to the mechanism of global optimism in their algorithm
design. Several very recent works [He al. 2022 Agarwal et al. 2022 Wagenmaker et al.
2022] achieve the sample complexity O(d 122 d²*/c) using computationally efficient algorithms. Compared to our work, the aforementioned rate has worse dependence on d and better dependence e. Nonetheless, our result is better in the practically important regime where the feature dimension d is typically very large and the target accuracy is not too small. To summarize, the sample complexity of OPTIMISTIC NPG strictly improves the best existing policy optimization algorithms and is not dominated by that of any existing computationally efficient algorithm.
By "exploration setting". we mean setup where there is no simulator nor reachability assumption and learner can only influence the evolution of environmental states by taking actions.

---

To our best knowledge, this paper also achieves the first polynomial sample-come complexxy guarantee for policy optimization under general function approximation.
Simple on-policy algorithm. At high level, OPTIMISTIC NPG is almost on-policy version of natural policy gradient (NPG) [akade 2001] with Boltzmann policies that use linear function upproximation for optimistie action-value estimates. By "on-policy", mean the consition-rewar data used to improve the current policy are obtained exactly by executing the current policy. However, the algorithm has a tuneable parameter (denoted by m in Algorithm T) that allows it to reuse data sampled from earlier policies. By using such data, the algorithm becomes off-policy. The optimal choice of the tuneable parameter is dictated by theoretical arguments. Interestingly, our analysis shows that even the purely on-policy version of the algorithm (i.e., set m in Algorithm I enjoys well-controleed sample complexity of ((dP/et) To the best of our knowledge, this is the first time an on-policy method is shown to have polynomial sample complexity in the exploration setting, given that all previous policy optimization or Q-learning style or model-based algorithms
[e.g.. Jin et al. 2020 Zanette et al. 2020 2021 Agarwal et al. 2020 Cai et al. 2020 Shani
et al. 2020 ctc] are off-policy.
New proof techniques. To achieve the improved rate, we introduce several new ideas in the proof, including but not limited to (a) exploiting the softmax parameterization of the policies to reuse data and improve sample efficiency (Lemma 3), (b) controlling on-policy uncertainty (Lemma 4) instead of cumulative uncertainty as in previous off- off-policy works, and (c) using a bonus term that is smaller than those in previous works by a factor of vd (see Lemma 2 and the discussions that follow).
1.1
Related works
Since this paper studies policy optimization algorithms in the setting of linear MDPs, below we restrict our focus to previous theoretical works on either policy optimization or linear MDPs.
Policy optimization. This work is inspired by and builds upon two recent works (Shani et al. 2020 Cai et al.] 2020] that combine NPG with bonus- based optimism to handle exploration. In terms of algorithmic design, this paper (OPTIMISTIC NPG) utilizes on- on-policy fresh data for value estimation
while Shani et al. [2020] Cai et al.
(020) are off-policy and reuse all the historical data. In terms of theoretical guarantees, Shani et al.
2020 and Cai et al. [2020) only study tabular MDPs and linear
respectively. while this paper considers the more challenging setting of linear MDPs [Jin et 2020] (in our view, linear MDPs are more challenging as there the number of model parameters scale with the number of states). We remark that due to some subtle technical challenge, so far it still remains unknown whether is possible generalize the analysis of Cai et al. (2020) to handle linear MDPs. Agarwal et al. 2020), Zanette et al. [2021] derive the first line of policy optimization results for RL linear MDPs without any reachability- (or coverage-) style assumption. Compared to Agarwal et al. [2020). Zanette et al. [2021]. our work considers the same setting but designs a simpler algorithm with cleaner analysis and sharper cample-complexity guarantee. Nevertheless, we remark that in certain model-misspecifccat
mixture MDPs [Zhou et al., 2021
settings, the algorithms of Aggawaa et al. [2020] Zanette et al. [202T] can potentially achieve stronger guarantees. Since we Tocus on the spel-speeifeed setting (that is, the environment is perfectly modeled by a linear MDP), we refer interested readers to Agarwal et al. (2020) for more details. Finally, there have been a long line of works [e.g.. Agarwal et al.) 202 Bhandari and Russo 2019 Liu et al. 2019 Neu et al., 2017 Abbasi Yadkorr et al. 2019, etc that study policy optimization under reachability (or coverage) assumptions, which eliminates the need for performing strategic exploration. Throughout this paper we do not make any such assumption and directly tackle the exploration challenge.
Linear MDPs. For linear MDPs, Jin et al. 2020 proposed a computationally efficient algorithm (LSVI-UCB) with O(d²/e² sample complexity. Later on, Zanette et al. (2220) utilized the idea of global optimism to obtain the optimal sample complexity (dd² /c2) at the cost of sacrificing computational efficiency. Recently, HHe et al. (2022). Agarwal et al.) (2022). Wagenmaker et al.] [202) designed new computationally efficient algorithms that can achieve Ó / + /e) sample complexity. Compared to the above works, the sample complexity of OPTIMISTIC NPG is not strictly worse than that of any known computationally efficient algorithm. In fact, the only computationally efficient method to achieve the optimal dimension dependence. Nonetheless, for
3

---

learning a near-optimal policy with vanishing suboptimality e, the current sample complexity of OPTIMISTIC NPG loose by a factor of e
2 Preliminaries
MDP. We consider the model of episodic Markov Decision Processes (MDPs). Formally, an MDP defined by tuple (S, R, H) where S denotes the of states, denotes the set of actions, both of which are assumed to be finite. P
heE denotes the set of transition probability functions so that PA (s' 8, a) is equal to the probability of transitioning to state s' given that action taken at state and step h, R (Ra, I (E(H)] denotes the collection of expected reward functions so that R2, (s, a) is equal to the expected reward be received if action is taken at state and step h, and H denotes the length of each episode. An agent interacts an MDP in the form of episodes. Formally,
assume without loss of generality that each episode always starts from a fixed initial state 81. At the hh step of this episode, the agent first observes the current state Sh, then takes action an and receives reward I'A Sh, (n) satisfying
(sr, an) 8h, anl (shs an)
After that, the environment transitions
Sh+1 PA 8h, an).
The current episode terminates immediately once Fy is received. Throughout this paper, we assume and R are unknown the learner.
Linear MDP. A d-dimensional linear MDP Jin et al. 2020 is defined by two sets of feature mappings, Hon S (8 x A + Rd) and {FA heEm (S + ) and set of vectors (wj)e S IRd so that the transition probability functions can be represented as bilinear functions of feature mappings hert and { he(m) and the reward functions can be represented as linear functions of (dx (eeM. Formally, have that for all (s, s') E S x A x S:
Pn | s, a) = (øn(s, a), (s))) Rn
(sn(s, a), wh)-
For the purpose the regularity, linear MDPs also require that max | (s, a)lle I 1, h,s,a
max
| S Vd.
h
and for any function Va+1 : S [0, 1].
<
Throughout this paper, we assume only (ontne is available to the learner while {1hn Jetee and {wi hee(r not.
Policy and value. A (Markov) policy is a set of conditional probability functions π = {TH heeeH] so that (-( s) e AA gives the distribution over the action set conditioned on the current state s step h. We define the V-value functions of policy by (V, ]KE[H) (S R) so that V,, (s) is equal to the expected cumulative reward an agent will receive she follows policy æ starting from state and step h. Formally,
H
V =
(sw' ax) 5h = s, ax ~ Tw sh4 ~ PA(- sh ah) =
Σ
where the expectation with respect to the randomness of the transition, the reward and the policy. Similarly, we can define the Q-value functions of policy by [QT [nj S (S x A A R) so that (T, a) is equal to the expected cumulative reward agent will receive if she follows policy starting from taking action a at state and step h. Formally,
H
(7 a) = E
The (SM', aw) (sh; or)) = (8, a), an ~ (sw) Sh41 ~ PA( sh dh)) A
Σ

---

We denote by x== he the optimal policy such that x* E argmax, V (s) for all (s, h) E S x [ By backward induction, one can easily prove that there always exists an optimal Markov policy, For simplicity of notations, we denote by V = V and Q7 = Q" the optimal value functions. Note that given an MDP, the optimal value functions are unique despite that there may exist multiple optimal policies.
Learning objective. The objective of this paper is to design efficient policy optimization
algorithm to learn an c-optimal policy π such that VT' (81) 2 (81) c. Here the optimality is only measured by the value at the initial state 81, because (a) each episode always starts from 81, and (b) this paper studies the online exploration setting without access to a simulator, which means some states might be unreachable and learning optimal policies starting from those states is in general impossible.
3 Optimistic Natural Policy Gradient
In this section, we present the algorithm OPTIMISTIC NPG (Optimistic Natural Policy Gradient) and its theoretical guarantees.
3.1
Algorithm
The pseudocode of OPTIMISTIC NPG is provided in Algorithm consists of the following three key modules.
T At a high level, the algorithm
Periodic on-policy data collection (Lines 46): Similarly to the empirical PPO algorithm [Schulman et al. 2017). OPTIMISTIC NPG discards all the old data, and executes the current policy x² to collect batch of fresh data D* after every m steps of policy update. These data will later be used to evaluate and improve the policies in the next m steps. Noticeably, this on-policy data mechanism is very different from most existing works in theoretical RL, where they either need to keep the historical data or have to rerun historical policies to refresh the dataset for the technical purpose of elliptical potential arguments in proofs. In comparison, OPTIMISTIC NPG only uses fresh data collected by the current (or very recent) policy, which resembles practical policy optimization algorithms such as PPO [Schulman et al. 2017] and TRPO [Schulman al. 2015).
Optimistic policy evaluation (Line 8 Given the above collected dataset D we estimate the value functions of the current policy nh by invoking Subroutine OPE (optimistic policy evaluation). In Section 4
we show how to implement Subroutine OPE for tabular MDPs, linear MDPs and RL problems of low eluder dimension.
Policy update (Line 9): Given the optimistic value estimates (Q of T. OPTIMISTIC
NPG performs one-step mirror ascent from * (- | s) with gradient (x, :) to obtain TA k+1(( efficient way, because by the update rule of mirror ascent of |) x exp(n Σ (%,(s )))
(- s) each (h. Importantly, this step can be implemented in a computationally
we only need to store mejhn from which any o/( s) can be computed on the fly.
3.2 Theoretical guarantee
OPTIMISTIC NPG is a generic policy optimization meta meta- algorithm. and we can show it provably learns optimal policies as long as subroutine OPE satisfies the following condition.
Condition 1 (Requirements for OPE). Suppose parameter m and n in OPTIMISTIC NPG satisfy m S (n) Then with probability at least 1 5, OPE(**, DD) returns (Qhheem S (S x A [0, HT) that satisfy the following properties for all k E [K].
(IA) Optimism: For all (s, h) E S x Ax [H]
2h a) (T=" 2 (n)))ss,a)
where (Ts,) Rn(s, + E (s (''s',o ,a)) | s' ~ Pn(: s,a), a' (s))
5

---

Algorithm OPTIMISTIC NPG
1: input: number of iterations K, period of collecting fresh data m, batch size N, learning rate
2: initialize: for all (h, s) E [M] x set m. Uniform(A)
3: for k 1..... K do
4: if :: = 1mod m) then
D < (N fresh trajectories Lid x²}
5:
6: else
7:
D - Dk-1
8:
(Q hEEHH + OPE(=*, DD)
for all (h, s) E [H] x update 1e+1(, (- s) x T/( (s) exp(n (x(s,))
9:
10:
output: π ouu that is sampled uniformly random from (=* ]ee[K]
(IB) Consistency: There exists an absolute complexity measure L E IR such that
((1) - Vi*" (81) S v (L/N) x log (NKL/0), where ((1) E ( an - ((())
Condition (IA) requires that the Q-value estimate returned by OPE satisfies the Bellman equation under policy ' optimistically. Requiring optimism is very common in analyzing RL algorithms, most algorithms rely on the principle of optimism in face of uncertainty handle exploration. Condition (IB) requires that the degree of over-optimism
initial state is roughly of order /I/N with respect to the number of samples N. This is intuitive since as more data are collected from policy n² some policy similar n (as enforced by the precondition value estimate at the initial state should be more accurate. In Section 4 we will provide concrete instantiations of Subroutine OPE for tabular MDPs, linear MDPs and RL problems of low eluder dimension, all of which satisfy Condition I with mild complexity measure L.
(n/lf²)-1), the
Under Condition I have the following theoretical guarantees for OPTIMISTIC NPG, which prove in Appendix
Theorem 1. Suppose Condition holds. In Algorithum 1 [
if we choose
H log (4)) = L Logg (LK/8)
m S θ (
-
7= H3
22
22
then with probability least 1/2, nout O(e)ooptimal.
Below emphasize two special choices of m (the period of sampling fresh data) in Theorem
When choosing m 1, OPTIMISTIC NPG is purely on-policy as it only uses data sampled from the current policy to perform policy optimization. In this case, the total sample complexity is
# iteration
K x
LH -
period of sampling batch size
= 6
which, to our knowledge, the first polynomial sample complexity guarantee for purely on-policy algorithms.
When choosing m = [H]e], we obtain sample complexity
# iteration
K N = LH
batch size
period of sampling
which improves over the above purely on-policy version by factor of H/ e. In Section 4.2 will specialize this result to linear MDPs to derive sample complexity that improves the best existing one in policy optimization (Zanette et al. 2021 by a factor of d.
Finally we remark that for cleaner presentation, we state Theorem for fixed, constant failure probability. However, the result is easy to extend to case when the failure probability some arbitrary value of 8 E 1) at the expense of increasing the sample complexity by a factor of 1og(1 one simply need to run Algorithm for log(1/5) times, estimate the values of every output policy accuracy and then pick the one with the highest estimate.

---

Subroutine Tabular (P D)
required parameter: a
2: split D evenly into H disjoint subsets DI...., DH
3: compute empirical estimate (PP Ra) of the transition and reward at step h by using D/.
4: set V (s) +- 0 for all E
5: for h H:
6: for all (8,a) E S x A, compute
(s, a) t Σ DDD, 1((sh, = (s,a))
and define
(x = min (H + 1, E B) (V+ + R a) (s,
Vn(s)= Ea-rr [Q((s,))
with bonus function
(s, = (J)a(s, + +1)-1/2
7: output 1H
Examples
In this section, we implement subroutine OPE for tabular MDPs, linear MDPs and RL problems of low cluder dimension, and derive the respective sample complexity guarantees of OPTIMISTIC NPG.
4.1 Tabular MDPs
The implementation of tabular OPE (Subroutine I is rather standard: first estimate the transition and reward from dataset D, then plug the estimated transition-reward into the Bellman equation under policy π to compute the Q-value estimate backwards. And to guarantee optimism, we additionally add standard counter-based UCB bonus to compensate the error in model estimation. Formally, have the following guarantee for tabular OPE.
Proposition 1 (tabular MDPs). Suppose we choose = θ (ogg in Subroutine then Condition holds with L = SAHH
By combining Proposition [ with Theorem we prove that OPTIMISTIC NPG with Subroutine learns an e-optimal policy within (KN/m) = ( episodes for any tabular MDP. This rate is strictly worse than the best existing result O (AAA in tabular policy optimization [Wu et al. 2022.. Nonetheless, the proof techniques in (Wu et al, 2022 specially tailored to tabular MDPs and it is highly unclear how to generalize them to linear MDPs due to certain technical difficulty that arises from covering prohibitively large policy space. In comparison, policy optimization framework easily extends to linear MDPs and provides improved sample complexity over the best existing one, as is shown in the following section.
!
4.2 Linear MDPs
We provide the instantiation of OPE for linear MDPs in Subroutine At high level, linear OPE computes upper bound Q for Q" by using the Bellman equation under policy I backwards from step H step while adding bonus to compensate the uncertainty of parameter estimation. Specifically, the step of ridge regression (Line utilizes the linear completeness property of linear MDPs in computing Q2 from V V4+1 which states that for any function V VA+1* S + R. there exists On E Rdd so that (s, a), On) Ra a) + (B)=Pa())e..) [V 1+ (s')] for all (s, a) E S x A. And in Line 6 we add elliptical bonus 6x (s, a) to compensate the error between our estimate 0, and the groundtruth 6% so that we can guarantee (s. a) 2 (T, (T a) for all (s, a, h) with high probability..
0, = argming
Σ
(nh J rh Tnn--Vtt1-0 (V+t(Sh+1)) + +11011
(I)
7

---

Subroutine 2 Linear (PE(T, D)
required parameter: a, A
2: split D evenly into H disjoint subsets Di,..., DH
3: set V [+) <- 0 for all s S
4: for h= H do
5: perform ridge regression according to Equation 1
6: compute covariance matrix
Σn (n),e (n(Sn, @n) (sh,, (n))
and define
Qn (s. a) = Truncatero.ir (10n. (s, a)) + by (s,
(s(s) (awrn(()s)) (Q(s.
with bonus function
(s, || ()) +Aax)))
7: output {Qm)k=
Subroutine 3 General OPE(T, D)
required parameter: ,3
2: split !D evenly into H disjoint subsets Di,..., . DH
3: set V (+) <- 0 for all S
4: for = H do
5: for (s, a) E S A do
6:
construct confidence set
Bn (Jn E Fh: Lu (Dn, fi)
min (D(D,, RrEFi
with loss function defined
(D),
Σ
(S(sh, an) Th (n+1($n+1))
(sh an (hh:h1))))
7:
compute
(x = SUp, Jn (n(88
Vn(s)= = Eanas 8) Qg (s)
LH 8: output (Q
Proposition 2 (linear MDPs). Suppose choose À and = (dlogg((N)) in Subrou- then Condition 7 holds with L H3.
tine 2
By combining Proposition with Theorem we obtain that (KN/m)= (df episodes are sufficient for OPTIMISTIC NPG to learn c-optimal policy, improving upon the state-of-the-art policy optimization results [Zanette et al. 2021] by factor d. Notably, this also the first computationally efficient algorithm achieve optimal quadratic dimension dependence for learning linear MDPs. The key factor behind this improvement is OPTIMISTIC NPG's periodic collection of fresh on-policy data, which eliminates the undesired correlation and avoids the union bound over certain nonlinear function class that are commonly observed in previous works. Consequently. OPTIMISTIC NPG uses a bonus function that is vd times smaller than in previous works [e.g.. Jin al. 2020 For further details on how we achieve this improvement, we refer interested readers to Appendix specifically Lemma
4.3 General function approximation
Now we instantiate OPE for RI. with general function approximation. In this setting, the learner is provided with function class = x ... Fu approximating the Q values of polices, where F. (S x A [0, H)).

---

General OPE. The pseudocode is provided in Subroutine 3 At each step h E [H] general OPE first constructs confidence set B₁, which contains candidate estimates for 7 Q (Line 6). Specifically, Ba consists of all the value candidates fi. E Fh whose square temporal difference (TD) error on dataset D/ is no larger than the smallest one by an additive factor 3. Such construction can be viewed as a relaxation of the classic fitted Q-iteration (FQI) algorithm which only keeps the value candidate with the smallest TD error. In particular, if we pick 8 0. BA collapses to the solution of FQI. Equipped with confidence set B,. general OPE then perform optimistic planning at every as E S x A by computing Qn, (s. a) to be the largest possible value that can be achieved by any candidate in confidence set B₁, (Line (7). We remark that general OPE shares similar algorithmic spirit to the GOLF algorithm [Jin et al. 2021]. The key difference that GOLF is a purely value-based algorithm and only performs optimistic planning at the initial state while general OPE performs optimistic planning at every state and is part of a policy gradient algorithm.
Theoretical guarantec. To state the main theorem, we need to first introduce two standard concepts: value closeness and eluder dimension, which have been widely used in previous works that study RL with general function approximation.
Assumption 1 (value closeness (Wang al. 2020)). For all h [H] and V441 : [0, H). Ty VA+1+ E Fv where [Tx Vi+1ass()s,) (s, a) 1 s' ~ PP(- P s.a)..
Intuitively, Assumption D can be understood requiring that the application of the Bellman operator Tr to any V-value function V4+1 results in a function that belongs to the value function class Fi This assumption holds in various settings, including tabular MDPs and linear MDPs. Furthermore, it is reasonable to assume that value closeness holds whenever the function class F has sufficient expressive power, such as the class of neural networks.
Definition 1 (eluder dimension [Russo and Van Roy 2013 ). Ler G be a function class from X to R and O. We define the c-eluder dimension of G. denoted (9. to be the largest L E N+ such that there exists II,...,,I,, FT, E X and gı, ....I......... Exs)( g((x:))2² < bbu g((21)) g/()))) 2
-1, 92. E 9 satisfying: for all E [L]
At a high level, eluder dimension dg(g, measures how many mistakes we have to make in order to identify an unknown function from function class G accuracy e, in the worst case. It has been widely used as a sufficient condition for proving samplc-efficiency guarantee for optimistic algorithms in RL with general function approximation, e.g., Wang et al. 2020 Jin et al. 2021
Now we state the theoretical guarantee for general OPE.
Proposition 3 (general function approximation). Suppose Assumption 7
holds and holds with L. =
choose B = θ (H2 log([F(NK/6)) in Subroutine 3 then Condition
H log( (l) maxx (F 1/N).
Plugging Proposition 3 back into Theorem we obtain that (KN/m) = Ó(dg (og(
episodes sufficient for OPTIMISTIC NPG to learn an c-optimal policy, which to our knowledge is the first polynomial sample complexity guarantee for policy optimization with general function approximation.
5 Conclusions
We proposed a model-free, policy optimization Stforithm-OPTMMS NPG for online RL and analyzed its behavior in the episodic setting. In terms of algorithmic design, it is not only considerably simpler but also more closely resembles the empirical policy optimization algorithms (c.g.. PPO, TRPO) than the previous theoretical algorithms. In terms of sample efficiency, for d-dimensional linear MDPs, it improves over state-of- withhhh-rt art policy optimization algorithm by a factor of d, and is the first computationally efficient algorithm to achieve the optimal dimension dependence. To our best knowledge, OPTIMISTIC NPG is also the first sample-efficien policy optimization algorithm under general function approximation.
For future research, we believe that it is an important direction to investigate the optimal complexity for using policy optimization algorithms to solve linear MDPs. Despite the optimal dependence on dimension d, the current sample complexity of OPTIMISTIC NPG is worse than the optimal rate by a factor of 1/c. It remains unclear to us how to shave off this 1/c factor to achieve the optimal rate.

---

Acknowledgement
Qinghua Liu would like to thank Yu Bai for valuable discussions. This work was partially supported by National Science Foundation Grant NSF-11S-2107304.
References
Yasin Yadkori, Dávid Pál, and Csaba Szepesvári. Improved algorithms for linear stochastic bandits. Advances in neural information processing systems, 24, 2011.
Yasin Abbasi-Yadkori, Peter Bartlett, Kush Bhatia, Nevena Lazic, Csaba Szepesvari, and Gellért Weisz. Politex: Regret bounds for policy iteration using expert prediction. International Conference Machine Learning, pages 3692-3702. PMLR, 2019.
Alekh Agarwal, Mikael Henaff, Sham Kakade, and Wen Sun. Pe-pg: Policy cover directed exploration for provable policy gradient learning. Advances in neural information processing systems, 33: 13399-13412, 2020.
Alekh Agarwal, Sham M Kakade, Jason D Lee, and Gaurav Mahajan. On the theory of policy gradient methods: Optimality, approximation, and distribution shift. Mach. Learn, Res., 22(98): 1-76, 2021.
Alckh Agarwal, Yujia Jin, and Tong Zhang. VOqL: Towards optimal regret in model-free RL with nonlinear function approximation. arXiv preprint urXiv:22/2.0660 2022.
Christopher Berner, Greg Brockman, Brooke Chan, Vicki Cheung, Przemyslaw Debiak, Christy Dennison, David Farhi, Quirin Fischer, Shariq Hashme, Christopher Hesse, Rafal Józefowicz, Scott Gray, Catherine Olsson, Jakub Pachocki, Michael Petrov, Henrique Pondé de Oliveira Pinto, Jonathan Raiman, Tim Salimans, Jeremy Schlatter, Jonas Schneider, Szymon Sidor, llya Sutskever, Jie Tang, Filip Wolski, and Susan Zhang. Dota with large scale deep reinforcement learning. arXiv preprint arXiv: arXiv: /9/2.0660, 2019.
Jalaj Bhandari and Daniel Russo. Global optimality guarantees for policy gradient methods. arXiv preprint arXiv: 1906. 01780, 2019.
Qi Cai, Zhuoran Yang, Chi Jin, and Zhaoran Wang. Provably efficient exploration in policy optimiza- tion. In International Conference on Machine Learning, pages 1283-1294. PMLR, 2020.
Chelsea Finn, Sergey Levine, and Pieter Abbeel. Guided cost learning: Deep inverse optimal control via policy optimization. In International conference on machine learning, pages 49-58. PMLR. 2016.
Jiafan He, Heyang Zhao, Dongruo Zhou, and Quanquan Gu. Nearly minimax optimal reinforcement learning for linear Markov decision processes. arXiv preprint arXiv:2212.06113. 2022.
Chi Jin, Zhuoran Yang, Zhaoran Wang. and Michael Jordan. Provably efficient reinforcement learning with linear function approximation. In Conference on Learning Theory, pages 2137-2143, PMLR, 2020.
Chi Jin, Qinghua Liu, and Sobhan Miryoosefi. Bellman eluder dimension: New rich classes of RL problems, and sample-efficient algorithms. Advances in neural information processing systems, 34:13406-13418 2021.
Sham M Kakade. A natural policy gradient. Advances in neural information processing systems, 14, 2001.
Boyi Liu, Qi Cai, Zhuoran Yang, and Zhaoran Wang. Neural proximm/uutt region policy optimization attains globally optimal policy. arXiv preprint arXiv: 11119990000006,, 10306, 2019.
Gergely Neu, Anders Jonsson, and Vicenç Gómez. A unified view of entropy-regullrizee Markov decision processes. arXiv preprint wxXiv:1705.077900 2017.
OpenAl, ChatGPT: Optimizing language models for dialogue, 2022. URL. URR.https:: wttph:ttp////cc httttst://ppeaa.... com/
10

---

Daniel Russo and Benjamin Van Roy. Eluder dimension and the sample complexity of optimistic exploration. Advances Neural Information Processing Systems, 26, 2013.
John Schulman, Sergey Levine, Pieter Abbeel, Michael Jordan, and Philipp Moritz. Trust region policy optimization. In International conference machine learning, pages 1889-1897. PMLR, 2015.
John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms. arXiv preprint
2017.
Lior Shani, Yonathan Efroni, Aviv Rosenberg, and Shie Mannor. Optimistic policy optimization with bandit feedback. In International Conference on Machine Learning, pages 8604-8613, PMLR, 2020.
Andrew Wagenmaker, Yifang Chen, Max Simchowitz, Simon Du, and Kevin Jamieson. Reward-free RI. is no harder than reward-aware RI in linear Markov decision processes. In International Conference on Machine Learning, pages 22430-22455 22456. PMLR, 2022.
Ruosong Wang. Russ Salakhutdinov, and Lin Yang. Reinforcement learning with general value function approximation: Provably efficient approach via bounded eluder dimension. Advances in Neural Information Processing Systems, 33:6123-6135, 2020.
Tianhao Wu, Yunchang Yang, Han Zhong, Liwei Wang, Simon Du, and Jiantao Jiao. Nearly optimal policy optimization with stable any time guarantee. In International Conference Machine Learning, pages 24243-24265. PMLR, 2022.
Andrea Zanette, Alessandro Lazaric, Mykel Kochenderfer, and Emma Brunskill. Learning near optimal policies with low inherent Bellman error. In International Conference on Machine Learning, pages 10978-10989. PMLR, 2020.
Andrea Zanette, Ching-An Cheng, and Alekh Agarwal. Cautiously optimistic policy optimization and exploration with linear function approximation. Conference on Learning Theory, pages 4473 4525. PMLR, 2021.
Dongruo Zhou, Quanquan Gu, and Csaba Szepesvari. Nearly minimax optimal reinforcement learning for linear mixture Markov decision processes. In Conference on Learning Theory, pages 4532-4576. PMLR, 2021.

---

A Proof of Theorem 1
Recall in Algorithm
π out is sampled uniformly at random from { ]Æ([K] so we have
(11) - Vi (i1)
K K
[1 - (si)
((() - [-(11]
(s1)
(81) VF (01)
Term (1)
Term (II)
To control Term (I) we import the following generalized policy difference lemma from Shani et al.
2020
Cai et al. 2020
Lemma (generalized policy-differenn lemma). For any policy and ls [K],
(s1 (i
H
Bes nix (Iral (..1(18)) |8p) -xh( |8x). (h(sn: M))
h=1
The Qh(sn. (Tx" (Tx' (5tt))sn
(sn
By invoking Lemma 1 with = =r', we have
K
1
(i1( - vi(())
Term(1)- =
K
k=1
ah( I s), 2h(,,
(Th (Te" oh(s,a))
< H max h,
H max h
(2)
K
0
H log |A|
+ 17733)
+ H max h,s,a
(T Q eh)
nRK
where the second inequality follows from the standard regret bound of online mirror ascent. By Condition (IA). the second term on the RHS of Equation (2 is upper bounded by zero. So we have
Term(T) S H log |A|
+ +
nk
As for Term (II), we can directly upper bound it by Condition
IB which gives:
TeIm H (L/N) x L/g
We complete the proof by plugging in the choice of K, N,
B Proofs for Examples
In this section, we prove the three instantiations OPE in Section 4 satisfy Condition I with mild complexity measure L. The proofs of the lemmas used in this section can be found in Appendix C
B.1 Proof of Proposition 2 (linear OPE)
We start with the following lemma showing that Q) is an optimistic estimate of Th"" TT" degree of over-optimism can be bounded by the bonus function.
Q and the
12

---

Lemma 2 (optimism of value estimates). Under the same choice of and a as in Proposition with probability least 6: for all (k, a) E [K] [ A:
s U The Q 1 a) (s, a);
where (6% heem are the bonus functions defined in Line
Subroutine linear OPE(T*, D*).
Importantly, Lemma holds with a bonus function that is smaller by a factor of v than the typical one used in linear function approximation [e.g.. Jin et al.) 2020), which is key obtaining the optimal dimension dependence. The main reason that this smaller bonus function suffices that we recollect fresh samples every iterations and split the data (Line 2 Subroutine 2 to eliminate the correlation between different steps h E [H]
Lemma 2 immediately implies that Condition
(IA) holds. Below we prove Condition (IB)
the definition of v and the Bellman equation under policy
By the second inequality in Lemma n², one can show
"
" Σ 4=1
O. V((s)) (31) = Σ Ex 1(2h -Th Th" (sn1)ssn and S B (bh an)]- h=1
(3)
Denote by to the index of the last iteration of collecting fresh data before the 4 iteration. By exploiting the softmax parameterization structure of { ] one can show that the visitation measure over state-action pairs induced by executing policy x is actually very close to the one induced by x'* in the following sense.
Lemma 3 (policy Lipschitz). Suppose we choose 1) and m such that 1ym S 1/H², then for any k E N and any function f S x A R+:
E [f an)l θ (E (f(nn, an))).
By combining Lemma 3 with Equation 1 and noticing that b/: = -%% we have
(*1)) VT 50
Σ KE(R]
max Exi. (M axa)) O
E (/)t (8h: (ni))))))))
REEK]
Since the bonus function 1 is defined by using the dataset D collected from executing policy x't,, one could expect its average under < should be rather small when the batch size is large enough, as formalized in the following lemma.
Lemma 4 (on-policy uncertainty). Let be arbitrary policy and X 2 1. Suppose sample (18 ag) J i.i.d. from æ. Denote En EE= (3),), ah ( af.). Then with probability at least 1 8:
dog (N/8))
E (o (sk, an an))l Manddr-]
N
As result, by Lemma 4 and the definition of 6,, we have that with probability at least for all A E [K].
H B [b (sh, an) = Hdy
log (NKK)))
N
where in applying Lemma we use the fact (D/ together, we get
N/H due data splitting. Putting all pieces
d 3 log 2 (KNH/8)
vi(s))- - -F 5o
N
As result, Condition
IB) holds with L H3
13

---

B.2 Proof of Proposition (tabular OPE)
The proof follows basically the same as that of Proposition 2 The only modification needed is to replace Lemma and by their tabular counterparts, which we state below.
Lemma (optimism of value estimates: tabular). Under the same choice of as Proposition 7 with probability at least 1 - 5: for all (k, h, 8, a)) [K] x [H] x S x A:
0 @ -T
Qh+1))s T
(s, a):
where (Unthel are the bonus functions defined in Line Subroutine 1 Iabularr OPE(T", . Lemma (on-policy uncertainty: tabular). Let π an arbitrary policy. Suppose we sample
(s8 JN)NN In ii.d from n. Denote Jn(s, a) = Ei= 1((5), og,) = (s.a)). Then with probability
at least -: 6:
= 0 (
SA (Alog(NN/))
(a Jorz
(V (n(s,a)+1 +1
N
B.3 Proof of Proposition (general OPE)
The proof follows basically the same as that of Proposition [ The only modification needed is to replace Lemma 2 and by their general counterparts, which we state below.
Lemma 7 (optimism of value estimates: general). Suppose Assumption hoods. There exists an absolute constant e such that with probability at least 1-8: 8: for all (k, h 8, a) E [K] [M] x A:
sup In.REEF
fn(s,a) f/(s,a)
0 S (Q Th" Qh (s S bn,s,,, =
-T=
Σ
(fu(sh on) fh (sh, a=))² S cB
S.f.
(5h (B),,n)
Lemma 8 (on-policy uncertainty: general). Let т be an arbitrary policy. Suppose we sample Dr {sh ] i.i.d. from Then with probability least 6:
E )a (s, a, Dn)] = ( (
dg (1/N, Fi)
log(1/8)
+ H
N
N
C Proofs of Lemmas
C.1 Proof of Lemma
Lemma I is immediate consequence of Lemma 4.2 in [Cai et al. 2020 Lemma in (Shani ct al. 2020].
C.2
Proof of Lemma
Let us consider fixed pair hk [K] [M]. Recall Q is defined
(x, a) Truncate H - (10) dn (s, + (s)
where
0 argming
Σ
(n) -V -V + x11011
(RRSk L)E
b% (s. a) = x || +
and 1/
Σ
o( (o(s), TT
(ED,
By the standard linear completeness property of linear MDPs Jin et al. 2020 there exists of such that |10/112 < H Hd and
(0n(s, a), 0%) = R2 (8, + ES 0.0)
V [
for all (s, E ESx A.
14

---

Therefore, to prove Lemma it suffices to show that for all (s, a)
(ōn a), o 0
by (s.
To condense notations, denote by ((s) o/ r/ s // 1 the tuples in Dr. By the definition of ridge regression,
(0n a), 8 0%)
( (don(t,a) a), (2% + (laxa)
M
Σ dn (sh. ah) (rh + V (hillsh41) on of) )f - 20R
(s +s +Naxn)
Σ (nh ah) (rh + -
ah) TO))
HVV
where the inequality follows from | llst ( Aaax)) S vA H Hvd. It remains to bound the first term in the bracket. Now here comes the key observation that helps shave off the vd factor from the bonus.
Observation 1. DÍ, and Vh+1 are independent conditioning on Th where by denotes the index of the last iteration of collecting fresh data before the Eth iteration.
To see why, recall that after obtaining Di Algorithm 2 splits it evenly into H disjoint subsets (D), ) and then only uses (D 1H
/h==++1 for evaluating and improving { 1H =1'=h+1 for E
[2 + m - 1]. As a result, {V (V4+1H 1+11ll= + (including V 1 is independent of D D conditioning on " By the concentration of self-normalized processes (Abbasi- Yadkori et al. 2011 we conclude that with probability at least 1 - d: for all (k, h)) [K] x [
on (6h ai) (rh V (5h1))) @n of TO))
0 sO(Hddlow dlog (ooolog(MHH88))
(2)) +Aaxa))-
C.3 Proof of Lemma 3
We first introduce the following two auxiliary lemmas about the lipschitzness continuity of softmax paraterization.
Lemma There exists an absolute constant such that for any policy æ. satisfying žt (a & Ta(a s) exp(Ln a)) where {La(s, a) hreim is set of functions from S x A to [-1/H, H, 1/H,, we have that for any TH == (51, ai....... 8H, aH) E (S A)
pd (TH) Sex (TH).
Proof of Lemma 9 By using the relation between and and the normalization property of policy n, we have that for any (h, a):
(a 3) exp(Ln(s,
( (a 8) = En Th (a' 8) exp(Ln
Th(a 8) x cxp(1/H)
< En (a'a' 8) exp(
= (a 8) x exp(2/H) < nh 8) x (1+ 0(1)
H
15

---

Therefore, for any == ($1, 01 ........ 8H,
H 1-1
p (TH)
(x
8h: an)
n (an s8))
H
x(+
0(1)
sh. sh)an) (s
x
II hmm
Th (an (9h)
H
-011
II
Pa(SN+1
Sh, an)
II
Ta(an
8n)
O(1) IPT (TH).
Lemma 10. Let u.v v be two probability densities defined over X such that l1w/v|l S a, then have that for any function f X - Rt, Eulf(x)] & (Evlf(x))
Proof of Lemma TO By definition, Eg]((x)] (IEE)](()))
(L((()ll s {L((((()())
By the update rule of NPG, we have
The () n (-1 x exp " " d
1=1
Since choose and m such that 1pm 1/H2.
Σ (s,))) S 1 (x)H S mmH S 11/H.
Therefore, by invoking Lemma with á = x² and T't, we have that for any TH (8 A)
p= (TH) S p= (TH).
By further invoking Lemma function f S x RRt :
10 with X' (8 A) p 1p* and par" obtain that for any
By [s an)l O [[ ax)))
Similarly, can show E. (f an) O (E,* (f an)l), which completes the proof of Lemma
C.4 Proof of Lemma 4
To simplify notations, denote 6) == (s a..)) For the technical purpose of applying mar- tingale concentration, we additionally define the intermediate empirical covariance matrices:
Σ Σm of (d))) for [N]. We have that with probability at least 5,
Be >~x [ll (sn. an (
E En (sk, an) (ao
| (Sg 100 (1 log(L/8)
(4)
N
n=1
(v dlog + +0
1og(1/5) N
< 0
N
where the first inequality uses Σn < Σn. the second one uses Azuma-Hoefiin inequality with 1, and the last one uses Cauchy-Schward inequality and the the standard elliptical potential argument.
16

---

C,5 Proof of Lemma
Let us consider fixed pair hk, E [K] x [H]. Recall 2n is defined as
(% min - 1, E BP (a) ( h+ ( (s, + ()))))
where P% and & the empirical estimates of transition and reward step h from D and (s, a) = aJ) (s, a) + 1)-1/2 with (s. a) E(snoon)ED ((s),, an) (s,a)). Therefore, to prove Lemma 5 it suffices to show that for all (s, a)
( (Rg (V
(5')) (+
PP (a.a) ( ( + (s, RR (x, - (s, a).
know {V --=))=----- is independent of D Dj conditioning on n'* which (+
By observation
implies V h+1 is independent of ipt Therefore, by Azuma-Hoeffding inequality and standard union bound, we conclude that with probability at least - 8: for all (k, h, 8, a) E [K] x [H] x S x A.
(( VVtt (s))
(xs (V + (s, Rn))
log log(KNHSA/0)
S O H
(8, +1
C.6 Proof of Lemma
For the technical purpose of performing martingale concentration, introduce the notion of intermediate counters: (s, a) Σi= 1((5), of))
(s, as) for [N]. We have that with
probability at least 1 - 6,
V In(s, a)+
+1
N
E 9b Jak
V JK a) +1
==1
(5)
1
N
1og(1/0)
JR (s al) +1 +
N
N
SA log N
log(1/0) N
0
+0
N
where the first inequality uses (s, S (n, a) for all (s,a) E S x A, the second one uses Azuma-Hoeffdiig inequality, and the last one follows the standard pigeon-hole argument.
C.7 Proof of Lemmal
By observation 1 of the last iteration when OPTIMISTIC NPG collects fresh data before iteration 1. With this independence relation in mind, we can easily prove that confidence set B satisfy the following properties by standard concentration inequality and union bounds.
we know DÍ: is independent V conditioning on T'* where tę is the index
Lemma 11. Suppose Assumption 7 holds. There exists an absolute constant such that with probability least 8. for all l E [] and h E [H].
Thi" Ditt E Bh.
1 for any fm. B% Deo (fn T (sh, an))2 < cB.
The proof of Lemma follows trivially from modifying the proofs of Lemma 39 and in Jin et al.) 2021 which we omit here.
17

---

Define
= = (fa E Fr:
Σ
(fa(sh, as) (Th" (h+z)(sh, an)) S cBf}.
(eNDRN)ED)
By using the first relation in Lemma and the definition of Th. we immediately obtain that
(Th Q Qn+1)(s,a)
sup f,(s, (s.aa f
and (x(s))) - -TTh (n+))(s,a)
sup (J((s,a) [kss,a) S sup Ju EB
(fa(s,a) - (h(,
fa.REBK
where the last inequality uses B C B3 by Lemma 11
C.8 Proof of Lemma g
Recall define
sup
- [n(8,a)-5((3.) (/((,,)
(8, a, Da) =
Σ (sD,an)EDa
(fi(sh, fhhss, az)) S cB
s.t.
which implies that (s, a, Da) < b,,s, a, Dí) for any D, S Dr. Let (( {(8 a ) We
have that with probability least 5,
N
[bn(s, a, D/ 1)n
Ein [bn a, (n)] S
E Bn )ur
N
n=1
N
log (1/5)
<
(s ah D/
+0
H
N
N
n=1
de dn(1/N,
log(1/8)
< O
H
H
N
N
where the second inequality uses Azuma- coena-Hoeffding inequality and the last one uses the standard regret guarantee for eluder dimension (e.g., Lemma in Russo and Van Roy (013)).
18


Reviews:
[{"review_id": "nufJIRm6Jr", "reviewer": "Reviewer_BU1M", "summary": "This paper presents a model-free policy optimization algorithm Optimistic Natural Policy Gradient for online and episodic MDPs. The authors present sample complexity results which are better than existing results for linear MDPs. This makes it computationally efficient and optimal dimension dependence, first of its kind. The algorithm is also similar to popular RL algorithms like PPO which makes it even more interesting. ", "questions": "1. Zanette et al [2020] were able to improve the sample complexity of FQI-style algorithm by paying the price in computation. What is that the proposed algorithm compensates on, if anything, to achieve optimal rates? \n", "limitations": "-", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "Technically solid paper with state of the art sample complexity results. The contributions are very well highlighted. The details of the algorithm are well presented by highlighting the key three modules in the algorithm. The paper also studies the online exploration scenario without access to a simulator. ", "weaknesses": "Agarwal et. al [2020] did have some experimental results on some environments to verify indeed the proposed algorithm enjoys what is proved theoretically. In this paper, any experimental proof of \"computationally efficient\" is missing.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the valuable and positive feedback.  Please see our response below.\n\n**Q.** Zanette et al., (2020) were able to improve the sample complexity of FQI-style algorithm by paying the price in computation. What is that the proposed algorithm compensates on, if anything, to achieve optimal rates?\n\n**A.** Technically speaking, in each $k$-th iteration, both Zanette et al., (2020) and this work need to control an estimation error of form \n$\\left| \\mathbb{E}\\_{s'\\sim\\mathbb{P}\\_h(s,a)} [r\\_h(s,a)+V\\_{h+1}^k(s')] - Q\\_h^k(s,a) \\right|$\nwhere $Q\\_h^k(s,a)$ is estimated by using  dataset $\\mathcal{D}\\_h:=\\\\{(s\\_h^i,a\\_h^i,r\\_h^i,s\\_{h+1}^i)\\\\}\\_{i=1}^n$ and $V\\_{h+1}^k(\\cdot)$ (the $V$-estimate at step $h+1$), e.g., ridge regression.\nThe key difference between these two works lies in how the dependence between $\\mathcal{D}\\_h$ and $V\\_{h+1}^k(\\cdot)$  is handled when performing the concentration argument. \n\n- In Zanette et al., (2020),  all the historically collected data are included in $\\mathcal{D}\\_h$, even those that are correlated with  $V\\_{h+1}^k(\\cdot)$.  This creates undesired dependence between $\\mathcal{D}\\_h$ and $V\\_{h+1}^k(\\cdot)$, which hinders standard concentration.\nHowever, due to the use of nested confidence set, global optimism and the FQI-style update rule, $V\\_{h+1}^k(\\cdot)$ always lies inside a max-linear function class  $\\mathcal{F}\\_{h+1}=\\\\{\\max\\_{a}\\phi\\_{h+1}(s,a)^{\\top}\\theta:~~\\theta\\in\\mathbb{R}^d,~\\|\\theta\\|\\_2\\le \\sqrt{d}H\\\\}$. As a result, this dependence issue can be easily addressed by performing uniform concentration for all functions inside  $\\mathcal{F}\\_{h+1}$ whose log-covering number is only $\\tilde{\\mathcal{O}}(d)$. \n\n- Since this work focuses on policy optimization algorithms, our $V\\_{h+1}^k(\\cdot)$ admits a rather different form: $V\\_{h+1}^k(s)=\\mathbb{E}_{a\\sim \\pi^k\\_{h+1}(s)}[Q\\_{h+1}^k(s,a)]$. If we want to similarly use all the historical data as in Zanette et al., (2020), we need to control the log-covering number of all possible $V\\_{h+1}^k(\\cdot)$. Unfortunately, we could not get any bound better than $\\tilde{\\mathcal{O}}(kd^2)$ that is the log-covering number of all possible $\\pi^k\\_{h+1}(\\cdot)$. As a result, we opted for an alternative approach: only using the data that is independent of $V\\_{h+1}^k(\\cdot)$. This subset of data approximately constitutes a fraction of $\\mathcal{O}(\\epsilon)$ of the complete dataset, which makes our result  worse by a factor of  $\\epsilon^{-1}$ than Zanette et al., (2020) that leverages the entirety of the available data."}, {"review_id": "IubmqF49QI", "reviewer": "Reviewer_EF4H", "summary": "This paper proposes optimistic NPG for online RL, which is computationally efficient and enjoys the polynomial sample complexity while learning near-optimal policies. The paper is well-written and organization is clear.", "questions": "I do not have question on this paper for now.", "limitations": "As the authors mentioned in the Conclusions Section, I am also curious how to avoid the factor of 1/epsilon compared with the optimal rate.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "There are several strengths:\n1. Sample complexity benefits: compared with other computationally efficient policy optimization algorithms, the proposed algorithm in this work has better sample complexity guarantees; (I think this is the major strength)\n2. The first polynomially sampled policy optimization algorithm under general function approximation.\n3. Literature comparison and position is clear. The paper is well-written!", "weaknesses": "I think this paper is clear and I do not have concern for now.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the valuable and positive feedback. \n"}, {"review_id": "elFEvdKI8q", "reviewer": "Reviewer_1VAU", "summary": "This work proposes a simple-efficient efficient policy optimization algorithm for online RL. When specialized to linear MDPs, the algorithm improves the best known result by a factor of $d$. Moreover, this is the first efficient policy optimization algorithm under general function approximation.", "questions": "1 When specialized to linear MDPs, the algorithm is computationally efficient. When specialized to general function approximation, the algorithm is not computationally efficient due to the hardness of selecting optimitic Q-function in the confidence set. From what I know, [Ruosong Wang et al.] claims they developed a provably efficient (both computationally and statiscally) Q-learning algorithm. My question is that for the policy optimization under general function approximation, is it possible to devise a computationally efficient algorithm under the proposed optimistic NPG framework?\n\n2 Can the authors comment on the subtle technical challenge in [Cai et al.] (linear mixture MDPs) in dealing with linear MDPs? Is the difficulty caused by covering number argument?\n\n[Ruosong Wang et al.] Reinforcement Learning with General Value Function Approximation: Provably Efficient Approach via Bounded Eluder Dimension\n", "limitations": "N/A", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "1 This work is well-written and well-organized.\n\n2 This work showcase a generic policy optimization meta-algorithm can be sample efficient. \n\n3 The theoretical guarantee outperforms the exisiting result in linear MDPs, and is the first sample efficient policy optimiztion algorithm under general function approximation.", "weaknesses": "1 When specialized to tabular scenario, the result is worse than the best existing result.\n\n2 Under linear MDPs, the dependency on $\\epsilon$ is not optimal.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the valuable and positive feedback. \nPlease see our response below.\n\n\n**Q1.** From what I know, [Ruosong Wang et al.] claims they developed a provably efficient (both computationally and statiscally) Q-learning algorithm. For policy optimization under general function approximation, is it possible to devise a computationally efficient algorithm under the proposed optimistic NPG framework?\\\n**A1.**  The computational efficiency in Wang et al., (2020) is established based on the following assumption: given a state-action pair $(s,a)$, a set of state-action pairs $\\\\{ (s^i, a^i) \\\\}\\_{i=1}^n$ and $\\epsilon>0$, one can  determine whether $(s,a)$ is $\\epsilon$-dependent on  $\\\\{ (s^i,a^i) \\\\}\\_{i=1}^n$ with respect to function class $\\mathcal{F}$ in a computationally efficient way.\nAs it stands, it is unclear when this assumption holds except for \nthe case $\\mathcal{F}$ being (generalized) linear function class. \nConsequently, the question of designing computationally efficient algorithms for general function approximation remains an open challenge, especially when considering reasonable computation-oracle assumptions.\nHowever, it's noteworthy that one can obtain computationally efficient policy optimization (PO) algorithms by amalgamating our optimistic NPG framework with the bonus-design and computation-oracle assumption used in Wang et al., (2020).\n\n\n**Q2.** Can the authors comment on the subtle technical challenge in Cai et al., (2020)  (linear mixture MDPs) in dealing with linear MDPs? Is the difficulty caused by covering number argument?\\\n**A2.** Yes, the difficulty is caused by controlling the covering number of all the possible V-estimates. In each $k$-th iteration, Cai et al., (2020) need to control an estimation error of form $\\left| \\mathbb{E}\\_{s'\\sim\\mathbb{P}\\_h(s,a)} [r\\_h(s,a)+V\\_{h+1}^k(s')] - Q\\_h^k(s,a) \\right|$ where $Q\\_h^k(s,a)$ is estimated by using  dataset $\\mathcal{D}\\_h:=\\\\{(s\\_h^i,a\\_h^i,r\\_h^i,s\\_{h+1}^i)\\\\}\\_{i=1}^n$ and $V_{h+1}^k$ (the $V$-estimate at step $h+1$), e.g., ridge regression. In Cai et al., (2020),  $\\mathcal{D}\\_h$ consists of all the historically collected data, including those that are correlated with $V\\_{h+1}^k(\\cdot)$. This creates undesired dependence between $\\mathcal{D}\\_h$ and $V\\_{h+1}^k(\\cdot)$, which hinders standard concentration.  One natural way to fix this problem is perform uniform concentration for all possible $V\\_{h+1}^k(\\cdot)=\\mathbb{E}\\_{a\\sim \\pi^k\\_{h+1}(\\cdot)}[Q\\_{h+1}^k(s,a)]$, which requires bounding the log-covering number of all possible $V\\_{h+1}^k(\\cdot)$.  Unfortunately, so far it remains unclear how to get any bound better than $\\tilde{\\mathcal{O}}(kd^2)$ that is the log-covering number of all possible $\\pi^k\\_{h+1}(\\cdot)$. As a result, it remains open whether the algorithm in Cai et al., (2020)  can generalize to linear MDPs or not. "}, {"review_id": "4IpMi0LA8D", "reviewer": "Reviewer_LFfR", "summary": "The paper presents $\\texttt{OPTIMISTIC NPG}$, a new algorithm that combines the natural policy gradient with optimistic policy evaluation to encourage exploration in online RL. The algorithm demonstrates computational efficiency and achieves optimal sample complexity in linear MDPs, outperforming existing state-of-the-art approaches. Furthermore, it extends to general function approximation, making it the first algorithm to achieve polynomial sample complexity for learning near-optimal policies in this broader setting.", "questions": "- On line 138, there appears to be a typo in the equation where $\\psi$, a $d$-dimensional vector, is integrated with respect to s, resulting in a real number bound.\n- In comparison to traditional off-policy policy gradient algorithms, what practical advantages does the on-policy algorithm offer?", "limitations": "Since this is a theoretical paper, its direct societal impact seems to be neutral.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "- The authors propose a computationally efficient policy optimization algorithm with improved sample complexity in $d$-dimensional linear MDPs.\n- The authors Introduce the first on-policy method in the exploration setting that achieves polynomial sample complexity, contrasting with previous off-policy algorithms.\n- The authors extend the linearMDP algorithm to a general function approximation algorithm, exhibiting polynomial sample complexity measured by the eluder dimension of a function class.", "weaknesses": "- The technical novelty of the algorithm for a general function class appears unclear, and further explanation is needed on how to construct confidence sets when working with function classes beyond linear functions.\n- Excluding the issue of computational intractability, Subroutine 3 appears to be applicable to general function classes with bounded eluder dimension. For example, Dong et al. (2021) proved that \"one-layer neural nets do not have polynomially-bounded eluder dimension,\" presenting an exponential eluder dimension. It is challenging to claim that the algorithm proposed in this paper is sample efficient for function classes with such characteristics.\n\n\\--\n\nDong, K., Yang, J., & Ma, T. (2021). Provable model-based nonlinear bandit and reinforcement learning: Shelve optimism, embrace virtual curvature. Advances in Neural Information Processing Systems, 34, 26168-26182.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the valuable and positive feedback. \n\n\n**Q1.** The technical novelty of the algorithm for a general function class appears unclear, and further explanation is needed on how to construct confidence sets when working with function classes beyond linear functions.\\\n**A1.** \nThe mathematical definition of the confidence set can be found in Line 6-7 of Subroutine 3 (General OPE) while additional intuitive explanations are offered in Line 257-268.  We kindly request the reviewer to specify the aspects of the confidence set construction that appear unclear, and we are enthusiastic about the opportunity to provide further clarification and address any points of confusion.\n\n\n\n**Q2.** Dong et al. (2021) proved that ''one-layer neural nets do not have polynomially-bounded eluder dimension,\" presenting an exponential eluder dimension. It is challenging to claim that the algorithm proposed in this paper is sample efficient for function classes with such characteristics.\\\n**A2.** Dong et al. (2021) also established that ''the minimax sample complexity of one-layer neural nets with ReLU activation is $\\Omega(\\epsilon^{-(d-2)})$'' (refer to Theorem 5.1 in  Dong et al. (2021)). \nConsequently, the fact that ``one-layer neural nets do not have polynomially-bounded eluder dimension\" should not be viewed as a  drawback of  this work, because information-theoretically any RL algorithm requires at least  $\\Omega(\\epsilon^{-(d-2)})$ samples to effectively learn one-layer neural nets under worst-case scenarios.\n\n**Q3.** On line 138, there appears to be a typo in the equation where   $\\psi$, a  $d$-dimensional vector, is integrated with respect to $s$, resulting in a real number bound.\\\n**A3.** Thank you for spotting the typo. The correct version should be the $\\ell_2$-norm of the left hand side is bounded by the same scalar. We will fix it in the revision.\n\n\n**Q4.** In comparison to traditional off-policy policy gradient algorithms, what practical advantages does the on-policy algorithm offer?\\\n**A4.** \nIn the realm of empirical RL, many widely-used policy gradient algorithms (e.g., PPO and TRPO) are on-policy. \n On-policy algorithms typically demand less memory resources because they do not  maintain an off-policy dataset as in off-policy algorithms (e.g., the replay buffer in A2C).\nRegarding performance, the superiority between on-policy and off-policy methods hinges on the specific tasks at hand. For instance,  Figure 6 in Schulman et al. (2017) highlights a comparison among PPO (on-policy), A2C (off-policy), and ACER (off-policy) across all 49 ATARI games featured in OpenAI Gym. The results therein illustrate that these algorithms excel in distinct tasks, thereby underlining the task-dependent nature of their effectiveness.\n\n\n---\nSchulman et al., (2017). Proximal Policy Optimization Algorithms. "}, {"review_id": "v9LymVPyaf", "reviewer": "Reviewer_czwS", "summary": "This paper proposes a simple and efficient policy optimization method with rigorous theoretical guarantee. The algorithm combines the natural gradient ascent and the optimistic off policy evaluation and is computationally efficient. They provide the condition under which the algorithm is guaranteed to be efficient and can provably learn the optimal policy. The authors also gave three examples to show the efficiency of the algorithm: tabular case, linear function approximation and general function approximation. They show that their algorithm achieves the optimal dependence on d for linear case which improves the algorithm proposed by Zanette et al, 2021 by a factor of d. They also show that their algorithm is the first one to achieve polynomial sample complexity in general function approximation case. \n\nIn general, the proof is sound and also the writing is very good and clear. I like the simplicity of their algorithm.", "questions": "/", "limitations": "a typo:\nLine 284: in the worse case --> in the worst case.", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "1. The algorithm is simple, efficient and easy to understand.\n2. They provide a sound argument of theory and the proof is sound to my knowledge.\n3. In linear case, their algorithm achieves the optimal dependence w.r.t. the dimension d with computational efficiency.\n4. Besides 3, they also provide the sample complexity in tabular and general function approximation case.", "weaknesses": "I do not think this paper has any apparent weakness. Though, I still have some minor questions about it.\n\n1. In Theorem 1, you claim the result holds with probability at least 1/2, and in Line 207-211,  you claim that you can achieve the probability 1-\\delta for any \\delta with a sample complexity multiplies by a log factor. I understand that you only need to run the algorithm one for log(1/\\delta) times, but how do you 'estimate the values of every output policy to accuracy \\eps'? Can you show exactly how you do to achieve this? In this estimation stage, do you need to sample additional online data using the output policy or not?\n\n2. In line 223-226, you claim the best sample complexity for policy optimization in the tabular case is H^4 S A / \\eps^2. I am not sure whether this is true. Indeed, the Wu et al. you cited expressed their result in the form of regret, and you can of course uniformly sample one policy from the policies output in Wu et al and get the sample complexity. However, in this paper (https://arxiv.org/pdf/2007.13442.pdf), they propose the algorithm BPI-UCBVI for best policy identification (another name of 'policy optimization'?), and they showed the sample complexity to be H^3 S A / \\eps^2 log(1/\\delta). (This is the second algorithm in their paper and the first one is reward-free version. Even the traditional UCBVI algorithm should be able to achieve the H^3 S A / \\eps^2 * polylog(1/\\delta). I wonder whether they considered a different setting as you did and whether result you claimed is the best one.\n\n3. In all three subroutines about OPE, you split the data into H even disjoint subset. Do you think this splitting is inefficient? I remember in some papers, such as this one (https://arxiv.org/pdf/2106.04895.pdf), they split the data into three instead of H subsets to reduce the sample complexity. Do you think this will help you further reduce the sample complexity in your algorithm?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the valuable and positive feedback. \nPlease see our response below.\n\n**Q1.** I understand that you only need to run the algorithm one for $\\log(1/\\delta)$ times, but how do you estimate the values of every output policy to accuracy $\\epsilon$? Can you show exactly how you do to achieve this? In this estimation stage, do you need to sample additional online data using the output policy or not?\\\n**A1.** We can evaluate  these \n$\\log(1/\\delta)$  policies by running each of them for $\\tilde{\\mathcal{O}}(H^2/\\epsilon^2)$ episodes. Then  the one with the highest empirical estimate is selected. \nTherefore, the reviewer is right that additional online data is needed. Nonetheless, the amount of additional data is only $\\tilde{\\mathcal{O}}(H^2/\\epsilon^2)$, which is smaller than the sample complexity of optimistic NPG. \nAs a result, the overall sample complexity remains the same order up to logarithmic terms.\n\n\n**Q2.** The best sample complexity for policy optimization in the tabular case.\\\n**A2.** Thank you for catching the typo. By regret-to-PAC conversion,  the result in Wu et al., (2022) implies a sample complexity of order $\\tilde{\\mathcal{O}}(H^3SA/\\epsilon^2)$ that matches the lower bound for tabular MDPs up to logarithmic terms. We will fix this typo in the revision.\nThank you for pointing out the  BPI-UCBVI algorithm. As we perceive it, the algorithmic framework of BPI-UCBVI bears more resemblance to  the UCBVI algorithm (Azar et al., 2017), as mentioned in Section 4.1 of the BPI-UCBVI paper.  Specifically, the policies in BPI-UCBVI are always chosen to be the greedy policies with respect to the Q-estimate. Therefore, in our understanding it leans more towards a value-based methodology instead of a policy optimization one. \n\n**Q3.** Can we use the reference-advantage decomposition to avoid $H$-fold data splitting?\\\n**A3.** This is a great observation. Upon initial consideration, we find this idea very promising.  While extending the three-fold splitting technique proposed in Xie et al. (2022) from tabular MDPs to linear MDPs, the only part that we feel uncertain about is how to construct the Bernstein-style bonus (i.e., $b_{h,1}(s,a)$ in Line 7 of Algorithm 1 in Xie et al., 2022) for linear MDPs. We believe that the Bernstein-style bonus introduced in Pu et al., (2023) could potentially serve our purpose. However, a meticulous and thorough analysis is required in determining the viability of this approach.\n\n\n\n**Q4.** a typo: Line 284: in the worse case $\\rightarrow$ in the worst case.\\\n**A4.** Thank you for spotting the typo. We will fix it in the revision.\n\n---\nPu et al., (2023). Nearly Minimax Optimal Reinforcement Learning with Linear Function Approximation."}]

Author rebuttal:

Meta-review: All the reviewers agreed that the theoretical contribution of this paper to policy gradient is significant (in particular the improvement of the feature dimension). I recommend the paper be accepted for spotlight presentation.
Decision: Accept (spotlight)