A Theoretical Analysis of Optimistic Proximal Policy Optimization in Linear Markov Decision Processes
Authors: Han Zhong
Tong Zhang
Venue: NeurIPS 2023 poster (2023)
Keywords: policy optimization
adversarial lienar MDPs
RL theory

Abstract: The proximal policy optimization (PPO) algorithm stands as one of the most prosperous methods in the field of reinforcement learning (RL). Despite its success, the theoretical understanding of PPO remains deficient. Specifically, it is unclear whether PPO or its optimistic variants can effectively solve linear Markov decision processes (MDPs), which are arguably the simplest models in RL with function approximation. 
    To bridge this gap, we propose an optimistic variant of PPO for episodic adversarial linear MDPs with full-information feedback, and establish a $\tilde{\mathcal{O}}(d^{3/4}H^2K^{3/4})$ regret for it. Here $d$ is the ambient dimension of linear MDPs, $H$ is the length of each episode, and $K$ is the number of episodes. Compared with existing policy-based algorithms, we achieve the state-of-the-art regret bound in both stochastic linear MDPs and adversarial linear MDPs with full information. Additionally, our algorithm design features a novel multi-batched updating mechanism and the theoretical analysis utilizes a new covering number argument of value and policy classes, which might be of independent interest.

A Theoretical Analysis of Optimistic Proximal Policy Optimization in Linear Markov Decision Processes
Han Zhong
Tong Zhang Department of Mathematics HKUST
Center for Data Science
Peking University
hanzhong@stu. pku edut..ddu.comm
tongchangttonghhang.... org
Abstract
The proximal policy optimization (PPO) algorithm stands as one of the most pros- perous methods in the field of reinforcement learning (RL). Despite its success, the theoretical understanding of PPO remains deficient. Specifically, it is unclear whether PPO or its optimistic variants can effectively solve linear Markov decision processes (MDPs), which arguably the simplest models in RL with function approximation. To bridge this gap. we propose an optimistic variant of PPO for episodic adversarial linear MDPs with full-information feedback, and establish (dd H22 H²2/441K//)))) regret for it. Here is the ambient dimension of linear MDPs, is the length of each episode, and K is the number of episodes. Compared with existing policy-based algorithms, we achieve the state-of of-the-art regret bound both stochastic linear MDPs and adversarial linear MDPs with full information. Additionally, our algorithm design features a novel multi-batched updating mech- anism and the theoretical analysis utilizes a new covering number argument of value and policy classes, which might be of independent interest.
Introduction
Reinforcement learning (RI. [34] is prominent approach to solving sequential decision making problems. Its tremendous successes [19, 32, 33, 5] can be attributed, in large part, to the advent of
deep learning [22] and the development of powerful deep RL algorithms [24, 28, 29, 11]. Among these algorithms, the proximal policy optimization (PPO) [29] stands out as a particularly signifi- cant approach. Indeed, it continues to play pivotal role in recent advancements in large language
models [27].
Motivated by the remarkable empirical success of PPO, numerous studies seek to provide theoretical justification for its effectiveness. In particular, Cai al. [6] develop an optimistic variant of the PPO algorithm in adversarial linear mixture MDPs with full-information feedback [4, 25], where the transition kernel linear combination of several base models. Theoretically, they show that the optimistic variant of PPO is capable of tackling problems with large state spaces by establishing a sublinear regret that is independent of the size the state space. Building upon this work, He et al. [14] study the same setting and refine the regret bound derived by Cai et al. [6] using the weighted regression technique [44]. However, the algorithms in Cai et al. [6]. He et al. [14] and other algorithms for linear mixture MDPs [4, 44] implemented in model-based manner and require an integration of the individual base model, which can be computationally expensive or even intractable in general. Another arguably simplest RL model involving function approximation is linear MDP [38, 17], which assumes that the reward functions and transition kernel enjoy low-rank representation. For this model, several works [17, 15, 13] propose value-based algorithms that directly approximate the value function and provide regret guarantees. To demonstrate the efficiency of PPO in linear MDPs from theoretical perspective, potential approach is to extend the results
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

Table 1: A comparison with closely related works policy optimization for linear MDPs. Here "Sto." and "Adv." represent stochastic rewards and adversarial rewards, respectively. Additionally, "Bandit" and "Full-infor." signify bandit feedback and full-information feedback. We remark that Zanette et al. [40] do not consider the regret minimization problem and the regret reported in the table is implied by their sample complexity. We will compare the sample complexity provided in Zanette et al. [40] and the complexity implied by our regret in Remark 3.2.
Sto. Bandit
Adv. Full-infor.
Adv. + Bandit
Regret O H 13/ K3/4) O A H20 K8/9)
[40]
X
X
[8]
[31]
O(dH2R6/7) 0(214
Our Work
X
of Cai al. [6], al. [14] to linear MDPs. However, this extension poses significant challenges due to certain technical issues that are unique to linear MDPs. See $1.1 for detailed description.
In this paper, we address this technical challenge and prove that the optimistic variant of PPO is provably efficient for stochastic linear MDPs and even adversarial linear MDPs with full-information feedback. Our contributions summarized below.
In terms of algorithm design, we propose new algorithm OPPO+ (Algorithm 1), an optimistic variant of PPO, for adversarial linear MDPs with full-information feedback. Our algorithm fea- tures two novel algorithm designs including multi-batched updating mechanism and policy evaluation step via average rewards.
Theoretically, establish O(B/4 H2 K3/4) regret for OPPO+, where d is the ambient dimension linear MDPs, H is the horizon, and K is the number of episodes. To achieve this result, we employ two techniques. Firstly, we adopt novel covering number argument for the value and policy classes, as explicated in SC. Secondly, in Lemma 4.3, we meticulously analyze the drift between adjacent policies to control the error arising from the policy evaluation step using average rewards.
Compared with existing policy optimization algorithms, our algorithm achieves better regret guarantee for both stochastic linear MDPs and adversarial linear MDPs with full-information feedback (to our best knowledge). See Table for a detailed comparison.
In summary, our work provides new theoretical justification for PPO in linear MDPs. To illustrate our theory more, we highlight the challenges and our novelties in $1.1.
1.1 Challenges and Our Novelties
Covering Number of Value Function Class. In the analysis of linear MDPs (see Lemma B.3 or Lemma B.3 in Jin et al. [17]), we need to calculate the covering number of V which the function class of the estimated value function at the h-th step of the k-th episode and takes the following form:
Challenge 1:
D = (V()- (
where Q and कं estimated Q-function and policy the h-th step of the k-th episode, respec- tively. For value-based algorithms (e.g.. LSVI-UCB in Jin et al. [17]), The is the greedy policy with respect to Q Then we have
D = (V()) max (+(.
Since max, is contraction map, it suffices to calculate A (V,)), where Øf is the function class of Q and N-))) denotes the covering number. By a standard covering number argument (Lemma D.4 or Lemma D.6 in Jin et al. [17]), can show that (o)) < O(dF). However, for policy- based algorithms such as PPO, n is stochastic policy, which makes the log-covering number (Vg)) may have polynomial dependency on the size of action space A (log-covering number

---

Kit
π
n
Q 11
Q 2g
4-1
Q k
4+l Q
Rewards
Rawards
k1
k
K
k
k2
K
Algorithm diagram. The entire K episodes are partitioned into I. K/B batches, with each batch containing B consecutive episodes. The policy/value updating only occurs the beginning of each batch. The policy evaluation uses the reward function in the last batch.
Figure I:
of |A| Ill-mimenioona probability distributions is at the order of [A].. We also remark that linear mixture MDPs more amenable theoretical analysis compared to linear MDPs, they do not necessitate the calculation of the covering number of V [4, 6J. As result, the proof presented by Cai et [6] valid for linear mixture MDPs, but cannot extended linear MDPs. See $A for more elaboration of technical challenges.
Novelty 1: Multi-batched Updating and A New Covering Number Argument. Our key obser- vation is that if we improve the policy like PPO (see (3.2) or Schulman et al. [29], Cai et al. [6]), m admits softmax form, i.e.,
( x exp Oz
Here (k:)/=1 is sequence of episodes, where I for all [1]. denoting the episodes in which our algorithm performs policy optimization prior to the k-th episode. By technical lemma (Lemma C.3), we can show that
log (class of m/. S Σ (Qg S Ó(1. d)).
If we perform the policy optimization in each episode like Cai et al. [6], Shani et al. [30], may linear in and the final regret bound becomes vacuous. Motivated by this, we use a batthe updating scheme. In specific, OPPO+ divides the whole learning process into several batches and only updates policies at the beginning of each batch. See Figure for visualization. For example, if the number of batches is 1//2 (i.c.. each batch consists of consecutive 1/2 episodes), have I < K1/2 and the final regret at the order of (KK3/4). Here we assume 11/2 a positive integer for simplicity. See &C for details.
Challenge Adversarial Rewards. Compared with previous value-based algorithms [e.g.. 17], one superiority of optimistic PPO is that they can learn ad MDPs with full-information feedback [6, 30]. Cai et al. [6], Shani al. [30], the policy evaluation step is that
Q =
P V4+ + bonus function, Vh [H],
V Vh+1 00
where r is the adversarial reward function and P is the estimator of the expected next step value 1/k 1+ This policy evaluation step invalid if we use the multi-batched updating. Consider the following case, if the number of batches is K 1/2 and
ke E 12K + +1]-1
(
arbitrary
otherwise
Then the algorithm only uses zero rewards to find the optimal policy hindsight with respect to arbitrary adversarial rewards, which is obviously impossible.

---

Novelty 2: Policy Evaluation via Average Reward and Smoothness Analysis. To tackle the above challenge, we adopt the following policy evaluation step at the beginning of each batch
Q - V h++1 + bonus function,
vh [H],
Vh+1 = 0,
where r the average reward of the last batch:
Σ (reward functions of the last batch)
batch size
Let Th denote the policy executed in the i-th batch. Intuitively, TTkaa is the desired policy within i-th batch since its calculation only uses the rewards in the first (i (i-1) batches (cf. Figure 1). Hence, compared with Cai et al. [6], Shani et al. [30], we need to handle the gap between the performance of 7 and z in the i-th batch. Fortunately, this error can be controlled due the "smoothness" of policies in adjacent batches. See Lemma 4.3 for details.
1.2 Related Works
Policy Optimization Algorithms. The seminal work of Schulman et al. [29] proposes the PPO algorithm, and line of following works seeks to provide theoretical guarantees for it. In particular, Cai et al. [6] proposes the optimistic PPO (OPPO) algorithm for adversarial linear mixture MDPs and establishes regret (dd K) for it. Then, He et al. [14] improve the regret to (dv H by the weighted regression technique [44]. Besides their works on linear mixture MDPs, Shani et al. [30], Wu et al. [37] provide fine- fine-grained analysis of optimistic variants of PPO in the tabular case. The works of Fei et al. [9]. Zhong al. [42] show that optimistic variants of PPO can solve non- stationary MDPs. However, none of these works show that the optimistic variant of PPO is provably efficient for linear MDPs.
There is another line of works 12. 10, 40] proposes optimistic policy optimization algorithms based on the natural policy gradient (NPG) algorithm [18] and the policy-cover technique. But their works are limited to the stochastic linear MDPs, while our work can tackle adversarial rewards. Compared with their results for stochastic linear MDPs, our work can achieve a better regret and compatible sample complexity. See Table 1 and Remark 3.2 for a detailed comparison. Several recent works [26, 23, 20, 8. 31] study the more challenging problem of learning adversarial linear MDPs with only bandit feedback, which is beyond the scope of our work. Without access to exploratory policies or even known transitions, their regret is at least ( [31], while our work achieves better ((K3/44 regret with the full-information feedback assumption.
RL with Linear Function Approximation. Our work is related to previous works proposing value-based algorithms for linear MDPs [38, 17]. The work of Yang and Wang [38] develops the first sample efficient algorithm for linear MDPs with a generative model. Then Jin et al. [17] proposes the first provably efficient algorithms for linear MDPs in the online setting. The results of Jin et al. [17] are later improved by [35, 15. 13, 3]. In particular, Agarwal et al. [3], He et al. [13] show that the nearly minimax optimal regret ((d/H²K) K) is achievable in stochastic linear MDPs. Compared with these value-based algorithms, our work can tackle the more challenging adversarial linear MDPs with full- hull-informttion feedback.
There is another line of works [4, 25, 6, 41, 14, 45, 44, 43] studying linear mixture MDPs, which is another model of RL with linear function approximation. It can be shown that linear MDPs and linear mixture MDPs are incompatible in the sense that neither model is a special case of the other. Among these works, Zhou et al. [44], Zhou and Gu [43] establishes nearly minimax regret H²
(d for stochastic linear mixture MDPs. Our work is more related Cai et al. [6], He al. [14] on adversarial linear mixture MDPs with full-information feedback. We have remarked that it nontrivial to extend their results linear MDPs.
2 Preliminaries
Notations. We use N+ to denote the set of positive integers. For any E N we denote [#] 21, H}. For any H e N and x E R. we use the notation min(æ, H|+

---

min(H, H. max(0,x)). Besides, we denote by (AA the set of probability distributions on the set A. For any two distributions P and Q over A. we denote (L(P))Q Ea-rlloo [
Episodic Adversarial MDPs. We consider an episodic MDP M, which denoted by a tuple
(S,A, H, K, (TA)).M)))))))( P = (Ph)))()))
where S is the state space, .A is the action space, H is the length of each episode, K is the number of episodes, r S x A + [o, is the deterministic' reward function at the h-th step of k-th episode, Ph, is the transition kernel with (s s, a) being the transition probability for state to transfer the next state s' given action a at the h-th step. We consider the adversarial MDPs with full-information feedbuck, which means that the reward {r [eEj)] is adversarially chosen by the environment at the beginning of the k-th episode and revealed to the learner after the k-th episode.
A policy = (TT is collection of H functions, where Th S + ((A) is a function that maps a state to distribution over action space at step h. For any policy и and reward function (r) he(rj we define the value function v :S R and Q-function Q7, :S x A as
ViT (z) = Ex
Th (INA, aw)
2h = x
h
2ht (z, E
Σ h'=h
r (Irs, aw)
2h I, an
for any (I, a, k. h) E S x x x [K] x [H] Here the expectation [- is taken with respect to the randomness of the trajectory induced by policy и and transition kernel P. It well-known that the value function and Q-function satisfy the following Bellman equation for any (z, a) E x A,
ViT = (0% (z, (- a))A. (x, a) = = a) + (P (Pr141)) a), where (A denotes the inner product over the action space A and we will omit the subseript when it is clear from the context. Here P^ is the operator defined
(2.1)
(P (z) a) ( (xx),,
: R.
(2.2)
Interaction Process and Learning Objective. We consider the online setting, where the learner improves her performance by interacting with the environment repeatedly. The learning process con- sists of K episodes and each episode starts from a fixed initial state 22 At the beginning of the k-th episode, the environment adversarially chooses reward functions {r/, he(r] which can depend on previous (k- trajectories. Then the agent determines a policy n and receives the initial state af = F1. At each step [H) the agent receives the state o chooses an action at ~ TT( ax)). receives the reward function r and transits to the next state # The k-th episode ends after H steps.
We evaluate the performance of an online algorithm by the notion of regret [7], which defined as the value difference between the executed policies and the optimal policy in hindsight:
K
Regrot((K = -max
Σ (vTT*((>) -TT" (x1)).
A=
For simplicity, we denote the optimal argmax, Σk VT
policy
hindsight by n², i.c. n
Linear MDPs. We focus on the linear MDPs [38, 17], where the transition kernels are linear in known feature map.
Definition 2.1 (Linear MDP). We say an MDP (S,A, H, K, (rA P (Prhneun) is linear MDP if there exists known feature o S A +> Rd such that for any (x, a, k, h) S x A x [K] x [H], we have
Pa(a' x. = H(x, a) (n (x'),
where pa (u/ (1)
(d) are d unknown signed measures over S satisfying [S)]())]22 S Va.
1h
'This assumption is without loss of generality since subsequent results are ready to be extended to the stochastic reward case. *Our subsequent analysis can be generalized to the case where the initial state is chosen from fixed distri- bution across all episodes.
5

---

Algorithm OPPO+
Require: Batch size B E N+, regularization parameter À > and confidence radius >> 0.
1: Initialize {Q)), {r BgRsO as zero functions and { } as uniform distributions on A, vh
[M]
2: Let L= L
and h; = (i 1) B for 1 S [4].
3: for episode .,2...., K do
4: Receive the initial state zÇ.
5: i k; then
6: ( 0.
7: for step h = ........ do
Update the policy by x- x an k-1 (.1.) -xplaa 2 (;,))) end for
8:
9:
10:
for step h = H. H
do
1 - Ersl k-1 6( 070( o7) + x ld.
11:
w + (AA) - o(0 o V.2 (2
13:
=h(;;)) +- (Ej=k; (),
14:
[h(+-) 5 8 (M)) -
15:
PVV +
w ). h)
16:
Qh(--)) = ( P/4
17:
(+((+ + (0%6 end for
19:
iti+1
20:
else
21:
+ 0
V. v Th
Th k pl -/- wh [H].
22:
end if
23:
for h = 1,2..... .,... H do
24:
Take the action following a T/(( (111)))))..))))))))))
25:
Observe the reward function r (.,.) and receive the next state #/+1'
26:
end for
27:
end for
Since we have access to the full-information feedback, we do not assume the reward functions are linear in the feature map & like Jin et [17]. We also remark that the adversarial linear MDP with iull-information feedback is a more challenging problem than the stochastic linear MDP with bandit feedback studied Jin et [17]. In fact, for stochastic linear MDPs, we can assume the reward functions are known without loss of generality since learning the linear transition kemel is more difficult than the linear reward.
3 Algorithm
In this section, we propose new algorithm OPPO+ (Algorithm 1) solve adversarial linear MDPs with full-information feedback. In what follows, we highlight the key steps of OPPO+.
Multi-batched Updating, Due to the technical issue elaborated in $1.1, we adopt the multi-batched updating rule. In specific, OPPO+ divides the total K episodes into L K/B batches and each batch consists of B consecutive episodes, Here we assume K/ / B is positive integer without loss of generality?. For ease of presentation, we use k; = - 1) B to denote the first episode in the i-th batch. When the k-tth episode is the beginning of a batch (i.e, k = k; for some i E [L)), OPPO+ performs the following policy improvement step and policy evaluation step.
Policy Improvement. In the policy improvement step of the k-th episode (k = k; for some i E [T.)), OPPD+ calculates - based on the previous policy n A using PPO [29]. In specific, OPPO+ updates
We can only consider the first B [K/B] episodes since the remaining episodes will lead at most BH regret, which is non-dominant term in final regret bound

---

x by solving the following proximal policy optimization problem:
Hh argmaa
[ ... EEg-1
Σ (Ta(: wn mm) ( mil)
(3.1)
where a > is the stepsize that will be specified in Theorem 3.1, and Lx- (TT) takes form
LK-1(T)= VI" (x4) + Eg
E ((x mal 2h) Th k-1 '- m2n)
which is proportional to the local linear function of ViT (af)) at n and replaces the unknown
Q-function 0% .k-1 by the estimated one Q for any h E [H]. It is not difficult to show that the updated policy nh obtained in (3.1) admits the following closed form:
x (: ar) x 2 (. ar) exp (ax 1 (x,,))
V(a,h) E EEEE [H].
(3.2)
Policy Evaluation. In the policy evaluation step of the k-th episode (k: ki for some [KD, OPPD+ lets V be the zero function and iteratively calculates the estimated Q-function hQehe in the order of h H, H. I.....1. Now we present the policy evaluation at the he-th step given estimated value V 4++1- By the definitions of linear MDP in Definition 2.1 and the operator Py in (2.2), we know PA 7,+ is linear in the feature map Φ. Inspired by this, we estimate its linear coefficient by solving the following ridge regression:
argmin wER
Σ (o(x),
(x + A.dd
(3.3)
where À > 0 is the regularization parameter and Ia is the identify matrix. By solving (3.3), we have
w = (A Σ ol a (=+2((h+1)) where A = Σ ol a a + x Ia.
Based on this linear coefficient, we construct the estimator [P Vh as
(P min(((;,)) Tw + (,) -1)+
where = = 3. (0(; .) ((A))) ( is the bonus function and /3 >> O is parameter that will be specified in Theorem 3.1. This form of bonus function also appears in the literature linear bandits [21] and linear MDPs [17]. Finally, we update Q and V by
(% = (,,)) (PAV))))))))
V.(( = (2 ),
. 1))aa.
(3.4)
Here F is the average reward function in the last batch, that is
(x Σ 1k--1 r((:)-)
(3.5)
B
where 1: (i 1) B 1 and k;- = =1-1=(1-2) B
Here we would like to make some comparisons between our algorithm OPPD+ and other related algorithms. Different from previous value-based algorithms that take simply take the greedy policy with respect to the estimated Q-functions [17]. OPPO+ involves policy improvement step like PPO [29]. This step is key tackling adversarial rewards. The most related algorithm is OPPO proposed by Cai et al. [6], which performs the policy optimization in linear mixture MDPs. The main difference between OPPO+ and OPPO is that we introduce multi-batched updating and an average reward policy evaluation, which are important for solving linear MDPs (cf. 11. Finally, remark that the multi-batched updating scheme adopted by previous work on bandits [12] and RL [36]. But their algorithms are value-based and cannot tackle adversarial rewards.
Theorem 3.1 (Regret). Fix ō E [0,1] and K > d. Let B = V and a = /2B log (4/(H²2) X 1, B O( with = log(dHK|AA/0)) then with probability least 1 - 8, the regret of Algorithm satisfies
Regret < 0// //////22 k34 log A) 0(55/2
7

---

Proof. By See $4 for detailed proof.
To illustrate our theory more, make several remarks follows.
Remark 3.2 (Sample Complexity). Since learning adversarial linear MDPs with full-information feedback is more challenging than learning stochastic linear MDPs with bandit feedback, the result in Theorem 3.1 also holds for stochastic linear MDPs. By the standard online-to-bated argument [16], we have that Algorithm can find an e-optimal policy using at most
H
HH
22
samples. Compared with the sample complexity (ld H /c²) in Zanette et al. [40], we have better dependency on but a worse dependency on e. Moreover, by the standard sample complexity to regret argument [16], their sample complexity only gives a (d H 23/4 K3///////// K3/4), which is worse than our regret in Theorem 3.1. More importantly, the algorithm in Zanette al. [40] lacks the ability to handle adversarial rewards, whereas our proposed algorithm overcomes this limitation.
Remark 3.3 (Optimality of Results). For stochastic linear MDPs, Agarwal et al. [3]. He et al. [13] design value-based algorithmss with D(d/H3K regret, which matches the lower bound ((dvH*K) [44] up to logarithmic factors. It remains unclear whether policy-based based algo- rithms can achieve the nearly minimax optimal regret and we leave this as future work. For the more challenging adversarial linear MDPs with full-info bull-information feedback, achieve the state-of- the-art art regret bound. In this setup, direct lower bound is ((dvH3K) [44, 14), and conjecture this lower bound tight. would be interesting to design algorithms with VK regret or even optimal regret in this setting.
Remark 3.4 (Beyond the Linear Function Approximation). The work of Agarwal et al. [2] extends their results the kernel function approximation setting. We conjecture that our results can also be extended to RL with kernel and neural function approximation by the techniques in Yang et al. [39].
4 Proof of Theorem 3.1
Proof. Recall that B E N+ is the batch size, L = K/B is the number of batches, and ky (i (i-1)- B + for any i [L.. For any [K], we use tx to denote the k; satisfying k; S h
Moreover, we define the Bellman eтror
t = r + PA V Qh v(k E [K] H].
(4.1)
Here V and Q are the estimated value function and Q-function defined in (3.4), and IP, the operator defined in (2.2). Intuitively, (4.1) quantifies the violation of the Bellman equation in (2.1). With these notations, we have the following regret decomposition lemma.
Lemma 4.1 (Regret Decomposition). It holds that
Regret(K)) (K) =
(v (x - ViTh (<
~-***((ai))
Am
E [1Q >) T px) - [xx)]
policy optimization error
H
Em (1n, an) - Ex (2n, (n))
1=1
statistical error
Proof. This lemma is similar to the regret decomposition lemma in previous works [6, 30) on policy optimization. See I for detailed proof.
D

---

Lemma 4.1 shows that the total regret consists of the policy optimization enror and the statistical enror related the Bellman enror defined in (4.1). Notably, different from previous works [6, 30, 37, 14] that optimize policy in each episode, our algorithm performs policy optimization infrequently. Despite this, we can bound the policy optimization error in Lemma 4.1 by the following lemma.
Lemma 4.2. It holds that
E. (10 T7(- x (xaI) S 2BH*K log |A.
k=1k=1
Proof. See BB.2 for a detailed proof.
For the statistical error in Lemma 4.1, by the definitions the policy evaluation step in (3.4) and Bellman error in (4.1), we have
Pa. PA -P,
(4.2)
reward mismatch error
transition estimation enror
The following lemma establishes the upper bound of the cumulative reward mismatch error
E 1( (xn,))))))) E,+ [( (x),,)))))
(4.3)
1=1R=1
and thus relates the statistical error in Lemma 4.1 to the transition estimation error in (4.2).
Lemma 4.3. It holds with probability least 1 8/2 that
K
Ex (2h, an)l - Egg 15 (kh, an)))
K
H
Ex [(P h+1 Tpte h+ (m)),a)))
Polk vbc - h41
PAV. af))
k=1 11
1=
+ +BH + aH + VH
Proof. By calculation, we can show that the cumulative reward mismatch error in (4.3) is bounded by
Σ R
VI " & (x1)) error terms,
which represents the smoothness of adjacent policies. Our smoothness analysis leverages the value difference lemma (Lemma B. $B.1 in Cai et al. [6]) and the closed form of the policy improve- ment in (3.2). See $B.3 for a detailed proof.
Then we introduce the following lemma, which shows that the transition estimation error can be controlled by the bonus function.
Lemma 4.4. It holds with probability least 1 - -8/2 that
-2 min H, 1 (z, a)} s (PA P 5
for all a, a) E [K]
H 8 A.
Proof. The proof involves the standard analysis of self-normalized process [1] and a uniform con- centration of the function class of V h++ [17]. As elaborated in $1.1, calculating the covering num- ber of this function class challenging and requires some new techniques. See $B.4 for detailed proof.

---

Combining Lemmas 4.3 and 4.4, we have
k
h
T (8 an)
Byg (0 an)l)
K
H
2
min
(a a BH K + VšK..
k= A=1
Hence, it remains to bound the term Σ Σ min(H, (zh, a which is the purpose of the following lemma.
Lemma 4.5. It holds that
K
ΣΣ
min(H, The (1h af) SOUP +0
12)2//2 - with A = Σ==1 o( a (1 TT) Proof. For all k E [K], I = 3. (Ø (A
Ia. By doubling trick, we can prove that
K
H
K
H min (H, (x a)) + error terms,
ΣΣ
min 1 (x)),
- ΣΣ k=11=
which can be further bounded by elliptical potential lemma (Lemma D.5 or Lemma 11 in Abbasi- Yadkori al. (1]). See $B.5 for a detailed proof.
Finally, putting Lemmas 4.1-4.5 together, conclude the proof of Theorem 3.1.
Note the choice of the number of batches L determines the batch size B = K/L. We make the following remark to illustrate how the choice L affects the final regret, which indicates that our choices of parameters are optimal based on our current analysis.
Remark 4.6 (Choices of Parameters and Final Regret). If OPPO+ performs the policy optimiza- tion for L times, then by Lemma C.3, we have the complexity (logarithmic covering number) of policy class roughly (L)) (ignoring the dependency of and H). Furthermore, by the new self-normalized analysis in $C, we have 3 Ō(VT), which further implies that the model estimation error is bounded by 8 ΣxE Σ V ddx2 (A (At))1o(att Lemma 4.5). Meanwhile, by Lemma 4.2, we have the policy optimization error bounded by O(K/VL) = O(K3/4). By choosing = O(vK), we obtain a regret of order (KK3/4).
"o(a), at) I Ö(VLK) (cf.
5
Conclusion
In this paper, advance the theoretical study of PPO in stochastic linear MDPs and even adversarial linear MDPs with full-information feedback. We propose novel algorithm, namely OPPO+, which exhibits state-of-tte of-the--rttt regret bound compared to the prior policy optimization algorithms. Our work paves the way for future research in multiple directions. For instance, a significant open research question is to investigate whether policy-based algorithms stochastic linear MDPs like previous value-based algorithms [3, 14]. Additionally, an interesting direction is to derive K-regret bounds for adversarial linear MDPs with -nlornnfontnton or even bandit feedback.
achieve the minimax regret
Acknowledgements
This work was done while Han Zhong visiting HKUST, The authors would like to thank Miao Lu, Haipeng Luo, Tianhao Wu, and Wei Xiong for helpful discussions and feedback.
10

---

References
[1] Yadasi,, Y., Pál, D. and Szepesvári, C. (2011). Improved algorithms for linear stochas- tic bandits, Advances in neural information processing systems, 24.
[2] Agarwal, A., Henaff, M., Kakade, S. and Sun, W. (2020). Pe-pg: Policy cover directed ex- ploration for provable policy gradient learning. Advances in neural information processing systems, 33 13399-13412.
[3] Agarwal, A., Jin, and Zhang, T. (2022). Vo q::: Towards optimal regret in model-free rl with nonlinear function approximation. arXiv preprint arXiv:2212.06069
[4] Ayoub, A., Jia, Z., Szepesvari, C., Wang, M. and Yang, L. (2020). Model-based reinforcement learning with value-targeted regression. In International Conference on Machine Learning. PMLR.
[5] Brown, N. and Sandholm, T. (2019). Superhuman ai for multiplayer poker. Science, 365 885- 890.
[6] Cai, Q- Yang, Z., Jin, C. and Wang. Z. (2020). Provably efficient exploration in policy opti- mization. In International Conference on Machine Learning. PMLR.
[7] Desa-Bianchi, N. and Lugosi, G. (2006). Prediction, learning, and games. Cambridge univer- sity press.
[8] Dai, Y., Luo, H., Wei, C.-Y. and Zimmert, J. (2023). Refined regret for adversarial mdps with linear function approximation. arXiv preprint arXiv:2301.12942.
[9] Fei, Y., Yang, Z., Wang, Z. and Xie, Q. (2020). Dynamic regret of policy optimization non- stationary environments. Advances in Neural Information Processing Systems, 33 3743-6754
[10] Feng, F. Yin, W., Agarwal, A. and Yang. I.. (2021). Provably correct optimization and explo- ration with non-linear policies. In International Conference on Machine Learming. PMLR.
[11] Haarnoja, T., Zhou, A., Hartikainen, K.. Tucker, G., Ha, S., Tan, J., Kumar. V., Zhu, H., Gupta, A.. Abbeel, al. (2018). Soft actor-critic algorithms and applications. arXiv preprint arXiv: 1812.05905.
[12] Han, Y., Zhou, Z., Zhou, Z., Blanchet, J., Glynn, P. W. and Ye, Y. (2020). Sequential batch learning in finite-action linear contextual bandits. arXiv preprint a646::2004.06321.
[13] He, J., Zhao, H., Zhou, D. and Gu, Q. (2022). Nearly minimax optimal reinforcement learning for linear markov decision processes. arXiv preprint arXiv:2212.06132.
[14] He, J., Zhou, D. and Gu, Q. (2022). Near-optimal policy optimization algorithms for learning adversarial linear mixture mdps. In International Conference on Artificial Intelligence and Statistics. PMLR.
[15] Hu, P., Chen, Y. and Huang, L. (2022). Nearly minimax optimal reinforcement learning with linear function approximation. In International Conference on Machine Learning. PMLR.
[16] Jin, C., Allen-Zhu, 7.,, Bubeck, S. and Jordan, M. T. (2018). Is q-learning provably efficient? Advances in neural information processing systems, 31.
[17] Jin, C., Yang, Z., Wang, Z. and Jordan, M. (2020). Provably efficient reinforcement learning with linear function approximation. In Conference on Learning Theory. PMLR.
[18] Kakade, S. M. (2001). A natural policy gradient. Advances in neural information processing systems, 14.
[19] Kober, J., Bagnell, J. A. and Peters, J. (2013). Reinforcement learning in robotics: A survey. The International Journal of Robotics Research, 32 1238-1274.
[20] Kong, F., Zhang, X., Wang, B. and Li, S. (2023). Improved regret bounds for linear adversarial mdps via linear optimization. arXiv preprint arXiv:2302.06834,

---

[21] Lattimore, T. and Szepesvári, C. (2020). Bandit algorithms. Cambridge University Press.
[22] LeCun, Y., Bengio, Y. and Hinton, G. (2015). Deep learning. nature, 521 436-444.
[23] Luo, H., Wei, C.-Y. and Lee, C.-W. (2021). Policy optimization in adversarial mdps: Im- proved exploration via dilated bonuses. Advances in Neural Information Processing Systems, 34 22931-22942.
[24] Mnih, V., Kavukeuoglu, K., Silver, D., Rusu, A. A., Veness, J., Bellemare, M. G., Graves, A., Riedmiller, M., Fidjeland, A. K., Ostrovski, G. et al. (2015). Human-level control through deep reinforcement learning. nature, 518 533-533.
[25] Modi, A., Jiang, N., Tewari, A. and Singh, S. (2020). Sample complexity of reinforcement learning using linearly combined model ensembles. In International Conference on Artificial Intelligence and Statistics. PMLR.
[26] Neu, G. and Olkhovskaya, J. (2021). Online learning in mdps with linear function approxi- mation and bandit feedback. Advances in Neural Information Processing Systems, 34 10407- 10417.
[27] Ouyang, L.. Wu, Jiang, X., Almeida, D., Wainwright, C., Mishkin, P., Zhang, C., Agarwal, S., Slama, K., Ray, A. et al. (2022). Training language models to follow instructions with human feedback. Advances in Neural Information Processing Systems, 35
[28] Schulman, J., Levine, S., Abbeel, P., Jordan, M. and Moritz, P. (2015). Trust region policy optimization. In International conference on machine learning. PMLR.
[29] Schulman, J., Wolski, F., Dhariwal, P., Radford, A. and Klimov, O. (2017), Proximal policy optimization algorithms. arXiv preprint 1707.066777
[30] Shani, L.,, Efroni, Y., Rosenberg, A. and Mannor, S. (2020). Optimistic policy optimization with bandit feedback. In International Conference on Machine Learning. PMLR.
[31] Sherman, U., Koren, T. and Mansour, (2023), Improved regret for efficient online reinforce- ment learning with linear function approximation. arXiv preprint arXiv:2301.1300
[32] Silver, D., Huang, A., Maddison, J., Guez, A., Sifre, L., Van Den Driessche, G., Schrittwieser, J., Antonoglou, I., Panneershelvam, V., Lanetot, M. et al. (2016). Master- ing the game of go with deep neural networks and tree search. nature, 529 484-489.
[33] Silver, D., Schritwwieser, J., Simonyan, K., Antonoglou, I., Huang, A., Guez, A., Hubert, T., Baker, L., Lai, M., Bolton, A. et al. (2017). Mastering the game of go without human knowl- edge. nature, 550 354-359.
[34] Sutton, R. S. and Barto, A. G. (2018). Reinforcement learning; An introduction. MIT press.
[35] Wagenmaker, J., Chen, Y., Simchowitz, M., Du, S. and Jamieson, K. (2022). First-order regret in reinforcement learning with linear function approximation: A robust estimation ap- proach. International Conference on Machine Learning. PMLR.
[36] Wang, T., Zhou, D. and Gu, Q. (2021). Provably efficient reinforcement learning with linear function approximation under adaptivity constraints, Advances in Neural Information Process- ing Systems, 34
[37] Wu, T., Yang. Y., Zhong, H., Wang. L., Du. S. and Jiao, J. (2022). Nearly optimal policy opti- mization with stable at any time guarantee. In International Conference on Machine Learning. PMLR.
[38] Yang, L. and Wang, M. (2019). Sample-optimal parametric q-learning using linearly additive features. In International Conference on Machine Learning. PMLR.
[39] Yang, Z., Jin, C., Wang, Z., Wang, M. and Jordan, M. I. (2020). On function approxima- tion in reinforcement learning: Optimism in the face of large state spaces. arXiv preprint ar 1.04222.
12

---

[40] Zanette, A., Cheng, C.-A. and Agarwal, A. (2021). Cautiously optimistic policy optimiza- tion and exploration with linear function approximation. Conference on Learning Theory. PMLR.
[41] Zhang, Z. Yang, J., Ji, X. and Du, S. S. (2021). Improved variance-aware confidence sets for linear bandits and linear mixture mdp. Advances in Neural Information Processing Systems, 34 4342-4355
[42] Zhong, H., Yang, Z., Wang, Z. and Szepesvári, C. (2021). Optimistic policy optimization is provably efficient in non-stationary mdps. arXiv preprint arXiv:2110.08984.
[43] Zhou, D. and Gu, Q (2022). Computationally efficient horizon-free free reinforcement learning for linear mixture mdps. arXiv preprint arXiv:2205.11500
[44] Zhou, D., Gu, Q. and Szepesvari, C. (2021). Nearly minimax optimal reinforcement learning for linear mixture markov decision processes. In Conference on Learning Theory. PMLR.
[45] Zhou, D., He, J. and Gu, Q. (2021). Provably efficient reinforcement learning for discounted mdps with feature mapping. In International Conference on Machine Learning. PMLR.
13

---

A Further Elaboration of Challenge in Section 1.1
Regarding the technical challenges involved in extending OPPO [6] linear MDPs, we provided more detailed explanations below.
Technically, for linear mixture MDPs (Equation (B.20) in OPPO paper [6]), they need to analyze
Σ (1) al)
(Ak)-1
Since V4+1 adapted to FR.h.1 { of ( (70 fr")rel (at at) hem they can bound this term with classical self-normalized process analysis directly (see Lemma D.1 in Cai al. [6]).
In contrast, for linear MDPs (see e.g., (B.26) in our paper or Lemma B.3 in Jin et al. [17]), we need to bound the term
Σ ol añ) (1 - (PAV (PA
(AR)-1
Since V is NOT adapted to FR.A.1 = {(I need to perform the uniform concentration the function class of V h--1 The challenge of calculat- ing the covering number of this function class has been elaborated Challenge Section 1.1.
(re hem. We
B Missing Proofs of Main Theorem
B.1 Proof of Lemma 4.1
Proof. Our proof relics on the following value difference lemma in Cai et al. [6]. Lemma B.1 (Value Difference Lemma). Let {TT.. Jee and / {T/ Nejen be two policies
and Q {Qn S x A + R. Ne(H) be any Q-functions. Moreover, for any E [H]. we define value
function Vn= S + R by letting (x) = (Qn(x,) :), (- x)). Then for any ko E [K] we have
H
(i(x1) - (x1) =
E. (QQn ) m. mx) T/6 xx))
H E. (Qn an) (r + PA an)]
A=1
Proof. See $B.1 in Cai et al. [6] for a detailed proof.
Back our proof, for any k [K]. we have
VT (x1) V.TH . (x1) = Vi re - V/
+V((21) V (x1))
(B.1)
(i)
Applying Lemma B.1 with π nt, N/' T., and Q = (Q2) IhEH), we have
K
K
H
= B [1) (A + xx))
E 18) ax),,
(B.2)
k= h
R
h - V h+1 is the Bellman error defined in (4.1). Similarly, applying Lemma B.1 where 5/¹ r r² and Q (Q hee we obtain
with ग
K
(ii)
E
16) ax)]]
(B.3)
Rim
P
14

---

Plugging (B.2) and (B.3) into (B.1) and then taking summation across & E [K], we have
Regret ()
(a
VIT - (xf))
K
H
Bx
T.a (xa)) - (-1=)))
K
H
BB (nn) Exn an))
k=11=1
which concludes the proof of Lemma 4.1.
B.2 Proof of Lemma 4.2
Proof. Recall that B N+ is the batch size, ki = (1-1) 1). B + and L K/B. Fix h E [M]. By the multi-batched updating rule, we have
B [10 :,, m an) T/C (111))))]] = Σ E. [10 (1r, m (1 Th Tht( (- (-1xx))) [xa)))]]
(B.4)
To derive the upper bound of (B.4), we need the following lemma.
Lemma B.2. For any (i, h, an) E [Z] x [H] x S. holds that
10 (zn, -), T (-1 mx) Th ( (x))
S a (T( an) T xR)) (T
( Th R4t1 (. [/a))
2
Proof. By the updating rule (3.2), we have
Th xn) explalx (xn,
Kh
kit1 (- (x)) EnEd Th ki (a an explact a})
(B.5)
For ease of presentation, we denote T EaEath (a and expla( (In a)}. Then we have
(aQ)i (an, ,), (t(( (NN) - Th 1 (112)))
(log Y log A R:+1(. (- mn) log R (- xR), m xn) FA Rit1 (- xnn)
= (log Th k (- xT) - log " (- xn). ( mn) Th ki+1 (- xN))
(B.6)
where the first equality uses (B.5), and the second equality follows from the fact that EnEA [/((a)
In) Th k.t1 (al xn) = 0. Rearranging (B.6) gives that
(B.6) = log
(- xn)
-.( (88) - (10g8
T (
mp( an))
5c xn)
ke+1 (. (20)))
Th Ri41 (. zn))
{ log
m xn) ox 2:12 (raa))
-L(
| (nn) || T (- xx)) KL ( and a
kit (- xn))
KL( kit1( xx क. (: mn)).
(B.7)
Furthermore, we have
(a (Hn, -), m (xA) 7/i (- xx))
= (aQ) (zo. :), T. (mn) - Th
ke+1 (x))))) - (a (In, -), ah ke ( (m))))) - Th ket1 (..1(.11)) (1x)))
<TT(TT mn)) || m (: (x)) KT. (mp(( xnn) Th (rr))))
ks
-KI(T kiti a1)) A [x)) + aH || (- pmx)) a
Rer (-1
(B.8)
15

---

where the last inequality uses (B.7), Cauchy-Schwarc inequality, and the fact that 110 oloo I H. By Pinsker's inequality, we have ( Together with (B.8), we obtain that
k+t1 ( (- 2x, l| n (- zx))
2 1 - (-
an) "x (- an 1/)//
(a0% (rh, )) ( [m)) ki (m))
( (nn)
x [a)) (L mnd Th u. xk))
| R [m) -m a. m + aHl || (-12n)
ke+1 2. (-12n)]l
Th
$ KL ( an)
x =n)) - KL (- mn) Th ki-i(
xa)) + a H² 12,
(B.9)
where the last inequality uses the fact that max ( (-y /2/22 aH y} a² a2H2222 Rearranging (B.9) concludes the proof of Lemma B.2.
By Lemma B.2, we further have
aH
Ex
KL
mh)
Th (- Ib)) (
"h
(- Ri+1 FA
[|1n)]]]]
(B.4) < B
i=1
Ex
KL (
ky (: xN))
FA) (T
Th
kLt1 (-
xhh)]]
=B.
2B
aH
B
lololAA a
(B.10)
2
where the equality uses the fact that L K/ B, and the last inequality uses the non-negativity of KL-divergence and the fact that = Tr, is the uniform policy. Combining (B.4), (B.10), and
/2B [AI(K we obtain for all h E [H]:
K
Ex [1Q) (o) m In) T [+aii| S v 22BHKK log Al.
(B.11)
Telescoping (B.11) across h [H] concludes the proof of Lemma 4.2.
B.3 Proof of Lemma 4.3
Proof. Recall that B N+ is the batch size, h; (i - (1) 1 and T.
K/B. Fix h [M]. We
have
K
K
Em 10% an) =
Σ
Ex (r an) + PP
- Q (1t, an)
k=1
E (sn,, as) + PA A (In, an) - 2% (I ax)
(B.12)
K
Bx Ir an) - - (xn, an) +
Σ Brr - Ph t (z an)], k=1
k=1
where the first equality uses the definition of ta and the updating rule, and the second equality uses the definition of Q Fk + PA
V in (3.4). Furthermore, have
E (rh, ax) Fhe (xn, an)l
Σ E (rh(
B
B
E.
(F)t
(In, an)
k=
K
1p-1
Ex [r (2), an)l
Σ
Ex (r an)
A=
K
Σ
Ex (an,
(B.13)
k= L=K-B++ B+1
16

---

where the first equality uses the updating rule, the second equality follows from the definition of F in (3.5), and the last inequality is obtained by the fact that || I for any (k, h) E [K] x [H]. Combining (B.12) and (3) and then taking summation across h E [ we obtain that
K
K
H
E. (6% a4h
E.
(PAV24
Ph ( an)l + BH.
(B.14)
A=1
k=1b=1
On the other hand, similar to the derivation of (B.12), we have
Ex 10% (1n: (n))
K
K Σ
Ex's & [F (Ih, an) - (sn, an)l +
Ega
[1P
Vit
IP (an (B.15)
A=1
For the first term of (B.15), by the updating rule and calculation, we have Exda (rth (It, an) rh an)] = Σ E I
h
(Ih, anl
Bx I (on. and
k=
L har-1
E Irx (2n, and
B (ax an)
b=nk
R R=
k+1--1
EE Ea (2 an)) - E
b=
(B.16)
where the last inequality uses the fact that Ek=kz Ceerb an) S 0. Summing over h [H] in (B.16) gives that
B ( (IR, and
rh((saaan)
k=
L-1 R141-1
(v(thil2)((01)) - VT (x1))()
k=
I- R44 -1
11
=
Σ Σ
E B (t
xn), Th ket1 xn) - T (- xx))
(B.17)
k=
h=1
where the last inequality uses the value difference lemma (Lemma B.1). By the policy updating rule in (3.2), we have
Th (: (n) exp (aQ)i (zh,
R++1 (. Inn
Th
EaEA Tl (a xx)) exp (aQ" (rı,
for any 2n, E S, which implies that
T T (- In)
Ensa (i xN) exp (aQ) (In, a))
T 1/-1 (- 1nh)
exp (aQhi (zn:-))
EnEA Th (a xh) exp(- (xp(-aH) 2 2 1-aH exp(aH)
where the first inequality follows the fact that 0 < (.,.) < H, and the last inequality uses the basic inequality exp(y) > 1 y for all R. Together with
ks (n) Th
Ks+1 (- xx) m (- 2T) ah ki+1 (. xxn) (1 K
ki+1
(- x
T
17

---

we further obtain
Ri-1 (.
xxx (- xn.) I aH " #i-1 (. x.
(B.18)
AA
for any 2h E S. Plugging (B.18) into (B.17) gives that
L-1
1 -1
H
(B.17) S aH Σ
Σ Σ
B
1(0
(Ins ) Th ki (- (x1aaM111 S aH
(B.19)
Amm
A=1
where the last inequality follows from the fact that Qh * (., I H. Plugging (B.17) and (B.19) into (B.15), we have
K
E (an,
an)
B+
( W4i PAVi44)(( an)] aH²K
k=
R=1
K
H
P v PA ( ab) + aa + HHKi,
(B.20)
where the last inequality uses Azuma-Hoeflding inequality. Putting (B.14) and (B.20) together, conclude the proof of Lemma 4.3.
B.4
Proof of Lemma 4.4
Proof. Recall that
PA (2 min(o(s)) Twutt + (. (B.21)
where wh and 1 take form
whe (A -1
pa 07) Via (1h+1)) (..) B (A2))))(
(B.22)
Here A is the covariance matrix:
A Σ o( Aolth af) + Ia-
(B.23)
Back to our proof, for any (x, a) 8 A. have
(Pn v (2, = ((x,a) ( (un, Viti)s
((x,,a) (air,a)((())) (AA)) (ue, V
((2, (eT,a)T(44 TA(())
pl a (o at) T (un, Vot + X (pey V viti's)
= ( ((A)))
(12,, ah) (PA ( ah) + A (Ma, Vhl (ssiss))
(B.24)
where the first and the last equality follows from the definition of linear MDP (Definition 2.1), and the third equality uses (B.23). Putting (B.22) and (B.24) together, we have
((x, a) T wht - V. h- (x, a)
((5 TA
(( ah) (Vit (3/+1) (PaV 1 (4 (N))
(B.25)
(4)
A A..(1,))) (A ( v(41)s.
(An)
18

---

For Term (+) in (B.25), by Cauchy-Sehie Sanchy-Schwarzae inequality, we have
(+) / al a) Σ pl 07))
(PA
(
(1
(044 H(x a)T (A -
(B.26)
where the last inequality follows from the following lemma.
Lemma B.3. Fix 8 E (0, 1]. It holds for all (k, h) E [K] x [H] that
Σ pa a7)
(PAV (47 oh1)
(172)-1
Proof. See $C for detailed proof.
For Term (**) in (B.25), we have
(**) S A Volz,a) (
(e Vht (
S VA
(1u V 1sl12
S VVdH2
V 66x a) (A4)))
(B.27)
where the second inequality uses the fact that A Ia 3 A and last inequality follows from Kum, issll < Hvd, which is implied by Definition 2.1. Plugging (B.26) and (B.27) into obtain
(B.25), together with À
[ō(x,a) aaTTaan wht 1=, (z, a)l //0(z, (A)) (o,, (2)
(B.28)
in for any (z, a) E 8 A with O 0(d/41114/423)) Together with the definition of fat vl,
(B.21), we have
(P V -
Tatx 22 h h+1 ())
(PA, ( a) min a) wh (z, (2,0),
max (Py, (2, a) - o(x, Tw - a), (Pn vhh (z, - (H (H),
< max (0, 0} = 0,
(B.29)
where the last incquality uses (B.28) and the fact that / S H Moreover, by (B.28), we have
(P Vic Pa
v (x, 2 (Pr V4e
h (ar o(x, Tw (x)
2 (2,
(B.30)
Combining (B.29), (B.30), and the fact that VT V4
-pt ().)) 2-2H, obtain
-2 ( H, T (z, a)} < (P, h+1 - p ((r,a) 10
which concludes the proof of Lemma 4.4.
B.5 Proof of Lemma 4.5
Proof. For ease of presentation, we define
= -3/0(.))
A
2l2% aooak aT) + Alas
(B.31)
for all (k, E [K] x H]. Then we have the following lemma, which uses the elliptical potential to bound Σk D 1 (2).
19

---

Lemma B.4. It holds that
K
H
r
(
1=14=1
Proof. By the definition of 2 in (B.31), we have
K
H
H
3
/olzh, (A at)
(B.32)
k=1==
k=
Applying Cauchy-Schwand inequality to (B.32), we have
1/2
3
K
( a/t)
h=1
H
[dot(A +1) det(AA))
1/2
3
2K
log
(B.33)
where the last inequality uses the elliptical potential lemma (Lemma D.5). For any h E [M]] we have
K
A = A.
la.
A
K+1
Σ
ol*h a (at of) + Ala 3 (K + A) la=
(B.34)
where the inequality uses the fact that ( s 1. Plugging (B.34) into (B.33), we have
ΣΣ (a a H3. 2dK log
K +
1/2
Together with the facts that 1, (4 1/22) we conclude the proof of Lemma B.4.
l) with E (0, 1]. and B
We also need the following lemma to connect the quantity Σk Σ/1 (a a in Lemma B.4 and our target Σk k= Σ# min H, The (a% (()). Lemma B.5. For any h E [H], we define the set &
En {k: t (a / 2}.
(B.35)
Then we have
E < 12
Proof. For En, there exists i E [T.] such that h; S K kit1- Then we know & Ki which further implies that
(A (F11)
(ee((At))
[0 at) (AA)) Mott, a/t Mir (A))) - af)
log
2 log
2 log
(ef()
(At(
Like (a att)
2 log
[h of)
where the first inequality follows from the fact that A Ki 2 A4. the second inequality uses Lemma D.6, and the last equality is obtained by the definitions of D and p in (B.31). Together with the definition of &, in (B.35), we further obtain that
det(A Rc:1))
log
2 2 2lo 2.
(B.36)
det(A
20

---

Meanwhile, we have
d det(A
(1
det(A,, -111 dot(A
K < (x)
log
= log
S d. log
(B.37)
A
1=1
where the last inequality follows from the facts that
A X- la.
A K+I
E pl o0(t, + P7 3 (K X) -r.
Here the last inequality uses ( ) S Combining (B.36) and (B.37). we have
{ E [L] log
/det(A (
}
dloog (KK + A)/A) log 2
(B.38)
det(A
Since each batch contains B episodes, we obtain that
Eu & B B. E [Z] : log
[
(det(A ) - (11/222111111 (
where the last inequality uses À 1, log(dH Al/5), B = Vd3 K and (B.38). Therefore, conclude the proof of Lemma B.5.
Back to our proof Lemma 4.5, we have
K
H
H Σ
H Σ
min H, 1 (a a
Σ KEEA
min
(x a
min (a
1=
T=
A=11 KgEn
(B.39)
For any h E [H] and is En, by the definition of En, have
min H, 1he (zy, a S min 21 (a aH) s (a at). 21,
(B.40)
Combining (B.39), (B.40), and the fact that min 1 (a a < H, we have
K
H
H
K
H
Σ
min Hin(HII The (x ah) s H
E
Σ
Th
aH)
H23/4
0 1),
where the last inequality uses Lemmas B.4 and B.5. Therefore, we conclude the proof of Lemma 4.5.
C Proof for Concentration of Self-Normalized Processes
Proof of Lemma B.3. By the previous concentration lemma of self-normalized process (Lemma D.3), for any 8' E (0, 1], > 0, and (k, h) E [K] x [H] we have
12
Σ
(1 af) (V (xh+)) (PA V (1%, (x))))))
(1/))-1
d
log ( + log
N6(Vi+1))
2
S 4H²
(C.1)
2 A
8'
A
with probability 1 - 8'. Here Ne(V is the e-covering number of function class D h+t1 which is defined by
v h+1
- : oh.,, &
(C.2)
21

---

where 2 and IH are Q-function class and policy class, respectively. Specifically, 2 is function class with the following parametric form
2 = -1r + +10 w +
h1+ + 1|wl22 I H HVdK/A, Amin (A) 2 2}. (C.3)
Here uses ||wf+11l2 ll2 S H / dK/A A (Lemma D.I) and Amin (A À to ensure that Qh+1
2h+ Meanwhile, the policy class 1 is defined as
Th ((( (2(-1-)) exp Σ (al().)) Q, E Vi where max(i: (i: K (k).
(C.4)
Notable, here & L since our algorithm only has L batches. Also, d in (C.2) belongs to this policy class since it takes the following form
ExplE (
"t Th+1 (a (x)
En'EA exp(Ei aQ (z)
For policy class defined in (C.4), we define its covering number with respect to the following distance
dist(n, x²) sup #
[- x) 7'(: x)
The following lemma connects the covering number of value class in (C.2) covering numbers of the Q-function class (C.3) and the policy class in (C.4).
Lemma C.1. It holds that
Ne(hh S Neep2(Oh+)) -Nerean) (Uh..))
Proof. See 1 for detailed proof.
Following the standard covering argument (Lemma D.4), can derive an upper bound for Ne/2(2f, (1)+ Nooveee,,Ne/221e (1T++1) relatively difficult bound since the log-covering num- ber of |A| -imeenssioa probability distribution is Ō([A)). Fortunately, have the following lemma that utilizes the structure of policy class (C.4) and converts the covering number of the pol- icy class the covering numbers of several Q-function classes.
Lemma C.2. It holds that
Ne
1) & II N (16GHH)) (Qt
i=1
Proof. See SC.2 for detailed proof.
Note that À and B 0(d//41k1/4,11)) Meanwhile, let 1/K and 8' 6/2. Combining (C.1) with Lemmas C.I, C.2, and D.4, we have
/2B log AI/(KH)), log(dH ((
o( ah) (v (x (Px v 1z an)
2OVd2112-- (N
=O(d/A
which concludes the proof of Lemma B.3.
22

---

C.1 Proof of Lemma C.1
Proof. Suppose (i) O 1212 is an e/2-net of 0h+1 with | 1222411 N2/2(Q 1): and (ii)
11 (/22))),-11 is e/(2f))-net of 11 with II [///2))) = (Ul Then we show O 2//2.411 x I */(2m),441 induces an g-net of Va Veti and thus obtaining the desired result. Specif- ically, for any V (Q(.)). (- | ())) with (Q,x) E O x I - we can find (Q', (7) Qh 2//2,4+1 1 E412)), such that
sup [Q a) - (m.a)ExxA
sup
| | x) x'( 1)) & e/(2H).
(C.5)
sES
Let == = (Q'(,,) ( 1)), we have
sup
V(x) [x()) sup =éS
(Q(x, (. 2)) - (Q'(z, n =))
ZES
sup eE
(Q(x,) Q' (x,,,), (- (-1 |x)>| + sup
< (Ix, -) .( x)) 7' (-1x)))
S
sup Q(xx (x.a)ESxA
sup
|| x)
#ES
se/2 8/2
where the first inequality follows from the triangle inequality, the second inequality uses Cauchy- Schwarz inequality and the fact that ||Q'| Il S H, and the last inequality follows from (C.5). There- fore, we conclude the proof of Lemma C.I.
C.2 Proof of Lemma C.2
Proof. Suppose O (2) is the minimum &² (16 of O for all i [4] Then for any a x exp(a E/= Q+) with Q 2 for all E [1] we can choose (o)
ot 2e ((66(HHH))))41) such that
E²
sup 1Q,(1, a) (((x, S 16alH2 (x.a)eSxA
vie [T].
(C.6)
Hence, we have
g²
sup (x.a)ESxA
a -a
a (((,a)) S sa Σ
sup (x.0)ESxA
(Q((, Q((2,)) S 16
(C.7)
where the first inequality uses the triangle inequality and the last inequality follows from (C.6). Then we use the following lemma to establish the upper bound for suPwes [|T([ (x) T'(- x)]l
Lemma C.3. For ,, n' E A(X) and Q + R if T(-) x exp(Q(-)) and 7'(-) x exp(Q'()), we have
IT 2'11 S 2V QQ O'
Proof. See SC.3 for a detailed proof.
By Lemma C.3, we have
sup #ES
|| 1x) 7'(: 11)111 2
sup (ma))SxAA
a Σ Q1(z, - a Σ (x) a) s E
2H
1=1
where the last inequality follows from (C.7). Therefore, we have
Ne/e2 (1 s II
[e /160)1)))))) (Qth))
==1
which concludes the proof of Lemma C.2.
23

---

C.3 Proof of Lemma C.3
Proof. Since (-)) exp(Q(.)) and (-) exp(Q'()), we have for any x E X:
π (σ)
exp(Q(x))
exp(a
(x) exp(Q((x)) Exexexp(Q(
Note that for any x E X we have
exp (z)) exp(Q(2) - Q'(x)) z exp(11 Q'1loo)
exp(Q(x))
exp( (x))) cxp(Q'(x) Q(x)) = exp(llQ Q')loo)
exp(Q(=))
which implies that
a (xx exp(1l ('1loo) exp(1lQ - (11))) exp(xxx)) cxxp(2llQ-Q) 2o)
+2x))
Exee exp(Q(x²))
Hence, we have
(Φx) +'xx) S 2|1Q Q'1lx
KL(T||T)) = Σ x()) log
Σ π(2) = 2/1Q - 1'1ooo
FEX
xE
Finally, by Pinsker's inequality, we have
111 S /2 =
which concludes the proof of Lemma C.3.
D Auxiliary Lemmas
Lemma D.I. For any hi, E [L] x [H], the linear coefficient wh defined in Line 12 of Algrotihm
satisfies
|| h S H /Kk/
Proof. Fix (i, h) E [L] x [H]. Our proof follows the proof of Lemma B.2 in Jin et al. [17]. For any E IRdd with ||ui|a = 1, by the definition of wi we have
k- Σ
1 h =
1
(A
6(0%, ah)
V (+t((1++1)
Since IIV 1loo S H, we further have
10
w
ky
H
(A
kg
1/2
k
1/2
< H.
T (A -
p( ah) (
H /dK/
where the second inequality obtained by Cauchy-Schware inequality, and the last inequality uses Aīa A h; S K, [|e|2 = and Lemma D.2. Hence, we have
| ku ll2 sup To w < H dK/A,
||
which concludes the proof of Lemma D.I.
Lemma D.2. Let A, A la Et T'σT with di E IRd and A > 0. Then we have
Σ (i(AA)) : d.
24

---

Proof. See Lemma D.1 in Jin et al. [17] for a detailed proof.
Lemma D.3. Let (I, E S) and { E [ with | I be stochastic processes adapted to the filtration {Fr) Let A = E Φト07 + X La. Then for any E (0. 1], with probability at least 1 - 6, for all k E N and function V E V satisfying supzes IV [V() S H, we have
d
k+
k
NC
8
Φ (V((TT))) ([ F-I)
< 4HH.
log
log
A7
2
A
where Ng is the e-covering number of the function class with respect the distance dist V') supzes (V) (a)).
Proof. See Lemma D.4 of Jin et al. [17] for detailed proof.
Lemma D.4. For any [H), let On be function class mapping from S A to R with the form
2x(3.) = r(s)) ) + min { TT) w 8 --)))- - -1
where r -8xA- (0, 1]. //1l S L, Amin (A) 2 Assuming | ))12 S and 3 > we have (o I d'log(1 + 4L/E) + d² log (1 + 8d (A=)),
where (Q)) is the e-covering number of the function class Qs with respect to the distance dist(Q, Q') sup(s,a)ESxa QQ a) Q'x a)}.
Proof. See Lemma D.6 of Jin et [17] for detailed proof.
Lemma D.5 (Elliptical Potential Lemma). Let fΦr E R satisfy l| 1 1 for all t N Moreover, let Ag RRddd be positive-definite matrix with (Ao) and A, = Ao + E!-1 2:00 for any & N+, Then for any N+, we have
det(Ac+11) det((A))
/de((A++1) det(Ai)
log
Σ
S 2lo
Proof. See Lemma 11 of Abbasi-Yadkori et al. [1] for detailed proof.
Lemma D.6. Suppose A, A' E Rddd are two positive definite matrices and satisfy A 3 A', then for any Rd, we have
dct(A') x AAx det(A) Ar
Proof. See Lemma 12 of Abbasi- Yadkori et al. [1] for detailed proof.
25


Reviews:
[{"review_id": "YsJmLpAnUV", "reviewer": "Reviewer_t7wE", "summary": "This work resolves the known issue for generalizing the policy-based algorithm proposed in [Cai el al.] for linear mixture MDPs to linear MDPs, by multi-batch updating and a bew covering number argument. The proposed model-free policy optimization algorithm advances the theoretical study of PPO in adversarial linear MDPs with full-information feedback.", "questions": "1 in Remark 3.3, the authors claim that they achieve the state-of-the-art regret bound for adversarial linear MDPs with full-information feedback. does it mean their result matches or improves the best existing result in linear MDPs? It would be better to give the reference of the best known exisiting result here.\n\n2 Equipped with the new proposed techniques, is it possible to improve the result by refined analysis?\n\n3 It seems the proposed novel techniques are specialized for policy-based algorithm for linear MDPs. Can the authors comment on the impact of the new techniques? For example, by applying those techniques, there is any existing result that can be improved or any hard problem that now can be solved.", "limitations": "N/A", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "1 This work resolves the issue in generalizing the policy-based algorithm in [Cai. el al.] for linear mixture MDPs to linear MDPs.\n\n2 Besides stochastic linear MDPs, the proposed algorithm can handle adversarial rewards with full-information feedback.", "weaknesses": "1 Full-information feedback instead of bandit feedback is considered.\n\n2 The proposed novel techniques developed in this work are insufficient for the policy-based algorithm to achieve the minimax optimal regret. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your review and positive feedback. We will try to address your concerns in the following.\n\n\n**Q1:** In Remark 3.3, the authors claim that they achieve the state-of-the-art regret bound for adversarial linear MDPs with full-information feedback. does it mean their result matches or improves the best existing result in linear MDPs? It would be better to give the reference of the best known exisiting result here.\n\n\n**A1:** To the best of our knowledge, there is no previous work that mainly focuses on the adversarial linear MDPs with full-information feedback. However, there are two recent works ([1] and [2]) studying the more challenging adversarial linear MDPs with bandit feedback and their results can directly imply the $\\tilde{\\mathcal{O}}(d^{2/3}A^{1/9}H^{20/9}K^{8/9})$ and $\\tilde{\\mathcal{O}}(dH^{2}K^{6/7})$ regret. We have discussed these two related works in the introduction and related works. We will add more discussions in Remark 3.3. Thanks for your suggestion.\n\n\n[1] Dai, Y., Luo, H., Wei, C.-Y. and Zimmert, J. (2023). Refined regret for adversarial mdps with linear function approximation. arXiv preprint arXiv:2301.12942\n\n[2] Sherman, U., Koren, T. and Mansour, Y. (2023). Improved regret for efficient online reinforcement learning with linear function approximation. arXiv preprint arXiv:2301.13087\n\n**Q2:** Equipped with the new proposed techniques, is it possible to improve the result by refined analysis?\n\n\n**A2:**  We think it is possible to improve the result by refined analysis. For instance, if we only perform the policy updating rule $\\log K$ times by the doubling trick on the covariance matrix, the model estimation error is at the order of $\\tilde{\\mathcal{O}}(\\sqrt{K})$. However, based on our current analysis, the policy optimization error term will be linear in $K$. If we can make a refined analysis for this term, then we can derive a $\\tilde{\\mathcal{O}}(\\sqrt{K})$ regret as desired. To progress towards a minimax regret bound, techniques in [3] and [4] might be helpful. Thanks for your question, and we intend to delve deeper into these challenges in our future explorations.\n\n[3] Agarwal, A., Jin, Y. and Zhang, T. (2022). Vo q l: Towards optimal regret in model-free rl with nonlinear function approximation. arXiv preprint arXiv:2212.06069.\n\n[4] He, J., Zhao, H., Zhou, D. and Gu, Q. (2022). Nearly minimax optimal reinforcement learning for linear markov decision processes. arXiv preprint arXiv:2212.06132.\n\n**Q3:** It seems the proposed novel techniques are specialized for policy-based algorithm for linear MDPs. Can the authors comment on the impact of the new techniques? For example, by applying those techniques, there is any existing result that can be improved or any hard problem that now can be solved.\n\n**A3:** Based on our new techniques, we improve existing regret bound for adversarial linear MDPs with full-information feedback. Also, we achieve the SOTA regret bound compared with existing policy-based algorithms for stochastic linear MDPs. In our view, these two problems are important and hard. Moreover, our techniques may have several potential applications:\n- Application to multi-agent RL: \n  - In linear Markov games, the covering number issue of value function class still exists and even more severe since the Nash equilibrium maybe stochastic. Our algorithm design and accompanying covering number analysis offer a potential avenue for understanding policy optimization in unknown Markov games. Here we remark that previous works (e.g., [5]) mainly study policy optimization in Markov games with known transitions and rewards. \n  - The statistical hardness of learning Markov games with adversarial opponents is well-established [6]. Our smoothness analysis could potentially shed light on this complex challenge, especially under the assumption of \"smooth\" policy changes by the adversary.\n- Application to adversarial decision making:\n  - Our algorithm design (especially policy evaluation via average rewards) seems new and may motivate more adversarial decision making problems and algorithms. For example, an interesting finding is that our algorithm does not need to know reward functions at the end of each episode (i.e., full-information feedback). Instead, OPPO+ only requires the average reward function at the end of each batch. This paves the way for tackling a novel class of adversarial decision making problems, where the learner interacts with an adversary and receives the average reward function (or the sum of reward functions) after a set number of episodes (e.g., 100 episodes). Finding more motivational examples of this type of problem and providing more efficient algorithms will be interesting. \n  - Notably, our algorithm is a low switching (multi-batched updating) algorithm for adversarial linear MDPs. We hope algorithm design and analysis can motivate further understanding of low switching algorithms in adversarial decision making.\n\n\n[5] Policy Optimization for Markov Games: Unified Framework and Faster Convergence. Runyu Zhang, Qinghua Liu, Huan Wang, Caiming Xiong, Na Li, Yu Bai\n\n\n[6] Learning Markov Games with Adversarial Opponents: Efficient Algorithms and Fundamental Limits. Qinghua Liu, Yuanhao Wang, Chi Jin.\n\n\n**Q4:** Weakness: (i) Full-information feedback instead of bandit feedback is considered; and (ii) the regret bound is not minimax optimal.\n\n**A4:** Yes, you are right. As we have discussed in our paper, our work cannot tackle these two challenges. These are important open questions and we hope these problems can be addressed in future work. Thanks for your questions."}, {"review_id": "5m18vF1u8q", "reviewer": "Reviewer_c9AM", "summary": "This paper studies the theoretical performance of an optimistic variant of PPO in episodic adversarial linear MDPs with full-information feedback (i.e., without assuming the reward functions are linear in the feature map), and establishes a regret bound of O(d^3/4 H^2 K^3/4) that matches the optimal regret bound in both stochastic linear MDPs and adversarial linear MDPs. The authors also introduce a new multi-batched updating mechanism to enable a new covering number argument of value and policy classes in their theoretical analysis.", "questions": "1. In the introduction, the authors mentioned both Cai et al. and He et al. that study linear mixture MDPs are implemented in a model-based manner, whereas existing theoretical studies in linear MDPs are typically value-based methods. However, from the algorithmic perspective, algorithms in Cai et al. and He et al. also perform regularized least-square approximation on value functions in the policy evaluation step. Do you treat all algorithmics that tries to explicitly learn /approximate the transition model (i.e., \\hat{p}) as model-based methods in MDPs with function approximation? Could you explain whether your approach falls into the model-based category? If not, which step makes the difference? Is the multi-batched update the main reason that makes the proposed algorithm more computationally efficient compared to the direct extension of the existing OPPO method to linear MDPs from the algorithmic perspective?", "limitations": "This is a theory paper with no potential negative social impact under the discussed context.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "Existing theoretical studies of PPO mainly focus on linear mixture MDPs with full-information feedback, which are implemented in a model-based manner and require an integration of the individual base model. In comparison, this work studies another set of linear MDPs that have low-rank representations and proposes a new optimistic variant of PPO that is provably efficient in both stochastic linear MDPs and adversarial linear MDPs. \n\nIn particular, this work exhibits several promising results:\n1. From the algorithmic perspective, the proposed algorithm involves the novel design of a multi-batched updating mechanism and a policy evaluation step via average rewards.\n\n2. Regarding the performance guarantee, the authors establish the optimal regret bound of O(d^3/4 H^2 K^3/4) with two fundamental findings. Instead of using the existing covering argument in linear MDPs, this work presents a new covering number argument for the value and policy classes. In addition, to ensure the sublinear regret, careful analysis has been done to analyze the drift between adjacent policies to control the error arising from the policy evaluation step.\n\n3. Apart from the regret guarantee, it also provides a PAC guarantee as sample complexity, which allows fair comparison with existing works in this line.\n\nThis work is well-organized and clearly articulates each part with the corresponding motivation, challenges, as well as technical novelties in its solutions. Overall, this paper is technically sound and demonstrates considerable technical novelties. It provides a better understanding of PPO in a class of MDPs with function approximation, which potentially benefits policy optimization in practice.\n", "weaknesses": "While this paper provides insights into the PPO algorithm in linear MDPs, it does have several drawbacks:\n1. One of the claimed novelties is the multi-batched updating mechanism, which coincides with the similar idea of \"policy switch\" in literature. However, there is no discussion of the existing works that involve \"policy switch\", and thus it is not clear whether the computational efficiency is solely brought by the policy switch scheme. \n\n2. Right now, the regret bound requires the batch size to be O(\\sqrt{d^3 K}), with leads to the number of batches being O(\\sqrt{K}). But whether this choice of batch size and the number of batches is optimal remains to be unknown. It would be worthwhile to study and discuss the balance between the batch size and the number of batches, the optimal choice, how the balance will affect the regret.\n\n3. Right now, this is solely theory-based work. As PPO is applied widely in practice, it will be beneficial to include simple benchmark empirical studies to demonstrate its effectiveness.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your review and positive feedback. We will try to address your concerns in the following.\n\n**Q1:** One of the claimed novelties is the multi-batched updating mechanism, which coincides with the similar idea of \"policy switch\" in literature. However, there is no discussion of the existing works that involve \"policy switch\", and thus it is not clear whether the computational efficiency is solely brought by the policy switch scheme.\n\n**A1:** We have briefly discussed previous works that involve multi-batched updating (low policy switch) in Lines 201-203. The algorithms in these works are value-based and cannot tackle adversarial rewards. Furthermore, the corresponding covering number argument is completely new and crucial for the analysis of policy-based algorithms.\n\nOur algorithm is computationally efficient since we can show the running time is polynomial in all parameters (e.g., $d, H, K$), akin to the computational efficiency showcased in LSVI-UCB [1]. Moreover, compared with existing algorithms that update policies in each episode such as LSVI_UCB, our method enjoys better computational efficiency due to the multi-batched update. \n\n[1] Jin, C., Yang, Z., Wang, Z. and Jordan, M. I. (2020). Provably efficient reinforcement learning with linear function approximation. In Conference on Learning Theory. PMLR.\n\n\n**Q2:** Right now, the regret bound requires the batch size to be O(\\sqrt{d^3 K}), with leads to the number of batches being O(\\sqrt{K}). But whether this choice of batch size and the number of batches is optimal remains to be unknown. It would be worthwhile to study and discuss the balance between the batch size and the number of batches, the optimal choice, how the balance will affect the regret.\n\n**A2:** Based on our current analysis, the choice of batch size is optimal. If we choose the batch size as $B$ (and ignore the dependence of $d$ and $H$), then\n- By the new self-normalized analysis in Appendix C, we have $\\beta = \\tilde{\\mathcal{O}}(\\sqrt{K/B})$, which further implies that the model estimation error is bounded by $\\beta \\cdot \\sum_{k=1}^K\\sum_{h=1}^H\\sqrt{\\phi(x_h^k, a_h^k)(\\Lambda_h^k)^{-1}\\phi(x_h^k, a_h^k)} \\le \\tilde{\\mathcal{O}}(K/\\sqrt{B})$ (cf. Lemma 4.5).\n- By Lemma 4.2, we have the policy optimization error is bounded by $\\tilde{\\mathcal{O}}(\\sqrt{KB})$.\n\nBalancing these two terms, we know the optimal choice of $B$ is $\\Theta(\\sqrt{K})$. We appreciate your valuable suggestion and intend to clarify this in the revision.\n\n**Q3:** Right now, this is solely theory-based work. As PPO is applied widely in practice, it will be beneficial to include simple benchmark empirical studies to demonstrate its effectiveness.\n\n**A3:** Thanks for your suggestions. We will consider adding some empirical results in the future version.\n\n**Q4:** In the introduction, the authors mentioned both Cai et al. and He et al. that study linear mixture MDPs are implemented in a model-based manner, whereas existing theoretical studies in linear MDPs are typically value-based methods. However, from the algorithmic perspective, algorithms in Cai et al. and He et al. also perform regularized least-square approximation on value functions in the policy evaluation step. Do you treat all algorithmics that tries to explicitly learn /approximate the transition model (i.e., \\hat{p}) as model-based methods in MDPs with function approximation? Could you explain whether your approach falls into the model-based category? If not, which step makes the difference? Is the multi-batched update the main reason that makes the proposed algorithm more computationally efficient compared to the direct extension of the existing OPPO method to linear MDPs from the algorithmic perspective?\n\n**A4:** For linear mixture MDPs, the transition kernel takes the form $\\mathcal{P}_h(s' \\mid s, a) = \\psi(s, a, s')^\\top \\beta_h$ with some $\\beta_h \\in \\mathbb{R}^d$. This means that the model of linear mixture MDPs is characterized by $d$ parameters. The algorithms in Cai et al. and He et al. perform regularized least-square regression to directly estimate the *model parameter* $\\beta_h$. In contrast, for linear MDPs where $Q_h^\\pi(s, a) = \\phi(s, a)^\\top \\theta_h$, and we use the regularized least-square regression to estimate the value function. Therefore, our algorithm does NOT fall into the model-based category. In fact, the number of model parameters of linear MDPs scale with the number of states (the number of model parameters is $d \\cdot |\\mathcal{S}|$ since $\\mu_h(s) \\in \\mathbb{R}^d$ for all $s\\in\\mathcal{S}$), and thus difficult to perform the model-based learning efficiently. This difference is one of the major differences between linear mixture MDPs and linear MDPs.  See also [1] and [2] for more discussions.\n\nWe want to emphasize that the existing OPPO method (Cai et al.) is restricted to linear mixture MDPs, and its extension to linear MDPs is highly nontrivial (see Challenge 1 in Section 1.1).  The incorporation of multi-batched updating, along with its corresponding analysis, plays a pivotal role in achieving sample efficiency. Furthermore, if we direct extend the existing OPPO method to linear MDPs from the algorithmic perspective (without any modifications)\n- In terms of statistical efficiency, it is hard to provide a theoretical guarantee due to Challenge 1 in Section 1.1.\n- In terms of computational efficiency, you are right --- the utilization of multi-batched update is the main reason that makes the proposed algorithm more computationally efficient. \n\n\n[1] Jin, C., Yang, Z., Wang, Z. and Jordan, M. I. (2020). Provably efficient reinforcement learning with linear function approximation. In Conference on Learning Theory. PMLR.\n\n[2] Ayoub, A., Jia, Z., Szepesvari, C., Wang, M. and Yang, L. (2020). Model-based reinforcement learning with value-targeted regression. In International Conference on Machine Learning. PMLR.\n"}, {"review_id": "oRfl0ghqsV", "reviewer": "Reviewer_r8ZK", "summary": "The paper proposes a theoretical analysis of the PPO algorithm. Some novel techniques such as batch-wise update are proposed so the algorithm can work on the adversarial setting of linear MDPs. A regret bound is given, which is better then or comparable to  previous results. ", "questions": "1. The updating rule of PPO has a very similar formula to Natural Policy Gradient (NPG). There also have been literatures that apply NPG to linear MDPs, can the authors make a comparison between their approach and these literatures? \n\nFor example, in section 4.2 of [1], the authors applied NPG to linear MDPs, and obtained a convergence rate of order $d^2H^6/\\varepsilon^3$, which should imply a regret bound of order $d^{1/2}H^{3/2}K^{3/4}$. \n\n[1] Liu et al., Optimistic Natural Policy Gradient: a Simple Policy Optimization Algorithm for Online Learning in Linear MDPs, https://arxiv.org/pdf/2305.11032.pdf \n\n2. Is it possible to extend the analysis to the general function approximation setting? \n\n3. One novelty of the paper is its ability to handle adversarial rewards. Can the authors explain which part of their algorithm is crucial to achieving this goal? Still take [1] as an example, I think the algorithms have similar formulation, and the difference of [1] is it doesn't use a multi-batched update. Does that mean the multi-batched updating rule is the crucial part for the adversarial setting? ", "limitations": "Since the paper is focused on a theoretical side, it's unlikely to have potential negative social impact. And some limitations and future research directions are mentioned in the Conclusion section. ", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper is well written, with a clear presentation and is easy to follow. The topic studied in the paper is important. The proposed technique is novel and the theoretical result is solid. ", "weaknesses": "1. See Question 1. One concern is the similarity between the proposed method and NPG. And additional comparison is needed so the readers could understand the novelty and contribution of the paper more easily. \n\n2. The algorithm design of OPPO+ is similar to OPPO. The difference is OPPO+ replaces the step-wise update with a multi-batched update, and considers the linear MDP setting so the state-action feature $\\phi$ can be directly obtained instead of doing integration. The authors claimed the weakness of OPPO, or linear mixture MDP, is that the integration is computationally expensive. But I would rather just regard it as a separate model setting, instead of a weakness. Therefore, when doing comparisons with previous work, besides the literature on linear MDP, it could be great if the authors can also give a more detailed explanation on the setting of linear mixture MDP. In particular, given that the algorithm formulations are so similar, it might be helpful if the author can explain why it's not straightforward to migrate the proof of OPPO to the linear MDP setting.  For example, it can be added to the challenge & novelty section, which will greatly strengthen their argument. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your review and positive feedback. We will try to address your concerns in the following.\n\n**Q1:** Comparison with OPPO for linear mixture MDPs.\n\n**A1:** We agree that linear mixture MDPs and linear MDPs are two different types of MDPs with linear function approximation. We have discussed some related works on linear mixture MDPs in Appendix A. Here we provide a more detailed comparison between linear MDPs and linear mixture MDPs from the perspective of parameter size. For linear mixture MDPs, the transition kernel takes the form $\\mathcal{P}_h(s' \\mid s, a) = \\psi(s, a, s')^\\top \\beta_h$ with some $\\beta_h \\in \\mathbb{R}^d$. This means that the model of linear mixture MDPs is characterized by $d$ parameters. In contrast, the number of model parameters of linear MDPs scale with the number of states (the number of model parameters is $d \\cdot |\\mathcal{S}|$ since $\\mu_h(s) \\in \\mathbb{R}^d$ for all $s\\in\\mathcal{S}$). Therefore, from our perspective, learning linear MDPs is harder than learning linear mixture MDPs. \n\nRegarding the challenges involved in extending OPPO to linear MDPs, we provided a brief explanation in Challenge 1 of Section 1.1. Now, let's delve into a more detailed explanation of these technical challenges.\n\n\nTechnically, for linear mixture MDPs (Equation (B.20) in OPPO paper (Cai et al., 2020)), they need to analyze  \n$$\\bigg\\|  \\sum\\_{\\tau = 1}^{k - 1} \\phi\\_h^\\tau(x\\_h^\\tau, a\\_h^\\tau) \\cdot \\big( V\\_{h+1}^{\\color{red}{\\tau}}(x\\_{h+1}^\\tau) - (\\mathbb{P}\\_h V\\_{h+1}^{\\color{red}{\\tau}})(x\\_h^\\tau, a\\_h^\\tau) \\big) \\bigg\\|\\_{(\\Lambda\\_h^{k})^{-1}}.$$ \nSince $V_{h+1}^\\tau$ is adapted to $\\mathcal{F}\\_{k,h,1} = \\{(x\\_{i}^{\\tau}, a\\_{i}^{\\tau})\\}\\_{(\\tau, i) \\in[k-1] \\times[H]} \\cup\\{r^{\\tau}\\}\\_{\\tau \\in [k]} \\cup\\{(x\\_{i}^{k}, a\\_{i}^{k})\\}\\_{i \\in[h]}$, they can bound this term with classical self-normalized process analysis directly (see Lemma D.1 in (Cai et al., 2020)).\n\nIn contrast, for linear MDPs (see e.g., (B.26) in our paper or Lemma B.3 in [1]), we need to bound the term\n$$\\bigg\\|  \\sum\\_{\\tau = 1}^{k - 1} \\phi(x\\_h^\\tau, a\\_h^\\tau) \\cdot \\big( V\\_{h+1}^{\\color{red}{k}}(x\\_{h+1}^\\tau) - (\\mathbb{P}\\_h V\\_{h+1}^{\\color{red}{k}})(x\\_h^\\tau, a\\_h^\\tau) \\big) \\bigg\\|\\_{(\\Lambda\\_h^{k})^{-1}}.$$\nSince $V\\_{h+1}^\\tau$ is NOT adapted to $\\mathcal{F}\\_{k,h,1} = \\{(x_{i}^{\\tau}, a_{i}^{\\tau})\\}\\_{(\\tau, i) \\in[k-1] \\times[H]} \\cup \\{r^{\\tau}\\}\\_{\\tau \\in[k]} \\cup\\{(x_{i}^{k}, a_{i}^{k})\\}\\_{i \\in[h]}$, we need to perform the uniform concentration on the function class of $V\\_{h+1}^k$. The challenge of calculating the covering number of this function class has been elaborated in Challenge 1 of Section 1.1 (Lines 58-73).\n\n\nThanks for your question, and we will add these discussions in the revision.\n\n[1] Provably Efficient Reinforcement Learning with Linear Function Approximation. Chi Jin, Zhuoran Yang, Zhaoran Wang, Michael I. Jordan\n\n\n**Q2:** Comparison with NPG algorithm [2].\n\n\n[2] Liu et al., Optimistic Natural Policy Gradient: a Simple Policy Optimization Algorithm for Online Learning in Linear MDPs, https://arxiv.org/pdf/2305.11032.pdf\n\n\n**A2** Thank you for pointing out this work. Firstly, it is important to note that this work has been released subsequent to the NeurIPS submission deadline. While we have discussed prior policy-based algorithms within our related works, we remain open to discussing the distinctions from [2].\n\n- Regarding the updating rule, both PPO and NPG share a similar policy updating rule. However, we additionally introduce the multi-batched updating and average reward policy evaluation mechanisms, which are crucial to handle adversarial rewards.\n- Regarding the results. Yes, their result implies an $\\tilde{\\mathcal{O}}(d^{1/2}H^{3/2}K^{3/4})$ regret for *stochastic* linear MDPs. However, their algorithm cannot tackle adversarial linear MDPs, which is the central focus of our paper.\n\n\n**Q3:** Is it possible to extend the analysis to the general function approximation setting?\n\n\n**A3** Yes, our analysis is ready to be extended to the kernel and neural setting [3]. Also, we believe we can deal with low eluder dimension setting like [2] and [4]. Thanks for your question and we will add more discussions in the revision.\n\n[3] Yang, Z., Jin, C., Wang, Z., Wang, M. and Jordan, M. I. (2020). On function approximation in reinforcement learning: Optimism in the face of large state spaces. arXiv preprint\narXiv:2011.04622.\n\n[4] Reinforcement Learning with General Value Function Approximation: Provably Efficient Approach via Bounded Eluder Dimension\nRuosong Wang, Ruslan Salakhutdinov, Lin F. Yang\n\n**Q4:** One novelty of the paper is its ability to handle adversarial rewards. Can the authors explain which part of their algorithm is crucial to achieving this goal? Still take [2] as an example, I think the algorithms have similar formulation, and the difference of [2] is it doesn't use a multi-batched update. Does that mean the multi-batched updating rule is the crucial part for the adversarial setting?\n\n**A4:** Compared with [2], we think the average reward policy evaluation and the corresponding analysis are the key to handling adversarial rewards (cf. Challenge 2 and Novelty 2 in Lines 87-102), though the multi-batched updating rule is also important to obtain a sublinear regret. If we use the instantaneous reward to perform policy evaluation like OPPO (Cai et al., 2020) or optimistic NPG in [2], we will suffer the linear regret (cf. Challenge 2 in Lines 87-94). To this end, we use the average reward to evaluate the policies (cf. Lines 95-97). This mechanism will introduce additional errors, which require a new smoothness analysis (cf. Lines 98-102 and Lemma 4.3).\n"}, {"review_id": "wv7vZQW48U", "reviewer": "Reviewer_Eaqc", "summary": "In this paper, the authors extend the theory of proximal policy optimization-based methods in the linear mixture MDPs and propose an optimistic variant PPO algorithm (OPPO+) for stochastic linear MDPs and adversarial linear MDPs with full information. \nThe proposed algorithm adopts a multi-batched updating rule from bandit literature, where the policy is updated at regular intervals of batches, instead of updating it every episode. During the policy improvement step, the policy is updated using proximal policy optimization, while the policy evaluation step involves estimating the value using least square value iteration with the average reward from the previous batch. \nThe proposed algorithm provides a regret guarantee for $\\tilde{O}(d^{3/4} H^2 K^{3/4})$ and has a sample complexity of $\\tilde{O}(d^3H^8/\\epsilon^4 + d^5H^4/\\epsilon^2)$. This regret bound is tighter than the existing PPO-based algorithms proposed for stochastic linear MDPs.", "questions": "1. What does it mean for the proposed algorithm to be \"optimistic\"? What I mean is that for example, in value-based algorithms, optimism refers to the estimated values of the algorithm being more optimistic than the true optimal value (Lemma B.5 in [17]).\n2. Can you explain the computational cost of policy improvement in OPPO+ compared to the policy improvement in value-based algorithms [17]?\n3. Besides the ability to learn stochastic policies, what other advantages does OPPO+ have compared to value-based algorithms?\n4. In line 203, the author argued that value-based algorithms cannot handle adversarial rewards. Could you provide more details about this?\n5. By performing policy optimization infrequently, the algorithm achieves a regret of order $O(K^{3/4})$. What are the drawbacks or trade-offs associated with this approach? In other words, in line 81, it was mentioned that if policy optimization is performed every episode, the regret would have a linear dependence on $K$. What benefits can be obtained from this approach?", "limitations": "As this is a theoretical paper, it does not seem to have any negative societal impact. However, the authors have not mentioned the limitations of this algorithm. (If they have mentioned any, please let me know, and I will check.) Nonetheless, they have provided an introduction to future work in Remark 3.3.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "- The proposed algorithm can be applied not only to stochastic linear MDPs but also to adversarial linear MDPs with full-information feedback.\nIn order to cover the case of adversarial linear MDPs, the average reward technique is used, and for the analysis, result for bound on the gap between the value of the policy from the previous batch and the value of the policy from the current batch is suggested.\n- When applying the existing covering number theory from linear MDPs, the regret may depend on the size of the action space. To address this, a method using novel covering theory is proposed to reduce it to a logarithmic scale.\n- Compared to existing policy optimization algorithms, it provides a tighter regret guarantee in both the stochastic linear MDP and adversarial linear MDP with full-information feedback settings.", "weaknesses": "- The computational cost of policy improvement is not discussed in detail.\n- It remains unclear what advantages the proposed policy optimization algorithms offer compared to value-based algorithms, apart from their theoretical purposes.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your review and positive feedback. We will try to address your concerns in the following.\n\n**Q1:** What does it mean for the proposed algorithm to be \"optimistic\"? What I mean is that for example, in value-based algorithms, optimism refers to the estimated values of the algorithm being more optimistic than the true optimal value (Lemma B.5 in [17]).\n\n**A1:** Thanks for your good question, this is indeed one of the most important differences between policy-based algorithms and value-based algorithms. \n- For the value-based algorithm LSVI-UCB in [17], they can obtain that $V_1^* \\le V_1^k$. Furthermore, \n$$\\mathrm{Regret}(K) = \\sum_{k=1}^K V_1^* - V_1^{\\pi^k} \\le \\sum_{k=1}^K V_1^k - V_{1}^{\\pi^k} \\lesssim \\text{sum of bonus function} \\le \\tilde{\\mathcal{O}}(\\sqrt{K}).$$ \n- For policy-based algorithms, we cannot obtain the guarantee that $V_1^* \\le V_1^k$ as Lemma B.5 in [17]. Instead, we can obtain that $V_1^{\\pi^k} \\le V_1^k$ for stochastic linear MDPs. In other words, $V_1^k$ is the optimistic estimation of the value of policy $\\pi^k$. Hence, we cannot follow the analysis way like [17]. Instead, we use the regret decomposition lemma (Lemma 4.1) to decompose the regret into two terms --- policy optimization error and estimation error, and then tackle these two terms separately.\n\nIn terms of algorithm design, our algorithm shares the same spirit with LSVI-UCB [17]. In both [17] and our work, the bonus function $\\Gamma_h^k$ serves to quantify estimation error (cf. Lemma 4.4 in our paper and Lemma B.4 in [17]). Furthermore, both OPPO+ and LSVI-UCB calculate the \"optimistic\" estimation by adding bonus functions to the estimated value function (cf. Line 15 of OPPO+ and Line 6 in LSVI-UCB). As a result, OPPO+ and LSVI-UCB can be regarded as the optimistic variant of PPO and LSVI, respectively.\n\n\n\n\n**Q2:** Can you explain the computational cost of policy improvement in OPPO+ compared to the policy improvement in value-based algorithms [17]?\n\n**A2:** OPPO+ updates the policy by solving a proximal policy optimization problem, while LSVI-UCB in [17] simply executes the greedy policy with respect to the estimated value function. Hence, it is hard to say that the computational cost of a single policy optimization in OPPO is lower than one step policy improvement in  LSVI-UCB. However, it is worth noting that OPPO+ adopts the multi-batched updating rule, which leads to better computational efficiency compared with LSVI-UCB that updates policy in each episode. \n\n\n**Q3:** Besides the ability to learn stochastic policies, what other advantages does OPPO+ have compared to value-based algorithms?\n\n**A3:**  OPPO+ can tackle adversarial rewards, while value-based algorithms (e.g., LSVI-UCB) cannot. Further elaboration on this point is provided in detail in **A4**. Moreover, PPO is one of the most widely recognized RL algorithms and linear MDP is arguably the most fundamental RL models with function approximation. Consequently, understanding the theoretical performance of PPO in linear MDPs is important.\n\n**Q4:** In line 203, the author argued that value-based algorithms cannot handle adversarial rewards. Could you provide more details about this?\n\n**A4:** In value-based algorithms, the learner estimates the Q-function and then chooses the greedy policy with respect to the estimated Q-function (see e.g., LSVI-UCB). Meanwhile, it is known to us that the deterministic policy policies will incur linear regret even for adversarial linear bandits (simplified problem of adversarial linear MDPs). Please see Chapter 11 (Exercise 11.2) in [1] for more details.\n\n[1] Lattimore, T. and Szepesvari, C. (2020). Bandit algorithms. Cambridge University Press.\n\n**Q5:** By performing policy optimization infrequently, the algorithm achieves a regret of order $O(K^{3/4})$. What are the drawbacks or trade-offs associated with this approach? In other words, in line 81, it was mentioned that if policy optimization is performed every episode, the regret would have a linear dependence on $K$. What benefits can be obtained from this approach?\n\n**A5:** If OPPO+ performs the policy optimization for $L$ times, then by Lemma C.3, we have the complexity (log covering number) of policy class is roughly $\\tilde{\\mathcal{O}}(L)$ (ignoring the dependency of $d$ and $H$). Furthermore, by the new self-normalized analysis in Appendix C, we have $\\beta = \\tilde{\\mathcal{O}}(\\sqrt{L})$, which further implies that the model estimation error is bounded by $\\beta \\cdot \\sum_{k=1}^K\\sum_{h=1}^H\\sqrt{\\phi(x_h^k, a_h^k)(\\Lambda_h^k)^{-1}\\phi(x_h^k, a_h^k)} \\le \\tilde{\\mathcal{O}}(\\sqrt{L K})$ (cf. Lemma 4.5). Meanwhile, by Lemma 4.2, we have the policy optimization error is bounded by $\\tilde{\\mathcal{O}}(K/\\sqrt{L}) = \\tilde{\\mathcal{O}}(K^{3/4})$. By choosing $L = \\Theta(\\sqrt{K})$, we obtain a regret of order $\\tilde{\\mathcal{O}}(K^{3/4})$. \n\nIn summary, the multi-batched updating mechanism is crucial to obtain a sublinear regret and the choice of the number of batches is optimal based on our current analysis.\n \n"}]

Author rebuttal:

Meta-review: This work provides a convergence guarantee for a model-free policy optimization algorithm. The main focus of this work is the linear MDP with full-information and adversarial reward setting(i.e., the reward function is known to the algorithm at the end of each episode). The authors established a novel upper bound guarantee of the order of poly(d,H)K^{3/4}, previously unknown for this setting. this work may enable further progress in this setting (either improving the K^{3/4} convergence or removing the full-information assumption). The reviewers were in consensus for the acceptance of this work and I support this decision.

I further encourage the authors to elaborate on two topics: (1) Strictly speaking, the algorithm the authors analyze resembles more to TRPO, or a mirror-descent like approach to policy optimization. This is different than the standard update role of PPO which relies on clipping and importance sampling ratio. Even though this became standard within the theoretical community, I believe it can be useful to emphasize this discrepancy.
(2) Further highlight the lower bound for this setting and the gap between the lower and upper bound.
Decision: Accept (poster)