Horizon-free Reinforcement Learning in Adversarial Linear Mixture MDPs
Authors: Kaixuan Ji
Qingyue Zhao
Jiafan He
Weitong Zhang
Quanquan Gu
Venue: ICLR 2024 poster (2024)
Keywords: reinforcement learning theory
reinforcement learning with adversarial reward
regret minimization
linear function approximation
Primary area: reinforcement learning

Abstract: Recent studies have shown that the regret of reinforcement learning (RL) can be polylogarithmic in the planning horizon $H$. However, it remains an open question whether such a result holds for adversarial RL. In this paper, we answer this question affirmatively by proposing the first horizon-free policy search algorithm. To tackle the challenges caused by exploration and adversarially chosen reward over episodes, our algorithm employs (1) a variance-uncertainty-aware weighted least square estimator for the transition kernel; and (2) an occupancy measure-based technique for the online search of a stochastic policy. We show that our algorithm achieves an $\tilde{O}\big((d+\log |\mathcal{S}|)\sqrt{K} + d^2\big)$ regret with full-information feedback, where $d$ is the dimension of a known feature mapping linearly parametrizing the unknown transition kernel of the MDP, $K$ is the number of episodes, $|\mathcal{S}|$ is the cardinality of the state space. We also provide hardness results to justify the near optimality of our algorithm and the inevitability of $\log|\mathcal{S}|$ in the regret bound.

Published as a conference paper at ICLR 2024
HORIZON-FREE REINFORCEMENT LEARNING IN ADVERSARIAL LINEAR MIXTURE MDPS
Kaixuan Ji Qingyue Zhao Jiafan He', Weitong Zhang', Quanquan Gu DDpartment of Computer Science, University of California, Los Angeles *Department of Computer Science and Technology, Tsinghua University ka Maixuanji@es ucla. edu, zhaoqy1 90mail 1s. tsingguu....... edu. en (jiafanhe19, weightzeroJ@uccl edu, ggulcs. ucla.edu
ABSTRACT
Recent studies have shown that the regret of reinforcement learning (RL) can be polylogarithiic the planning horizon H. However, remains an open question whether such a result holds for adversarial RL. In this paper, we answer this ques- tion affirmatively by proposing the first horizon-free policy search algorithm. To tackle the challenges caused by exploration and adversarially chosen reward over episodes, our algorithm employs (1) a aifaane--uncetaintyy aware weighted least square estimator for the transition kemnl; and (2) an occupancy measure- measure-based technique for the online search of stochastic policy. We show that our algorithm achieves an ((dd + log (S)) K + d²) regret with full-information feedback where d is the dimension of a known feature mapping linearly parametrizing the unknown transition kernel of the MDP, K is the number of episodes, [S] is the cardinality of the state space. We also provide hardness results to justify the near optimality of our algorithm and the inevitability of log [S] in the regret bound.
INTRODUCTION
Learning in episodic Markov Decision Processes (MDPs) (Altman 1999 Dann & Brunskill 2015
Neu & Pike- Burc-BBueeeeee 2020) is key problem in reinforcement learning (RL) (Zzeeeváá 2010 Sutton & Barto 2018). where agent sequentially interacts with environment with a fixed horizon length H. Each action 0e the agent takes at state 8, incurs some reward r(st, r()),))), and takes into the next state $t+1. The agent will restart in the same environment after every H time steps. Although the curse of horizon has been deemed as a challenge in episodic RL (Jiang & Agarwal, 2018). recent line of works have developed near-optimal algorithms achieve regret with no polynomial dependence on H for both tabular MDPs (Zhang et al.] 2021a) and RL with linear function approximation (Zhang et al., 20216] Kim et al. [2022] Zhou & Gu 2022). This suggest that the regret of episodic RL can get rid of linear dependency on H. Nevertheless, these horizon- free algorithms are only applicable
learning MDPs where the reward function is either fixed or stochastic, yet in many real-world scenarios. we have cope with the adversarially changing reward (Even-Dar et al.) [2009] Yu al.] 2009) Zimin & Neul 2013).. However, little known about horizon- free RI. in adversarial MDPs. Thus, the following question remains open.
Can we design near-optimal horizon-free free RL algorithms under adversarial reward and unknown transition with function approximation employed?
In this paper, we affirmatively answer the question for linear mixture MDPs with adversarial reward
under full-information feedback (Cai et al. 2020 He et al. 2022b). We propose a new algorithm termed -orizon-Free
(ocupancy-Measuue Guided Optimistic Policy Search (HF-O²PS). Following Cai et al. (2 He et al. (2022b), we use online mirror descent (OMD) to update the policies and value-targeted regression (VTR) (Jia al. 2020 Ayoub et al.) 2020) learn the transition. Never- theless, we show that the wereefffuniioo--useeeeee
mirror descent ievitablyy introduces the polynomial dependency on the planning horizon H in the regret upper bound. To address this issue, inspired by Rosenberg & Mansour (0119)); Jin et al. (2020a) and Kalagarla et al. (2020), we use occupancy measure as a proxy the policy and conduct OMD on the occupancy measures to update. Like Jin
'Equal Contribution
HHere O(-) hides logarithmic factors of H, K and 1/8.

---

Published as a conference paper at ICLR 2024
et al. (2020a), we maintain confidence set of the transition kernel and utilize constrained OMD to handle the unknown transition. To achieve a horizon-frie regret bound, we also adapt the high-order
moment estimator in Zhou & Gu (2022) to stochastic policies and obtain tighter Bernstein-type
confidence set. The regret of our algorithm can be upper bounded by Ō(dvK + de) the first K episodes with high probability, where d is the dimension of the feature mapping. To the best of our knowledge, our algorithm the first algorithm achieve horizon-free regret in learning adversarial linear mixture MDPs. Our three main contributions are summarized as follows:
We propose new algorithm, HF-O*PS, for linear mixture MDPs with adversarial reward uni- formly bounded by 1/11. Compared to the previous works (e.g.. Cai et al. (2020); He et al. (2022b)) HF-O*P PPS use occupancy aecupacy-mmaauure www.-me-aaaeaeeeeeeeeeee OMD rather than direct policy optimization. HF-O also use the high-order moment estimator to further facilitate the learning of the transition kernel.
Our analysis shows that HF-O'PS achieves a regret bound Ö(d K + +d),, where K is the number of episodes and d is the dimension of the feature mapping. As far as we know, HF-O*PS is the first algorithm for adversarial RL achieving horizon-free regret upper bound.
We also provide hardness results in addition the regret upper bound. First show that an unbounded S will result in lower bound asymptotically linear in v HH, which justifies sumption of |S| co. We also provide a minimax lower bound of (dvKK), which manifests the near optimality of HF-OOPS.
Notation We denote scalars by lowercase letters, and denote vectors and matrices by lower and uppercase boldface letters respectively. We use 'n] to denote the set f1..... n). and [n] Given Rdxd e E O and vector Rdd we denote the vector's L2-norm by ||x||2
and define ||x|== V Ex. We employ standard asymptotic notations including O(),, (()), O(). and further use (-) to hide polylogarithmic factors. Let 1 denote the indicator function, and [0][a,s] denote the truncation function x {a < x S b} + a 1fx < a} + b. 1(x > b} where S b E R, R. Let ((-) represent the probability simplex over a finite set.
2 RELATED WORK
Horizon-tree RL RL is once believed to be far more harder than contextual bandits. However, recent works has begun to overthrow this long-standing stereotype (Wang al. 2020a). To achieve fair comparison with CB, there are two options. One is to assume the total reward is bounded by one in each episode (Jiang Agarwal| 2018). Under such assumption,
possible to obtain entirely
H H-independent regret bounds in the tabular setting (Zhang et al., 2021a 2022). Recent works further proposed horizon-free algorithms for linear mixture MDPs and linear MDPs (Zhang et al. 2021b]
Kim et al. 2022 Chen et al., 2022; Zhou & Gu 2022). Though near-optimal algorithms have been
proposed learn Dirae policy with O(dvK + d²) regret under linear function approximation (Zhou & Gu 2022). and similar regret guarantees with no poly(H) dependency has been established various settings (Zhang et al., 2020; Tarbouriech et al., Zhou al., 2022). any of the above work can not even learn a nontrivial categorical policy. Another assumption is to assume that the reward uniformly bounded by 1/H (Assumption 2. Zhang et al. [2021a). We employ the later assumption to approach MDPs with large state space and adversarial reward and learn stochastic policies horizon-free manner.
RL with adversarial reward A long line of works (Even-Dar et al. 2009 Yu et al. 2009 Neu al. 2010 2012; Zimin& & Neu 2013 Dick al. 2014;
Rosenberg & Mansour 2019a Cai al. Jin et al. 2020a) Shani et al. 2220 Luo et al. 2021 He et al. (022b) has studied RL with ad- versarial reward, where the reward is selected by the environment at the beginning of each episode.
2020
To cope with adversarial reward, there are generally two iterative schemes. The first scheme is the policy-optimization-aasss
method (Neu et al., 2010, Cai et al. 2020 Luo al., 2021 He et al.) 20226), where the policy is updated according to the estimated state-value function directly. Fol- lowing this spirit, under bandit feedback, Neu al. (010 achieves regret upper bound of Ö(T2/3) with known transition, and Shani et al. 22020) achieves D(v52AH44 A 22/3) regret under unknown transition. Under full-information feedback, Cai et al.) (2020) establish the first sublinear regret guarantee and POWERS in He al. (2022b) achieves netr-optimal Ö(dH / /K) regret for adver- sarial linear mixture MDPs The second scheme is occupancy vccupancy-measure. www.ure-eeeeeeeeeeae- based method (Zimin &
Neu 2013 Rosenberg & Mansour
2019a b Jin et al. 2020a Luo et al. 2021 Neu & Olkhovskaya,
2

---

Published as a conference paper at ICLR 2024
Dai et al. 2022). The policy is updated under the guidance of optimization of occupancy mea- Guided by this scheme, under known transition, Zimin & Neu (203)) achieves O D(VHSAR regret for bandit feedback and near-optimal Ó(HyK) K)) regret for full-information feedback. For unknown transition and bandit feedback, an Ö(HSV AK) regret is achieved by Jin et al. (2020a). Under linear function approximation with bandit feedback, O(H O(HvdK) viK) regret is achieved achieved for linear MDPs (Neu & Olkhovskaya, 2021) and Ö(dS²
2021
VHSAK) regret is achieved for
linear mixture MDPs (Zhao et al. 2023). In this work, we use deal with adversarial reward and focus on the setting of linear mixture MDP with full-information feedback.
method to
PRELIMINARIES
We study RL for episodic linear mixture MDPs with adversarial reward. We introduce the definitions and necessary assumptions as follows.
3.1 MDPs WITH ADVERSARIAL REWARD
We denote a homogeneous, episodic MDP by a tuple M = (S, (rh) jkke k), k), where is the state space and A is the action space, H is the length of the episode, pt S x x [0, 1/H] is the reward function at the le-th episode, and (P(-:-)) :) is the transition kernel from state-action pair to the next state. r is adversarially chosen by the environment at the beginning of the k-th episode and revealed the agent at the end of that episode. A policy π { is collection of functions Th S + ((A).
3.2
VALUE FUNCTION AND REGRET
For (s,a) S x A, we define the action-value function Q and (state) value function Vg, as follows:
(5, ()) =
1 (s, + = (SH, an) 8h = 8, 0h = =
(s) = Eawno (-1s) [QT, n (s, a)], i =s)
Here in the definition of QR, we use F[| to denote the expectation over the state-action sequences (sh, ah, Sh+1, ah,11.., 8H, aH), where Sh = s, an = a and s1+11 ~ F(-|sw, axe), a/++1 ~ Th (1((swww-1))) for all h' h I..H 1. For simplicity, for any function : S + R, we denote
[FV a) (. V(5).. [VV](s, [PV a) (IPV)
where 2 is shorthand for the function whose value at state s is (V())) 2 Using this notation, for policy have the following Bellman equality (s. In the online setting, the agent determines policy x² and start from a fixed state at the beginning of episode k. Then at each stage h E [H], the agent takes an action an ~ (-1s%) and observes the next state &
+ PVV I.V a).
P(-|s a.). For the adversarial reward, the goal of RL. to minimize the expected
regret, which is the expected loss of the algorithm relative to the best-fixed policy in hindsight (Cesa-)
Bianchi & Lugosi 2006). We denote the optimal policy n= sup= ΣK 2k=1 (s1())). Thus the expected regret can be written
Regret(K) [K) ΣK_ (s1 Vg
where we use Vi, (-) denote VT (-), which is the expected total reward in episode under the optimal policy.
focus on achieving a horizon-free bound Regret ()) Two assumptions crucial to this end. The first assumption gives a reward shaping reciprocal of the planning horizon length Hl so as to offset the dependence on Hl contributed by reward scaling (Jiang & Agarwal 2018).
In this paper,
Assumption 3.1 (Dann Brunskill 2015)). (*K, on) < 1/H, Vh E [H] for any trajectory {sh, ah Jk induced by an ~ Th and 8h+1 ~ PP(-ss,, an) for any policy in every episode.
DDe limited space, defer previous works RL with function approximation Appendix
3

---

Published as a conference paper at ICLR 2024
The intuition behind Assumption 3.1 is the absence of spiky reward in all episodes. The next next assump-
tion assumes the transition kernel P enjoys a linear representation w.r.t a triplet feature mapping.
We define the linear mixture MDPs UJi et al. 2020; Ayoub al. 2020 Zhou et al.
2021 Zhou &
Gu 2022 as follows 2
Assumption 3.2 (Linear mixture MDP). MDP M = (S, A, H, (1* ]еj]]] IP) is called an episode
B-bounded linear mixture MDP, if there exists a known feature mapping @(s' a) 8 A x Rd and an unknown vector 0 E IR such that P(s'|s,, a) = (ø(s'|s, a), 0*) for any state-action- next-state triplet (s, a, s'). We assume |10*12 ||2 I B and for any bounded function : [0, 1] and any (s, a) E S x A, we have (s, a)lla S 1, where Φv a) = -Eres O( (sssss.)V(ss')
Linear mixture MDPs have the following key properties. For any function V S - R and any state-action pair (s, a) ES x A, the conditional expectation V over P(-|s, a) is a linear function (dv (s, a), 0²). Meanwhile, the conditional variance of V over P(s, a) is
of 0", i.e., [PV] quadratic in 0", i.e., (8, = (8) [ (s, a),
3.3 OCCUPANCY MEASURE
We introduce occupancy measure Altman 1999 Jin et al. 2020a) proxy of the stochastic policy, which will be used in our algorithm design. The occupancy measure 2" {2% x A S + [0, - associated with stochastic policy æ and transition function IP is defined as:
(s, a, Pp; = (s,, = an a, 84+1 s' IP.
A reasonable occupancy measure x" must satisfy the following constraints:
Σ
as, 1.
I/ Normalization
(3.1)
SES,NEA,N'SS
Σ as,
Σ S
[ H]. // Same marginal occupancy
rEANES
DES,bEA
(3.2)
21 (a (== 81) P()'s a), v(s, ESXA.
// Initial distribution (3.3)
Lemma 3.3 (Rosenberg & Mansour (019a)). If a set of functions xx {2p : :S A x +
[0, 1]]1 satisfies (3.1) and (3.2). then is a valid occupancy measure. This occupancy measure associated with the following induced transition function P. and induced policy
a8,
Eves E (s,
Pn(s'1s,a)= Ee'es (s,
Th (a(s)) = EwEsses 2% a')
(3.4)
for all as, 8' h) 8 A [H].
We use denote the occupancy measure induced by the optimal fixed-policy in hindsight, " and the true transition function, P.
THE PROPOSED ALGORITHM
In this section, demonstrate OF-OPPS for learning episodic linear mixture MDPs with adversarial reward. At high level, in each episode, HF-O"PS can be divided into two steps. HF-O'PS firstly updates the policy based on observed data, then uses VTR (Jia et al. 2020; Ayoub al. 2020) to learn the transition model. To achieve horizon-free regret, we use meeupancymmasurreeee mirror descent rather than proximal policy optimization to update the policy, and adopt variance- uncertainty-awee aware linear regression and high-order moment estimator See Section for details.
4.1
OMD ON OCCUPANCY MEASURE
At the beginning of each episode, following Jin et al. (2000a) and Kalagarla et al. (020). HF-O2PS uses occupancy measures to update the policy based on the observed data. First we calculate the occupancy measure of this episode {z === based on the occupancy measure {2/- f= Jı=1 and the reward {rA 1 ! of the last episode. To utilize Iearned information, we hope that the transition induced by the new occupancy measure is close to estimation. Given the confidence set of 0*
We inevitably only consider finite and A due technical reasons (see Section 5 for details).
4

---

Published as a conference paper at ICLR 2024
Algorithm HF-O'PS
Require: Regularization parameter X, an upper bound B of the fo-norm of 0" confidence radius
{3x 1811.21 level M, variance parameters {, [M] (o..... M 1}, learning rate
1: Set initial occupancy measure
as uniform distribution and assume r (.,-) 0.
2: For m E [M], set 1.. + 0, 20,++1.m + AI, b0.u+1,, + Set V1,H++1(-) < 0, C1 + {0:
|@| - 81}
3:
for k == L...., K do
4: Set C2 + {0:
Σ
1/2 ( 0k0))12 s Be], DE as 44.1
0.
5:
T² - Algorithm
Du. a)
6:
for h 1..... do
7:
Take action of TH (+1=%) and receive next state 1/41 PPll1182,4 at
8: Observe the adversarial reward function (.,.)
9:
end for for h
H, ...., 1 do 11: Set Qu,((s)), : (-. as in and 4.5
end for
13:
For m E [M], set Em, 1,
for h 1 1...., do
For m [M], denote @khhm = @ven (sh, at).
16:
Set fōk.A.m ME[M] +- Algorithhm 3/ Ok knhh Ea.m Demmmeeto ME Ber {,
17:
For [M]. set 1, +- Exmam + &R 11 k.h.m / k.
V. 18: For m E [M] set b.. + ba.u + k k.t+1 (5 (5h+2)/022. k.h.m
19: end for
For m E MM. set Ex+1. Ep.H+im D b 1+m Ost1. Skt1m Ba+1m
21: end for
Algorithm Mirror Descent on Occupancy Measure
Require: the occupancy measure of last iteration --- constraint set Dx, learning rate a
1: for (h, 8, 5') E [M] S x A x S do
2: Set w (s, s') k a (s, (s,a))
3: Set 2t +- arrgmin
4: Set (als) +- E. (x.0.)) 20. (e.0,))
5:
end for
at the beginning of k-th episode, Cg (Line Algorithm T we construct the feasible domain of occupancy measure Dx such that for all occupancy lies in Dr, the transition it induced lies in the confidence set Cx
Definition 4.1. Given the confidence set Cs of parameter 0*, we define the feasible occupancy measure set Dj C ||SS|AA| as follows:
D3 2n (((:))) E RI h [ (n(s))))
24 (s, v. = Σ
6.9/
Σ
21 (,,,)
Vs 1
2x(8,,,)) 0, VES
Σ
s,(s,,,)
3 0x.,h,, E C.
(,, (t..n,k,.-1ssssa) (111,,)))
(4.1)
E 24 (s)
We detail the intuition behind Definition 4.1 and computational issues of I Line Appendix
P

---

Published as a conference paper at ICLR 2024
Algorithm 3 High-order moment estimator (HOME) (Zhou & Gu. 2022)
Require: Features (mn,b..)mmeen
vector estimators {Ok.m (
me(ar]
covariance
matrix
[Ek,m [1sm)me[[]] mE[M] and { (. M. me(M]] confidence radius PR. 7
1: for m = O,..., M 2 do
2: Set [V V.m.V..h11 k a/) <- [( Px 0 1zz }+ min {I, kk,,, + // --1
[ O 0x 10.11
3: Set EEAh,, + min {1, 23x ptalll.......ls..ma
4: Set k.h. + max kl k 15 0%) + Ek.h 52, 7² ( 1
5: end for
6:
Set A.A.M- & max 1,52, 0 @ S
Ensure: ( M
We define the standard mirror map & for the probability simplex and the corresponding Bregman divergence De as follows:
H
((=)
ΣΣ Σ an(8, alls,,,s)(ls zn (8,0, Do (z. v) = ((x) (0-((y))- ( (r-v Vo())). (4.2)
h=18,0,
And the following lemma shows that our mirror map is //H-slyongly convex.
Lemma 4.2. & is //H-strongly convex on the space of occupancy measure with respect to thus strongly convex on kk.
||
lI
The basic idea of updating z* is minimize the trade-off between the value-loss and the distance from the occupancy measure of last episode. Formally we have:
arg min zED.
1,.t-1,,~11 + D0(2,="-1)
(4.3)
where is the learning rate and the inner product is defined follows:
(2
Σ
2n(s,a,
5,a, 1ESXAXXIII1
Following Rosenberg & Mansour 2019a), split 443) to the two-step optimization at Line 2 and
of Algorithm By Lemma 3.3 we update the policy as follows:
Σ. (s,
Th
Eas (8,0,'))
For sake of simplicity, we also define the optimistic expected total reward given by the occupancy measure (s1) as follows:
(8. = Σ 8(),s,)
h.s.a,a'
After obtaining * HF-OPPS chooses actions at based our new policy मं and observe the whole reward function n at the end of the episode.
4.2
VTR WITH HIGH-ORDER MOMENT ESTIMATION
The second phase of HF-O²PS is to estimate the transition model (0*, Φ)) and evaluate the policy * this step, we construct a variance--uneettaityyaaw -awaee weighted least square estimator Zhou
& Gu 2022) and explicitly estimate higher moments of P (Zhang et al., 2021b Zhou & Gu 2022 which are poly(0* (0*) under Assumption 3.2
Concretely, we first compute the optimistic estimation of QF" (resp. Vi²"), Qui (resp. Vk,N), in backward manner. Specifically, HF-O²PS computes the optimistic Qu and Vk, as:
Qu.((.)) [r* (.--) + (Or.o, &va (c.)) + Bell ( a ( ( الااك,1. o.1)"
(4.4)
V.en()) = Ba (0
(4.5)

---

Published as a conference paper at ICLR 2024
where θk,u is the 0-th estimator of 0", Σk.o is the covariance matrix and 3g is the radius of the confidence set defined as:
+ 1124
+ 30 (0g + log((>/ / VAB,
(4.6)
Then we estimate 0* by weighted regression problem with predictor Φ ove n+ (5 a
against response Vi,b+1 (1)+ Specifically, 0R,0 is the solution to the VTR problem:
k-1 ΣΣ jo,, 0) Va (6
argmin 2/ + 6
where the weight 3,00 is a high-probability upper bound of the conditional variance [VV, ). In detail, for each & [K] and E A, if [VV af) can be computed for a function efficiently, we define
L.A.0 = max max e $
2 2,0.0
(4.7)
where [VVi,n+1](s), a is the variance-aware term and y²| @ ب is the umcertainty-aware term.
However, we choose to replace [VV,,a+1]($$ a with [V ag) + Ex,A,0 in (4.7) since
the true transition P is unknown, and hence the true conditional variance not exactly available.
Here Ex,n.0 (Line 3 in Algorithm 3 is an error bound such that [VV,,A+1](s); ak) + Fx, 2
[VV,, ( af) with high probability and [VVe,A+1]s a%) (Line in Algorithm is designed
K 12.111 - K(o,,A.o Ox 1).0))/.11
where k4.1.11 &Vz,,,, ( (sh, att and 0x,1 1 is the solution the - regression problem
with predictor Φb against response V (sh+1)) Similar to the estimating procedure of 0g.0- we set 1 based on [VV2,++1 a²)) + E.,,, which is upper bound of [VV VVE ( at) with high probability. Repeating this process, we recursively estimate the conditional 2 -th moment of Vk.b+1 by its variance in Algorithm which is dubbed as high-order moment estimator.
MAIN RESULTS
5.1
REGRET UPPER BOUND FOR HR-O2PS
We first provide the regret bound for HF-OřPS.
Theorem 5.1. Set M = (4K E / dd(KK)), = 1/d A= d/B², and a = H/VK. For any d 0, with probability at least 1 (3M + 2)6, Algorithm yields regret bounded as follows:
Regret K) = (((d log (1S VK + +d²)
(5.1)
Remark 5.2. By omitting the logarithmic terms in 5.I). HF-OPPS achieves horizon free regret upper bound Ö(dvK + dd). Our regret bound is better than Ō((H + d)vK + df obtained by He et al. (022bb) when = 2(log (I). Additionally, compared with HF-UCRL-VTR+ algorithm proposed by Zhou & Gu (2022) for episodic linear mixture MDPs with fixed reward, HF-OPPS provides robustness against adversarial reward while maintaining its regret upper bounded by Ö(dvK + dd).
5.2
HARDNESS RESULTS
We also provide two regret lower bounds. The next theorem gives a regret lower bound of MDPs with known transition and adversarial reward.
Theorem 5.3. When H 2H, where H positive integer, for any algorithm and any given nonempty action space A. there exists an MDP satisfying Assumptions 3.1 and
3.2 with d = 1 and
|S| =((AAl)) such that
lim lim [[Regret(K)] 10000 /K log AA]
1
E Regret) (K)
2
V2
and
-1000
lim
lim
K log S
C2 2/2

---

Published as a conference paper at ICLR 2024
Remark 5.4. Theorem 5.3 indicates that even the estimation enror Iz disappears in (6.1 which means we are in the "learning- -aeee--feeeeee setting, with infinitely large S, purely the adversarial environ- ment can introduce VH dependency asymptotically. Therefore, we can only expect a horizon-free algorithm whose regret upper bound at least depends on log [S], and K.
The following theorem provides another regret lower bound of learning homogeneous linear mixture MDPs with adversarial reward.
Theorem 5.5. Let B > and K max _ (d 1) 1))}. for any algorithm. there exists a B-bounded adversarial MDP satisfying Assumption I.d 3.2 such that the expected regret E [Reegett( K)] has lower bound dv / (1163)..
Remark 5.6. Theorem 5.5 shows that when K large enough, any algorithm for adversarial MDPs satisfying Assumption 3.1 and 3.2 has regret least ((dvK). Moreover, the regret lower bound in Theorem 5.5 matches the regret upper bound in Theorem 5.1 which suggests that HF-OPpS is near-optimal.
6 PROOF OVERVIEW
In this section, we provide the proof sketch of Theorem 5.. and illustrate the key technical issues.
Proof sketch of Theorem 5.1 First, we have the regret decomposition:
K
K
K
Regret(K) = (Vin(s1) (s.)(s1)) +
(Vo,1(81) - (s
+
(Vr.(81) - (s11
Is
(6.1)
Bounding I1. I is the regret of policy updating. By the standard regret analysis of OMD, the regret probability simplex is bounded by O(IVK) where I. is the upper bound of the gradients and K is the number of iterations. In MDPs, we have // decisions to make in each episode. There- fore, policy updating can be seen as conducting mirror descent simultaneously on H simplexes, and the total regret is the summation of regret on each simplexes. Consequently, the regret upper bound is roughly O HT. K), where is the average upper bound of the gradients over all the simplexes. In OPPO (Cai et al. 2020) and POWERS (He (022b), the policy is updated via proximal policy optimization: nx (a)s) & o 1 (a) exp(aQu- ).). Hence the gradients is QR-1,n a), which, after taking average over h E [H]. result in an average L = O(1) and consequently regret bound of Ō(HVK) To address this issue, consider using r* as the gradients, which is enabled by introducing an occupancy measure. By Assumption 3.I. the standard regret analysis OMD results in 11 = Ō(vK).
Bounding Iz. Iz can be further decomposed into three major terms, the sum of bonus, transition noise and policy noise. Roughly, we have:
H
Ig
PV (s (sh (1.1
E a (
Qki Qu. ah)]
Rm h
Armm 2
(ii) transition noise
(ii) policy noise
Qk (5 ah) r(s at) PV (h)) +r.
banus terms
where I' is defined as follows, which can be bounded by Ō(VK) using Azuma-Hoefiding's inequal- ity:
K
K
(Bon (s) (sf,
r
a
VIT' (sf)).
A=1
The standard way to bound the bonus term is applying the total variance lemma (Jin et al. 2018 Lemma C.5) to the total variance of transition noise (He et al. 20226 Zhou et al.) 2021 However,
8

---

Published as a conference paper at ICLR 2024
in our case, naive adaptation of He al. (2022b) Lemma 6.4) and total variance lemma results in upper bound with VK dependence. Also, the transition noise and policy noise can only be bounded using standard concentration inequalities, which results in another VKH term.
To shave poly(F) H)) off, we propose to bound the bonus term and transition noise recursively inspired by Zhou & Gu (2022), cquipped with the variance- cunpuceennntttttt--aaaa aware weighting mechanism and Algorithm] One notable challenge is to tackle the randomness in x (-I-). (iii), to which simply applying Azuma-Hoeffding inequality will yield H) We follow the procedure of bounding (ii) in Zhou & Gu (202)) where the transition noise of order m is first bounded the sum of condi- tional variance VV (5) af - using martingale concentration inequality. Then, the key step bounding the conditional variance with higher order transition noise as follows:
VVEN (1h- of s X(m) PV.."" 13 (s -
ai
k. (sh)
E.A ((s) VE
Qe (s
transition noise of higher order
(6.2)
where X X(m) only depends on m, the second term of the right hand side is exactly the transition noise of higher-order Value function. For argmax policy, the martingale difference (*) in (6.2) is O,
which indicates that the total variance can be bounded by the martingale difference of higher order. For policy noise which did not appear in (Zhou & Gu 2002), we first bound (*) by the sum of conditional variance, each term of which is:
E (1)) Qi,h gm (sh a)] - E²
(axx((1ef)) 1 (
E Bawaf((st) 1Q
mm (sh, a)] - Qi (sh a + Qia (sh, a - Ba Pawn QR, (s a)}-
(6.3)
Because 6..2 always holds whether x is stochastic, combining 6.2 with 6.3
we have the follows:
Pa-nt (lot)) (s a)] - E² E (11s)) 1Q ( (sh, a)] + VV (8h-1, a
((m) PVet** ( Vi. (5h) + TE (aant( 1
2m (sh a)]
2h (sh at)
k. (0%)
E² or (- 1 (sh m)],
which nearly the same as (6.2) except (**). Therefore if we view the transition noise (*) and policy noise (*)) as a single martingale, then it can be bounded by total noise of higher order the same as 6.2). The rest framework of HOME in Zhou Gu (202)) can be adapted smoothly and yields an upper bound O(dvK + d²).
Bounding T3. I3 is the gap between the optimistic value function derived from occupancy measure guided policy updating and the other one derived from backward iteration (Line of Algorithm [ By Lemma 3.3 for each & E [K]. the occupancy measure {zf Ju induces a new MDP and policy. Then 2t E DR implies that the transition still lies in the confidence set, thus can also be bounded by (s,((:)) ()) and (+). Formally, we have the following lemma:
Lemma 6.1. For all E [K). let VR. (s1) be the optimistic value function given by occupancy
measure and Vs, the value function computed by backward iteration (Line 11 We have (E,1 & Va,1($1), and thus I3 < O.
Finally, combining the upper bounds of all three terms finishes our proof.
7 CONCLUSION
In this work, we considered learning homogeneous linear mixture MDPs with adversarial reward. We proposed a new algorithm based on occupancy measure and high-order moment estimator. We show that HF-O*PS achieves the near-optimal regret upper bounded Ō(dvK K + d²). To the best of our knowledge, our algorithm is the first horizon-free algorithm in this setting. Currently, our result requires the uniformly bounded reward assumption, i.c., Assumption 3.I, For horizon-fiin free algorithms require only the total reward in each episode bounded by 1, we leave it as future work.

---

Published as a conference paper at ICLR 2024
ACKNOWLEDGEMENTS
We thank the anonymous reviewers and area chair for their helpful comments. JH and QG are sup- ported in part by the National Science Foundation CAREER Award 1906169 and Amazon Research Award. JH is also supported in part by Amazon PhD Fellowship. WZ is supported by UCLA Disser- tation Year Fellowship. The views and conclusions contained in this paper are those of the authors and should not be interpreted as representing any funding agencies.
REFERENCES
Yasin Abbasi- Yadkori, Dávid Pál, and Csaba Szepesvári. Improved algorithms for linear stochastic bandits. Advances in neural information processing systems, 24, 2011.
Eitan Altman, Constrained Markov decision processes: stochastic modeling. Routledge, 1999.
Alex Ayoub, Zeyu Jia, Csaba Szepesvari, Mengdi Wang, and Lin Yang. Model-based reinforcement learning with value-targeted regression. In International Conference on Machine Learning, pp- 463-474 PMLR, 2020.
Kazuoki Azuma. Weighted sums of certain dependent random variables. Tohoku Mathematical Journal, Second Series, 19(3):357-377, 1967.
Heinz H Bauschke and Jonathan M Borwein. projection algorithms for for solving convex feasibility problems. SIAM review, 38(3):367-426, 1996.
Heinz H Bauschke and Adrian S Lewis. Dykstras algorithm with bregman projections: conver- gence proof. Optimization, 48(4))409-42)) 2000.
Qi Cai, Zhuoran Yang. Chi Jin, and Zhaoran Wang. Provably efficient exploration in policy opti- mization. In International Conference on Machine Learning, pp. 1283-1294. PMLR, 2020.
Yair Censor and Simeon Reich. The dykstra algorithm with bregman projections. Communications in Applied Analysis, 2(3):407-420, 1998.
Nicolo Cesa-Biance and Gabor Lugosi. Prediction, Learning, and Games. Cambridge University Press. 2006. doi: 10007//B09770511546999
Liyu Chen, Rahul Jain, and Haipeng Luo. Improved no-regret algorithms for stochastic shortest path with linear mdp. In International Conference on Machine Learning, pp. 3204-3245, PMLR, 2022.
Thomas M Cover. Elements of information theory. John Wiley & Sons, 1999.
Yan Dai, Haipeng Luo, and Liyu Chen. Follox--heepeetuubbd--eeeee for adversarial markov decision processes with bandit feedback. arXiv preprint arXiv:2205.1344 2022.
Christoph Dann and Emma Brunskill. Sample complexity of episodic learning. Advances in Neural Information Processing Systems, 28, 2015.
reinforcement
Travis Dick, Andras Gyorgy, and Csaba Szepesvari. Online learning in markov decision processes with changing cost sequences. In International Conference on Machine Learning, pp. 512-520. PMLR, 2014.
Simon Du Sham Kakade, Jason Lee, Shachar Lovett, Gaurav Mahajan, Wen Sun, and Ruosong Wang. Bilinear classes: A structural framework for provable generalization in rl. In International Conference on Machine Learning, pp. 2826-2836. PMLR, 2021.
Simon S Du, Sham M Kakade, Ruosong Wang, and Lin F Yang. Is good representation sufficient for sample efficient reinforcement learning? In International Conference on Learning Represen- fations, 2019.
Eyal Even-Ded -ar, Sham M Kakade, and Yishay Mansour. Online markov decision processes. Mathe- maticy of Operations Research, 34(3):726-736, 2009.
10

---

Published as a conference paper at ICLR 2024
Jiafan He, Heyang Zhao, Dongruo Zhou, and Quanquan Gu. Nearly minimax optimal reinforcement learning for linear markov decision processes. arXiv preprint arXiv:2212.061.22 2022a.
Jiafan He, Dongruo Zhou, and Quanquan Gu. Near-optimal policy optimization algorithms for learning adversarial linear mixture mdps. International Conference on Artificial Intelligence and Stafistics, pp. 4259-4280 PMLR, 2022b.
Zeyu Jia, Lin Yang, Csaba Szepesvari, and Mengdi Wang. Model-based reinforcement learning with value-targeted regression. In Learning for Dynamics and Control, pp- 666-686. PMLR, 2020.
Nan Jiang and Alekh Agarwal. Open problem: The dependence of sample complexity lower bounds on planning horizon. In Conference On Learning Theory, pp. 3395-3398. PMLR, 2018.
Nan Jiang, Akshay Krishnamurthy, Alekh Agarwal, John Langford, and Robert E. Schapire. Con- textual decision processes with low bellman rank are pac-leamable. International Conference on Machine Learning. 2017.
Chi Jin, Zeyuan Allen-Zhu Sebastien Bubeck, and Michael Jordan. Is q-learning provably effi- cient? Advances in neural information processing systems, 31, 2018.
Chi Jin, Tiancheng Jin, Haipeng Luo, Suvrit Sra, and Tiancheng Yu. Learning adversarial markov decision processes with bandit feedback and unknown transition. In International Conference on Machine Learning, pp. 4860 PMLR, 2020a.
Chi Jin, Zhuoran Yang, Zhaoran Wang, and Michael Jordan. Provably efficient reinforcement learning with linear function approximation. In Conference on Learning Theory, pp. 2137-2143. PMLR, 2020b.
Chi Jin, Qinghua Liu, and Sobhan Miryoosefi. Bellman eluder dimension: New rich classes of problems, and sample-efficient algorithms. Advances in neural information processing systems, 1113406-13418 2021.
K. C. Kalagarla, Rahul Jain, and Pierluigi Nuzzo. A sample-efficient algorithm for episodic finite- horizon mdp with constraints. In AAAI Conference on Artificial Intelligence, 2020.
Yeoneung Kim, Insoon Yang, and Kwang-Sung Jun. Improved regret analysis for variance-adaptive linear bandits and horizon-free linear mixture mdps. Advances in Neural Information Processing Systems, 35: 35:1060-1072. 2022.
Haipeng Luo, Chen-Yu Yu Wei, and Chung-Wei Lee. Policy optimization in adversarial mdps: Im- proved exploration via dilated bonuses. Advances in Neural Information Processing Systems, 34: 22931-22944 2021.
Gergely Neu and Julia Olkhovskaya. Online learning in mdps with linear function approximation and bandit feedback. Advances in Neural Information Processing Systems, 34: 14:44-77-1,,,7, 2021.
Gergely Neu and Ciara Pike-Burke. A unifying view of optimism in episodic reinforcement learning. Advances in Neural Information Processing Systems, 33:1392-1403, 2020.
Gergely Neu, Andras Antos, András György, and Csaba Szepesvári. Online markov decision pro- cesses under bandit feedback. Advances Neural Information Processing Systems, 23, 2010.
Gergely Neu, Andras Gyorgy, and Csaba Szepesvári. The adversarial stochastic shortest path prob- lem with unknown transition probabilities. In Artificial Intelligence and Statistics, pp. 803-813. PMLR, 2012.
Aviv Rosenberg and Yishay Mansour. Online convex optimization adversarial markov decision processes. In International Conference Machine Learning, pp. 5478-5486. PMLR, 2019a.
Aviv Rosenberg and Yishay Mansour. Online stochastic shortest path with bandit feedback and unknown transition function. Advances in Neural Information Processing Systems, 32, 2019b.

---

Published as a conference paper at ICLR 2024
Lior Shani, Yonathan Efroni, Aviv Rosenberg, and Shie Mannor. Optimistic policy optimization with bandit feedback. In International Conference on Machine Learning, pp. 8604-8613. PMLR, 2020.
Wen Sun, Nan Jiang, Akshay Krishnamurthy, Alekh Agarwal, and John Langford. Model-based rl in contextual decision processes: Pac bounds and exponential improvements over model-free approaches. Conference on learning theory, pp.
PMLR, 2019.
Richard S Sutton and Andrew G Barto. Reinforcement learning: An introduction. MIT press, 2018.
Csaba Szepesvári. Algorithms for reinforcement learning. Synthesis lectures on artificial intelli- gence and machine learning, 4(1):1-103, 20100
Jean Tarbouriech, Runlong Zhou, Simon S Du, Matteo Pirotta, Michal Valko, and Alessandro Lazaric. Stochastic shortest path: Minimax, parameter-free and towards horizon-free regret. Ad- vances in Neural Information Processing Systems, 34:6843-688 6855, 2021.
Ruosong Wang, Simon S Du, Lin F Yang, and Sham M Kakade, Is long horizon reinforcement learn- ing more difficult than short horizon reinforcement learning? arXiv preprint arXiv:2005.0052) 2020a.
Yining Wang, Ruosong Wang. Simon Shaolei Du, and Akshay Krishnamurthy. Optimism in rein- forcement learning with generalized linear function approximation. In International Conference on Learning Representutions, 2020b.
Gellért Weisz, Philip Amortila, and Csaba Szepesvári. Exponential lower bounds for planning in mdps with linearl--realizabl optimal action-value functions. In Algorithmic Learning Theory, pp. 1237-1264. PMLR, 2021.
Lin Yang and Mengdi Wang. Samplc-optimal parametric q-learning using linearly additive features. In International Conference on Machine Learning, pp. 6995-7004. PMLR, 2019.
Jia Yuan Yu, Shie Mannor, and Nahum Shimkin. Markov decision processes with arbitrary reward processes. Mathematics of Operations Research, 34(3):737-757, 2009.
Andrea Zanette, Alessandro Lazaric, Mykel Kochenderfer, and Emma Brunskill. Learning near op- timal policies with low inherent bellman error. In International Conference on Machine Learning, pp. 10978-10989, PMLR, 2020.
Zihan Zhang, Simon S Du, and Xiangyang Ji. Nearly minimax optimal reward-free reinforcement learning. arXiv preprint arXiv:2010.05901, 2020.
Zihan Zhang, Xiangyang Ji, and Simon Du. Is reinforcement learning more difficult than bandits? near-optimal algorithm escaping the curse of horizon. In Conference on Learning Theory, pp- 4528 4531. PMLR, 2021a.
Zihan Zhang, Jiaqi Yang, Xiangyang Ji, and Simon S Du. Improved variance-aware confidence sets for linear bandits and linear mixture mdp. Advances in Neural Information Processing Systems, 34:4342 4355, 2021b.
Zihan Zhang, Xiangyang Ji, and Simon Du. Horizon-free reinforcement learning in polynomial time: the power of stationary policies. In Conference on Learning Theory. pp. 3858-3904, PMLR, 2022.
Canzhe Zhao, Ruofeng Yang. Baoxiang Wang, and Shuai Li. Learning adversarial linear mixture markov decision processes with bandit feedback and unknown transition. In The Eleventh Inter- national Conference on Learning Representations, 2023.
Dongruo Zhou and Quanquan Gu. Computationally efficient horizon-free reinforcement learning for linear mixture mdps. arXiv preprint S.xXi::205.115:5 2022.
Dongruo Zhou, Quanquan Gu, and Csaba Szepesvari. Nearly minimax optimal reinforcement leamn ing for linear mixture markov decision processes. In Conference on Learning Theory, pp. 4532- 4576. PMLR, 2021.
12

---

Published as a conference paper at ICLR 2024
Runlong Zhou, Ruosong Wang, and Simon S Du. Horizon-free free reinforcement learning for latent markov decision processes. arXiv preprint arXiv:2210. 1600,, 2022.
Alexander Zimin and Gergely Neu. Online learning in episodic markovian decision processes by relative entropy policy search. Advances in neural information processing systems, 26, 2013.
13

---

Published as a conference paper at ICLR 2024
A ADDITIONAL RELATED WORKS
Table 1: A comparison of related horizon-free algorithms and algorithms for adversarial linear mix- ture MDPs
Adversarial Reward
Extra Requirements
Algorithm
Regret
Assumption
VARLin
Homogeneous, En 1 Homogeneous, En S Homogeneous, Σn nh 1 Homogeneous Th 1/H
O(d VK d
No
Zhang et al.
2021b
VARLm2
n2
Ō(dvK + +
No
Kim et al.
2022
HF-UCRL-
VTR
ÖldvK + +
No
Zhou & Gu
2022)
Lower bound
((dvK)
No
K 2 df
Zhou & Gu
2022)
OPPO
Inhomogeneous, Σn th S H Inhomogeneous, Σn Th S H Homogeneous, Th 1/H Homogeneous, S 1/H
d 2 log AAl,
Ō(dHPVK)
Yes
Cai et al.
2020)
K 2 poly (d. H)
POW ERS
d Z log Al,
Õ(dv H3))
Yes
(He ct al.
2022b
K 2 poly (d, H)
Ours
Theorem 5.1
Yes
d 2 log A
Open
Lower Bound
Yes
K 2 d
At least ()
RL with linear function approximation To make MDPs with large state space amenable for provable RL, there has been an explosion of works relying on MDP classes with various linear
2021 Jin et al. 2021). Among different assumptions made in recent work Yang & Wang 2019 Wang et al. [020b] Uin et al. 2020b) Du jet al. 2019 Zanette et al. 2020 Ayoub al. 2020 Jia et al. 2020 Weisz et | Zhou al.
structures (Jiang et al. 2017; Sun et al./ [2019] Du et al.
2021
we consider the linear mixture MDP setting (Jia al. 2020 Ayoub al. 2020 Zhou et al. 2021 Zhang et al. 2021a He et al. 20226),
He et al. [20226 Zhou & Gu 2022, He et al., 2022a)
where the transition kernel is a linear combination of given models. More specifically, we focus (2022b). whose approach nearly minimax optimal but insufficient to obtain horizon-free regret, with refined reward assumption. There is also a parallel line of work (Jin et al. 2020b He al. (022a) investigating the linear MDP model of Din et al. (2020b) with much larger degree of freedom, where the transition function and reward function are linear in a known state-action feature mapping respectively.
on the adversarial linear mixture MDP He et al.
B PROOF OF LEMMAS IN SECTION 4 AN SECTION
B.1 PROOF OF LEMMA 4.2
Proof. Say we have two occupancy measures z, w, then we have
(s, s') log 2n s') w/(s,, a,
Do(2llw) = Σ Σ
1=1 s,a."!
H
>
5n(8,,,88)) wp wn (s,,
2 h=1
a,a,s!
1
H
[n,s, 8) = 2
2H
1=1 8.a.e'
1
2
w
2H
where the first inequality holds due to Pinsker's 's inequality and the second incquality holds due to Cauchy-Schwartz inequality.
14

---

Published as a conference paper at ICLR 2024
B.2
PROOF OF LEMMA 6.1
Given a set of occupancy measure, we define the respective transition as the Proof of Lemma
follows:
(s, (x,
( k ((6'1,,0))
V(s,a, h) E S A S.L. Σ
( 0.
Now let's consider another MDP M = (S, H, (Tn), (PP,,h,s. where the state space, action space, length of horizon, reward functions are the same as the true MDP M, and (- = (.).).) However, our new MDP is tabular one and its transition kernel is different from M. Consider running first inner loop in our algorithm (line I0 line 12). since M and M2 share the same reward function, and the other terms also do not depend true transition, the results running on the two MDPs should be the same.
For the sake of simplicity, we (recursively) define the value functions on the imaginary MDP M
Vx, O, Qu, a) = (s, a) + (0 Φv n4i (s, (s) (las))=an(((al (a]s) [2 (s.a)].
Then it is easy to verify that (81) computed by occupancy measure is the same as the one computed by the above way. Then, we prove our theorem by induction. The conclusion trivially holds for n = H + 1. Suppose the statement holds for n = h + 1, then for n = h, for each (s, (s,a), since (s,n(s,a)
1, so if (s, a) = then the proof is finished. Otherwise
have:
( Qk,((s,a) a) - (s, 2 (0x,0- Iv (3:-) + Bellove,n (, (1-))ls: - (0s,a, A (8, a))
(0z.o O asahh @v (.,)) + Ba Bellora (1s
Ba @vll ( (s.))ls @O.. a2.a,t.k Ss. ll (: )1
20,
where the first inequality holds by the inductive hypothesis, the second inequality holds due to Cauchy-Schwartz inequality and the third inequality holds due to a E Cg. By induction, we finish the proof.
C PROOF OF THE MAIN RESULT
In this section, generated by the random variables representing the transition noise and the stochastic policy noise. For k [K], h [H], we define FR, the o-algebra of state and actions till stage k and step h, and GK. the state till stage k and step h. That is,
going provide the proof of Theorem First, define the o-algebra
$1 a .... h/ 0/. .... st, af
1
2 2
2 2
$ Q1 ....
h: Oh:.... ..., H H
6 1
4 m. 8b 4/
k
generates FR.h, and
81 a]:
8/g 0h:
H dH
$7 a ..., s 2
$ a s/
generates Gk. Second, we define J/ as
(ff(ss = E Eu Een
(C.1)
for any h) E [K] [H] and function f: A - R for simplicity.
15

---

Published as a conference paper at ICLR 2024
C.1 LEMMAS FOR SELF- CONCENTRATION MARTINGALES
In this section, we provide two results of concenennnnnotioon martingales, which are key to our proof. Lemma C.1 (Lemma B. Zhou Gu 2022). Let {or, R2 be sequence of non-negative num- bers, E.Y > O, (xx k22 C R and in the following way: Z1 AI,
Xx 22
L. Let (2 and {ōx) be inductively defined
Vk 2 0R [ok & 7//l/x
(2,1) Za+1 Zs + X 10
2
Let L log(1 + KL2 (dd)))) Then we have
K min 11, Bxx|Ixxxll, S 2de + 2 max
K
BKY di + 2V di ke(K]
(2 + +
Am1
k=
Same as in Zhou & Gu 2022)) first we need to prove that the vector O lies in the series of confidence sets, which implies the estimation we get via occupancy measure is optimistic and the high-order moments are close to their true values.
Lemma C.2 (Lemma C.1, Zhou & Gu 2022). Set (3 as 4.6). then, with probability at least - M6, have for any &s E [K], [H], m [M].
[1 0²) 11s I Bkg |1 1 ah) - [VV af1 S Eg.
Let f denote the event described by Lemma C.2 The following lemma provides high-
probability bound estimation error terms.
Lemma C.3. On the event fcg we have for any [K] [H].
(s att r(s att PVA,4+ at) s 2 min {1, Ba 1 pu.,ool2))
Proof of Lemma C33 The proof is almost the same that of Lemma C.4 in Zhou & Gu 2022 only to replace ( with Qu, of).
C.2 RECURSIVE BOUNDS FOR STOCHASTIC POLICY
For any &e E [k). h [H), we define the indicator function I as the following
/ (vm [M], det(
km det S k.m). 4),
where 1 is obviously Gh measurable and monotonically decreasing with respect to h for all k
[K]. For all m E [M], we also define the following quantities:
K
H
Rm
I min 11,3u112 1/2 $2.
(C.2)
Jmn Am
K
Am
hh
i al:)
(s + P (
aht)
km h=
(C.3)
Sm
Σ
VV 15t at) 1 (s [Jh ( (s
(C.4)
K
G Σ (1- 15)
(C.5)
1=1
Finally, for simplicity, we also define
1 = log(1 + KH KH)(dX)))),
(C.6)
log(4 log( K H))8).
(C.7)
16

---

Published as a conference paper at ICLR 2024
Remark C.4. Our definition is nearly the same as in Zhou & Gu (2022), despite that in our algo- rithm we use stochastic policies, which induce an additional term each in Am and Sm. regarding to the random variable and its conditional variance of the policies noise.
Now we are going to bound all these quantities. Basically, the technique we are using nearly the same as in /hou & (2022..) The only difference is that we need to deal with the extra policy noise resulted by stochastic policy.
Lemma C.5. Y. & be defined in Algorithm then for m E [M - 1], we have
Rm < (ide + 8 83x v di / Sm + 4Bm + 2Rm+1 KHE, KH}.
(C.8)
We also have RM-1 S K..
Proof. For (ks h) such that 1 1, using Lemma D.2
we have
det 2k.m)
1/2 km Pk,
E k &.. 1l
1/2
S 4/ E 1122 &K.
del km
Substituting the above inequality into C.2). we have
K
Rm
min {1, 1,
Σ 11112 1/2 k.h.m &..h, 112
k= h=1
where the right hand side can be bounded by Lemma h. and Zy.n Ek. We have
C.1 with BE, = 3k. Th.h = Ok.hmm Xk.h
K
1
min
Σ
1/2 k.h.m pm.m.mll2)
k=1h=1
2di 2ddi
<
2d 2,3x Vd..V
h VVVV ( Fa.h.m) KH
< 2d 23xx 23x Vde.
Hh 2I a 2E + KH
< 2di 23x 23 23x
WVV (5t, 4Rmm + 22 KHz2 (C.9)
Since we have
ΣΣ
1h Uh (ht (Jh (hmm 20
A=1
which, substituted into C..). gives
h V (5 at) S Sm.
(C.10)
Therefore by substituting (C.10) into C.9
we have
h Σ
Rm < 8di 2 88k ddi
WVVE (st, at) + 4Rm 2Rm+1 + KH
I 8di 88x 88x V di
Sm 4Rm + 28 KH
which completes the proof.
17

---

Published as a conference paper at ICLR 2024
Lemma C.6. On the event c for all E [M - 11, we have
Sm S Am+11 + 2 (K 2Ro) + G.
Proof.
The proof follows the proof of Lemma C.6 in Zhou & Gu (2022) and Lemma 25 in Zhang We have
et al. 2021b).
k
Sm
1 (VVEnti att + 1h+1 Q (Einth11)))
K
H
1 (PVEntiiShh att Qi
H
((PV a
H
2hta 2m
(sh. af)
H
1
- [1h+1 1 (+h+))))))))
PPV att v2 (5h422) + Jhtt Qh.ht
k,
Am
K
H
I ( ab) (IPV ((PVR
K
H
11 (sh - 22th (sh aft
Ih
(VVR (1 (+++))))+)1))))
The first term here is exactly Am+1, have
Sm = Am+1* +
ORT (5% (IPV (IPV22"+2I< (f
1=
A I (5t ah+1) Qi (s at)
K h
1 (V - Of
h=1
Am
I (sh att - (IPV2 +f
k=1
H
the
1 (v2 Of
where he the largest index satisfying 1/ hf H. we have 1h Qh ( i +1
1
Th, and if by H. we have Th, Qu (sk +1, ah 0 The in both
18

---

Published as a conference paper at ICLR 2024
circumstances have
K
K
Sm S Am +
(sh, ah) - (I a
(ii)
K
22 (, - (1 Qua 1 (st+111)1
(C.11)
For (ii) in
C.III.
we have
k
H
2m (sh aht - att) 27
k=
h=1
K
H
'2tmi' (sh. att (IPVi.N+11s aHt) 2
h
k= h=1
(Q (0%, a/)
10 (t) I (6h ah) + (PVea++1l(h af))
K H
5
ΣΣ
ah: + 2mmmm1 E Φx 12
km1bm1
<2 (K + 2Ro),
where the first inequality holds by recursively using EX² 2 (E²X), the second holds due to As-
sumption 3.1 and the third holds due Lemma C.3 remains to bound the last term (iv) in (C.11
We have
H
t IVE 1Jht1 +1
K
The ((Th+)Q0++(((L))) [T Dh, (s
H
(4 a) (
E2
(1 111 Qu. (10 ( (sh+zl))
<0,
where the first equality holds due to the definition of Vk (s the second holds due to 7 is IK. meaasurble,, and the inequality holds due to x 2 (B2X) X). Combining the estimations of the four terms completes the proof.
Lemma C.7 (Lemma 25, Zhang et al. 2021b). We have P( Cean
- 2M8, where
('m E [M] |Am| S. min / /25S {.2KH)).
Proof. The proof follows the proof of Lemma 25 in Zhang et (021b). First, we define
1/ 1PV2 at)) 122h V2 (
Tk.h
Blæa, 0, Elyn.n (r.
yk.h = 1 W
Q 1 (sh +21
0.
Obviously, {œ1,1, Vi.,, Fk.h: 3h.hh forms martingale difference sequence, whose conditional second-order moments are
Ej Fu.n 1 k. (sft, af),,
E E (3, = T/e [Jh PiTi (shir) -II 1
19

---

Published as a conference paper at ICLR 2024
Summing these terms over [K] x [H] yields
K
E BR
(k, Sm
(C.
Therefore, by Lemma D.3 for each m E [M], with probability at least we have
Am S 2Cs +
Taking union bound over m E [M] and also using the fact that | [yk.al S completes the proof.
Lemma C.8 (Lemma C.8. Zhou Gu 2022). Let be defined (C.5) then we have S Mdt/2.
Finally wer provide the high-probabilie bounds of two remained martingales, both of which are direct application of Lemma D.I
Lemma C.9. With probability at least we have
Σ (r(s at) - V/ (o4) vx9) s /2K log(1/0).
Lemma C.10. With probability at least 1 - 6, we have
(f (n.1(st,att) af)) s /2K log(1/8).
We use from and f to denote the event described by the corresponding lemmas.
C.3
PROOF OF THEOREM 5.1
Now proof main result. First going provide two theorems, The first theorem provides a horizon-free regret analysis of high-order moment estimator.
Theorem C.11. Set M log( (gg44HH) log 2, for any 8 > O, on event E we have
Regret(K) < 2432 max 192 2 + 3x v di Mdt/2 /2 + KHa
Mdi/2 + 24( 24(v(MMa () + 22ol 32 max (83 max Vdl, /2
where Ç are detined in C.6 and
Moreover, setting & Vd/(KH), = 1/dt/4 and
A d/B² yields bound T2 Õ K d3) with high probability.
20

---

Published as a conference paper at ICLR 2024
Proof. All the following proofs under the event C.2
20.9
1:
First, we have the
composition for 12, for all k, we define Q), =0.
K
E
(J+t) (s.((ta.ff))
K
( QK+INTI (h
h=1
K
(U$ (x.1(s),
The (Qu,l(s at) (ut1an1((hs::0
(C.13)
K
H
(1 (Qnn((h) - -0-LLAt(6Sh
K
(s. + Σ(
(1 - 1 Qu,nu (She
k=1
k=1
(Q at) QU+1,1+155 +f))
where hg is the smallest number such that 1he = 0. Then for the second term we have
K
H
1h (5h aht - -K++LA+1 1)+)))
hs ab)) + ΣΣ
Qh att r(5 aati (V af)l
k=1A=1
H
IlPV,, LIPV (s aht V + Jht1 1(th Qu ah+1)l
km
K
H
K
rs
+
I o r(sh a PV a/)1 + Ao.
K=
Am h=1
Substituting the inequality above to C.13
we have:
(sf Vi=" (of))
K (Jt) - (st( + Σ
K
K
H
(r(sh, -
k=
k=1
k=1
h=1
K
H
1s - r a - PV at) + Ao
< / log((18//) + G + 2R + Au
where the second inequality holds due to Lemma C.10 Lemma C.9 and Lemma C.3 Thus, we only need to bound 2Ro + Ao. We have
A S /2 +
S (/(((AAmee + G 2 (K + 2R)) +
S /2C /Ammt + 2 |(K + 2Rn) + /2çG + +
21

---

Published as a conference paper at ICLR 2024
where the first inequality holds due Lemma C.7 the second inequality holds due to Lemma C.6 and the third holds due to V + 6 S va + vb. We also have:
Rm S 8di + 7 de + 83k V du / / Sm + 4Rm 22m+1 + KHo²
8,3 v di A Am+1 + G + 2m+ (K + 2Ro) + 4Rm 2mm+1 + KHo
8dl + 7
83K v di v Ll/lAmit Am++ 2m (K + 2Ro) 4mm 2Rm+1
8du + 8 di + 83x Vdiv + KHa?
where the first inequality holds due to Lemma C.5 the second holds due to Lemma C.6 and we denote To = 8ds + 7 88 d + KHo + /2CG+( Combining the two estimations have
Aml + 2Rm s 21. + 2 max m83 Ve. 2
v 55 + 5 2m (K 2Ro) + 16Rm + 88m+1
S 21 + 4 max 10,xx883xx0 de, 2
v Am+il 2mm+1 + Am + 22 + 2 IK 2Rg + AAo)).
where the first inequality holds due to vā + vb S 2(a + +b. Then by Lemma D.4 with am.
2 Am + Rm I 4KH and M log(4K log have:
|Aol + 2Rp s 22 16 max max (643x de, 2(} + 12Ic
+ 16 max V8kVall di, 2 2((K + 2Ro (Ao)
< 704 max (32,x di, {}
+ 12(ddi x di 8BK VKK
+ 2(G+
+ 16 83 V de, / 2K + 16v max (83x Vdi, / / /2 + |Aul.
2
By the fact that x S a
< 2a 2b, we have
AAo + 2Ro < 2432 max m32, di,c}
+ 24(8di + 8, 2 de + 83 V v2(G+
32
de, 2C
Bounding G by Lemma C.8
we have
Σ (Vr. (s)) < 2 log(1/6) G 222g Aa
< 2432 max de, { + 192 3K7 de 3x de M
+ +ddi/2 24( 24(VcMdd () /2/2 +2 (1/0) 32x Vdl, /2cH]V2K,
which completes the proof.
Theorem C.12. On the event we have
K
H log |
Ka 2H
Σ (V221(s)) -
<
Proof. This follows the standard regret analysis of online mirror descent. The only difference from standard arguments is that need to deal with the changing convex set. We include the adapted proof for completeness. For sake of brevity, we denote fu(z) = Eh.sa Zh Zn a, s')) a), then we have
fx(=") (s1), Sa(=*)
(o1( V(a(-) (rh( a)),,a,d
22

---

Published as a conference paper at ICLR 2024
where 2" is the occupancy measure induced by X² and true transition. Since we have that for all E [1: KJ. 0" E Ck. we know that x" E D& for all k. Then we have
f = (= (=* =*
(x" =D (1=" + 1=
= (VQ((v) k+
D (0 (x(x"Ilu**))
where the equities hold due to the update rule of mirror descent. Because Da+1 is convex and =" D&+1, we have the first order optimality for 2k+1;
(v v T) (2 - 2n) S 0.
which can be written equivalently as the generalized Pythagorean inequality: 10==+11110**0
1= (=
(C.14)
Combining the two expression, we have
fa(=)) fa(=")-f(==)) x a a "(xx(="1>*))) (2(2"11= For the second term, we have
(1 + -1 '(D -
(2
Da( Do Do(
= -(=*) - 11= v
- =
s (V)(=*)) - (0 (z"
=
.+1 11
2H
aVi (2* 1= =b
1
||* z ++ 2
1|
2H
<
H k+] 111
a
1
11
- 2 k-1
11
2H
a²
2H
where the first inequality holds due to Lemma 4.2 the second inequality holds due r* (c,)) $ 1/H. and the third inequality holds due to quadratic inequality. Summing up over k, we have
K
aK
Σ ((())))((()))))))) s (Do(2"))) - Dz D0((=1122ktt) +
2H
D
Ka
2H
(=
Ka
a
2H
H Hog ||
Ka
2H
where the third inequality holds due extended Pythagorean's inequality (C.14) and the forth holds since wf = 2A is an uniform distribution on S x A x S.
Now we are able to prove our main result.
Proof of Theorem 5./
First we have the following regret decomposition
K
(81) - VITh (s1))
(s)) (11) + Vh.1 Ve,1(81) + Va.1(s)) - (s1))
k (Vi, -VT((s))),
(Vii(5)) Vs..(s1))
23

---

Published as a conference paper at ICLR 2024
where the inequality holds due to Lemma 6.1 Picking {- = vd/(KH), 1/d
and À
d
B²,
by Theorem C. we know that 1 = O(dvK K + df) on event 400
By
Theorem 12 we have
H log |8| A|
Ka 2H
1 -
a
Setting H1/KK, combining the two terms and taking the union bound of event Eic completes the proof.
C.4 PROOF OF THEOREMS 5.3
Proof of Theorem 5.3 The major idea is to cast learning a special MDP with finite S, A and deter- ministic (and known) transition, which can be represented as a complete [Al-way tree, as prediction with expert advice and leverage the asymptotic lower bound (Cesa- Bianchi & Lugosi] [006 Theo- rem 3.7) to manifest a v /HK log |A] or / K log [S] dependence the lower bound. Our two-stage reduction begins with a hard-to-learn MDP M1 with its total reward in each episode bounded by 1. The hard instance (1 A, H, (r%,). P) is purely deterministic, where H is even, i.e., Va E A, 8, E F(s'ss,u) is either 0 or 1. The transition dynamies forms a complete [Al-way tree with each node corresponding to state and each edge directed to leaves corresponding to the transition after an action. Let ST1, m] denote the m-th state (node) in the I-th layer of the tree, VI [H + 1), E [[A["] and let A(I, m, n)] denote the only action (edge) from S(,, m] to STI + 1, (m 1) + n]. VI E [H]. m E [[AA']. n E [|A]]. The agent is forced to start from of = S[L, 1] in every episode k E [K] so it will always end up in leaf state, which is denoted by *H+1 = +1H+1, mu] for some my E [[A| [T To align with prediction with expert advice, we con- strain rf(,,-)= = 0, vh E [H ---1 1] and rk (.,-) E [o, 1], which implies the agent can not receive any positive reward until it moving towards the last layer of the MDP (tree). Under these constraints, We allow p* to change arbitrarily across episodes Notice that unlike the common reward design in the hard instance constructions for obtaining information- theorretc lower bounds, which are usually to illustrate the difficulty of parameter estimation, we do not assign specific numeric values to rf in order to expose the impact of the adversarial environment.
H All the |A|# rewards towards leaves in M1. (;)), form an array of experts and any given policy n² = {->(())))>>>>> actually induces probability simplex (of state-reaching after taking the action = over these experts in episode k, which can be represented by a weight vector wok A (I]A)"]) Clearly, Vii (s+) = (wk, rH) where we abuse r to denote the reward vector rh E [o, 1]1-1" towards leaves corresponding to wk. With hindsight, क sup, E VŁ, (of) by which the optimal weight vector w. is induced. In such deterministic MDP, πτ" may not be unique but the corresponding w. can have a restricted support set over the |A| experts, which we re-index as r
[i]. To be more rigorous, let W = suppw,, = fiE [|A] # : ww. [i] # 0]. then obviously
W = argmax; Σ r...). Thus, Vi E W, WK (xt) Ek=1 (w., r Ek=1 r max, Σx T and
Regret K)
Σ (+) Vei
max (E[AAI
Σ
# (wk, rH)
(C.15)
reveals the connection between learning in M1 with its |S] ((AA #) and prediction with expert advice with |A| experts and K rounds. Each expert has its reward bounded in [0, 1]. The first stage of this reduction accounts for the overhead incurred by the adversary under full-information feedback. For any algorithm, there is a well-known asymptotic lower bound for Regret(K):
C.15)
Lemma C.13. For any algorithm and any given nonempty action space A, there exists episodic MDP (with the corresponding A) satisfying Assumption 3.2 such that its expected regret satisfies
Regret(Ki K)
lim #1000 R
lim ((H [A]
2 1,
'Here in the constructions of this proof, we allow the reward function to be time- iim-iinhomogeneuus because although in Assumption 3.1 we set the reward to he hom-eenngenssuss for the simplicity of notation, all the arguments in the proof of regret upper bound can naturally be applicable to the time-inhomogenous case.
24

---

Published as a conference paper at ICLR 2024
if the total reward in each episode is bounded in [0. 1].
Proof of Lemma C.13 See the proof of Cesa-Bianchi & Lugosi 2006 Theorem 3.7) for details. The only work left is to verify Assumption [.2 Let d = 1, = and the deterministic transition kernel IP in M1 be the only basic model in the linear mixture MDP, then we can see that the M1 we construct indeed satisfies Assumption 3.2
We bridge the gap between the reward design in Lemma C.13 and Assumption 3.1 in Theorem 5.3 via the second stage of this reduction.
When H is even, Lemma C.13 also holds for M1 == M1 A, H/2, (P) with H replaced by H/2, where the S, A, and from M1 are restricted to the first H/2 time steps in Mi and Fh ( E [0. and the agent gets reward in all the first H/2 - time steps by construc- tion. We can equivalently transform M1 into a MDP M2 satisfying Assumption 3.1 with plan- ning horizon H as follows. We replace every node S {H/2 + 1, in the (H/2 Ij-th layer of Mi by a (H/2 + 1)-leerr complete Allwway tree, and further assign the transition kernel of Mi to this extended M1. To obtain M2, refined reward design is to assign zero reward for actions (edges) conducted in states in the first H/2 layers and we assign each edge (action) in this sub- tree with reward r H/ (S [H/HH, m] A [2/2, nl) /H E [0, 1/H] for any subtree rooted in S SH/2 + 1, (m - 1) + n). Such construction yields M2 H, (Th), , P), learning in which can similarly be reduced to the standard prediction with expert advice with |A|l//2 experts and K rounds. Therefore, Lemma C.13 also holds for M2 with H replaced by H/2, yet the properties of the reward assignment in My is strictly strong than Assumption 3..Imt that all the actions conducted from states in the same subtree rooted in the (H/2 + 1)-th layer causes the same reward.
Our goal is to claim a lower bound for a (. A, H, {r*), which shares the same S, A, and P with Mj but has its reward assignment generally satisfying Assumption 3.1 i.e. all actions taken from all states cause a reward P% E [0. 1/H]. Since M2 is strictly a special case of MM which implies that the asymptotic lower bound for My. can not be lower than that in Lemma C.13 up to constant factor 22. Also, it is obvious that |S| O [A (H in complete |Al-way tree with H layers.
C.5 PROOF OF THEOREM 5.5
Proof of Theorem 5.5 The proof is almost identical to the proof of Theorem 5,4 in Zhou & Gu 2022). Consider the MDP M' = A, H,,,, .P) constructed in Theorem 5.4, Zhou & Gu (2022).
Now we consider a linear mixture MDP with adversarial reward A' = (S, A, H. (rk [K].
where all the elements except reward function is inherited from M'. Now we detine ,*
((-))
for all & E [K]. It is easy to verify that M satisfy Assumption 3.1 and Assumption 3.2
Since the adversarial reward functions are fixed, we know that the optimal hind-sight policy of M
is the optimal policy of M'. Thus, the adversarial MDP will degenerate to non-adversarial MDP.
The adversarial regret of algorithm on M will also be identical the -oversrrraliall regret on M'. By Theorem 5.4 in Zhou & Gu 2022 we know that when K >> max (3d2, (d 1)/(192 1))2b for any algorithm, there exists a B3-bounded homogeneous linear mixture MDPs with adversarial rewards such that the expected regret EE E[(Regret(K)) is lower bounded by d' K/(663)).
D AUXILIARY LEMMAS
Lemma D.1 (Azuma-Hoeffding inequality, Azuma 1967). Let M > 0 be a constant. Let { } be stochastic process, G; a (x1,-.., xx:) be the oaaleebra of , T., Suppose Elx,/9e-1 0. |. & M almost surely. Then, for any 0 < < 1, we have
Σ x. M 2m
1 8.
Lemma D.2 (Lemma 12, Abbasi- Yadkori et al. 2011).
Suppose A, Raxd are two positive
definite matrices satisfying A > B, then for any Rdd ||x||A I ||x|| (B))
25

---

Published as a conference paper at ICLR 2024
Lemma D.3 (Lemma 11, Zhang al. 2021b). Let M > 0 be constant. Let {a; [ be stochastic process, G. = a (I1,....,24 24) be the o plaggebra of I1,.... 24. Suppose
= O, | - M
and B[x 1] oo almost surely. Then, for any ö, >> O, we have
n
P Σ
2i 2 (lgg(1/))
Σ
B[a719
2M 2 1og(1/0)c 2M 2M log(1/5)
2(1og( 2 n/²)) +166.
Lemma D.4 (Lemma 12, Zhang et al. 2021b). Let A1, 0. A > and
k = max (logg A1, 1). Let d1,..., ax be non-negative real numbers such that ag s
min A1, X2v a; + ai-1 + 2 + )1 for any 1 S i I K. Let ax+1 A1- Then we have a I 22A2 + 6d4 + 422/223.
E INTUITION BEHIND DEFINITION 4.1 AND COMPUTATIONAL ISSUES LINE 3 IN ALGORITHM 2
The second and the third constraints in Definition follows 3.2 and (3.1). which implies that the total probability of every 2/. i... L (s, a, s'), is The last constraint under linear function approximation basicly induces an imagined transition function from (6-1.-). At first glance, is not obvious whether Bregman projection step onto Dr (Line Algorithm is com- putationally efficient. Despite such a projection cannot be formulated as linear program, we can show D to be an intersection of convex sets of explicit linear quadratic forms, which the Breg- man projection onto convex sets problem can be implemented by Dysktra's algorithm efficiently. A detailed discussion is given follows.
First we provide Lemma E.1. For every (s, a, h)) E S x [H), let Zh, denote the vector of occupancy measure 24, (8, a) -) and B., E IR xgl denote the matrix generated by stacking (--1s, a)
closed-form expression of the only implicit constraint in Definition 4.1
i.e.
2h (n a (11)
3,, = 2/ (s,
=
B,aa =
(E.1)
En 0, ((ISS))
where {(1)...., (S)) is indices se of all states, then the only constraint including explicitly 0.,.hh.k in Definition 4.1 is equivalent the following closed-form:
(B 1/2 (zh,e, Iz, Bs. 2x Ok,0))12 S 1ln.,..ol1... Br, v(s,a,h) Ax (E.2)
[H]
Proof. Given (s, a, h) E Sxxx [H, if Σ sE zn (s, a, s') = O, then obviously it satisfy
E.2 Now
we consider the case that Σ es 2n (8, a, > O, then we denote p to be the normalized vector, i.e.
Pa(ss r) = (, a, E 2n (s, a, s'). Then, our new constraint is equivalent to
[| k.0
1/2 ) (p Bs.a 0x.0l2 1 3x
(E.3)
and our original constraint becomes:
0 Ck, s.t., p B
which is equivalent to
1/2 1/2 1/2(( @x. 3 C2 S.t. B.,.Ok. BB,a
Σ
4.0
By definition our confidence set, we know that C₁ means the same as that the following function has solution with norm less than Br. In other word, this means that the solution with the least norm has norm no bigger than 3g.
|
1/2 (0 0x.0)112 - Be, so this
p B 02.0 B. B. 2/,x,
(E.4)
"I this paper, means the i-th state visited in an episode, while s(O) = 1...., |S] is irrelevant to the episodic learning setting and only denotes the indexing order when we refer to the wildcard S in vectorized notation.
26

---

Published as a conference paper at ICLR 2024
Algorithm 4 Dykstra algorithm with Bregman projections
Require: e <> 0, as defined in (4.2), which is strictly convex; N closed convex sets C Ci..... Cn. corresponding to the decomposition in (E.5). C == n,C; * 0; To f- w", where w is defined in line 3 of Algorithm 2 (-
4o = 0 E IR (|AAA serves as auxiliary
4-1
initialization.
1: repeat
2: Fn < (P, V (VI(Tn-1) + (n-N);
3: On <- ( In-N Vf((n);
4:
until || In In TV S
where x is the unknown variable. The least norm solution of (E.4) is (Bs.a E (t (p- B Ox,00,,)).
which should have a norm no bigger than 3R. and thus yields E.3 Therefore, we conclude that the two constraints are equivalent.
By Definition 4.1 and Lemma E. Dr can essentially be reformulated as the joint of several "easier" closed convex sets:
DR 2n()))) RISPIA h [H]
Σ (n(s,,,85) anls', Vh 1h [
=x())))) E RISSPI h E [H]
Σ 21(5,,,5)) = - tt ) a,
(E.5)
(x()))) E Mlspi , E [M]
2x *x())) (
(((())))))) E S/3 IP N
(exx)))SSAx((1]
(B 1/3 (Zh.s. | B, 0n.00)12 Bs, S a 1 }).
Therefore, the best approximation problem w.r.t Bregman Siteergenddsstp... i.e. line 3 in Algorithm 2 can be cast to the projection onto convex sets under Bregman divergence (POCS (Bauschke & Borwein 1996)) problem. Since Dr is the intersection of several hyperplanes, halfspaces, and el- lipsoids onto which (Bregman) projections are hopefully easier to conduct, the Dykstra algorithm with Bregman projections (Censor & Reich 1998). which is verified to be convergent for general closed convex constraints (Bauschke & Lewis 2000), can be utilized.
specialized scheme employing the Dyksira algo- rithm with Bregman projections may invoke the projected gradient descent algorithm to deal with the information projection subproblems onto hyperplanes and halfspaces, both which are blessed with closed-form Euclidean projection formulas (see Lemma E.3) and invoke Frank- Frank-Wolfe Wolfe to ad- dress the information projection subproblems onto ellipsoids, which only requires an efficient imple- mentation of linear optimization problem over the quadratic constraint, in that linear optimization over an ellipsoid has closed-form formula (see Lemma E.4).
For the implementation of line 2 in Algorithm
Remark E.2. The number of variables in line 3 of Algorithm 2 is of order dual problem can not be much easier. The inequality constraints in (E.5) must conducted for each (s, h)) i.e. the unknown transition kernel incurs at least | 77 dual variables in the dual problem.
while its
'In our case, is just information projection Cover 1999
'Rigorously speaking, (E.2) can be relaxed to an elliptcall constraint, because we only concern about Zh.s.a with / lll 0. For (h, 8, whose ||zt.s.all 0. its induced transition kernel Pr, (-|s, a) can be any
eligible unit simplex, which doesn't need to follow 3.4b in Lemma
27

---

Published as a conference paper at ICLR 2024
Lemma E.3. If A R is of full row rank, b E R", R" M0), d E R. the orthogonal
(Euclidean) projections of x E R" onto {x : Ax = b) and fx c x I d} are unique respectively, and have closed-form solutions as follows:
(AA ) (Ax b) = argmin lyy - x|12
X
y:Ay=b
c x
d argmin I - x||2
c
y y=d
Lemma E.4. If A > 0, then linear optimization over an ellipsoid defined by A E S++ and x E R":
y
s.t. Iyy x A-1 1,
has the unique solution with closed-form expression:
Ac
y x Vc Ac
28


Reviews:
[{"review_id": "GYSZjwDCNP", "reviewer": "Reviewer_p5dn", "summary": "This paper studies the online learning problem of horizon-free and linear mixture Markov Decision Processes (MDPs). \nTo the best of my knowledge, this is the first paper that can achieve theoretical guarantees with adversarial losses, that is, the loss function can change arbitrarily from episode to episode. \nTo achieve this result, the authors propose two main techniques: (1) a variance-uncertainty-aware weighted least square estimator and (2) an occupancy measure-based approach for constructing policies. The first technique is widely use for linear mixture MDPs, while the second one is mainly used for adversarial losses. \nCombining these two techniques to establish valid regret guarantees is quite challenging. \nMore importantly, the final regret bound is of the order $O(d\\sqrt{K})$, which is nearly the optimal.", "questions": "1.Is it possible to design policy optimization algorithms for this problem setting? \n2.Is it possible to avoid the usage of occupancy measure (which is not quite efficient in real world).", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. The idea of combining the two techniques is very interesting. It would be great to see such combination to be applied in other (more general) linear MDP settings.  \n2. Though I just skimmed the proof of several lemmas, the results seems to be rigorous proved and mathematically correct.", "weaknesses": "This paper does not have any specific weaknesses.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "gcTyt1r6Js", "reviewer": "Reviewer_tM5p", "summary": "This paper addresses the question of whether the favorable polylogarithmic regret seen in reinforcement learning (RL) with respect to the planning horizon can also be extended to adversarial RL scenarios. The authors introduce the first horizon-independent policy search algorithm, designed to cope with challenges arising from exploration and adversarial reward selection over episodes. The algorithm utilizes a variance-uncertainty-aware weighted least square estimator for the transition kernel and an occupancy measure-based approach for online stochastic policy search.", "questions": "Please see the questions in the weaknesses section above. I am happy to increase my score if there are any misunderstandings.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "Given my limited expertise in the adversarial RL domain, my evaluation focuses exclusively on the technical soundness and clarity of the paper. The manuscript exhibits a commendable standard of articulation. The framing of the problem, underlying assumptions, and derived outcomes are adequately elucidated. Notably, the inclusion of a proof sketch in Section 6 enhances the paper's comprehensibility, serving as a valuable reference point for those seeking deeper insight into the paper's theoretical foundations.", "weaknesses": "The paper makes relatively strong assumptions: linear, finite-state MDPs and full-information feedback. The only novel aspect here is the paper tackles adversarial reward functions rather than fixed or stochastic rewards. But even so, I think that the full-information feedback assumptions greatly alleviate the difficulty of adversarial rewards. To me, the hardness result is more interesting: an unbounded state space will incur regret in $\\Omega(\\sqrt{H})$. Is this result novel in the literature?\n\nI am a bit confused about the assumptions about the reward. Firstly, can the rewards be negative? If so, would assumption 3.1 still make sense? Furthermore, is assumption 3.1 equivalent to the bounded rewards assumption, i.e., if rewards are bounded in $[-R, R]$, we can always scale everything by $1/RH$ to satisfy assumption 3.1.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "K9JJNGknVs", "reviewer": "Reviewer_ZMLZ", "summary": "This paper introduces the first algorithm enjoying horizon free bounds for the adversarial linear mixture MDP. The algorithm is based on a careful combination of policy updates step performed with mirror descent steps in the occupancy measures space and an optimistic policy evaluation phase carried out using weighted ridge regression estimators.\n\nAn interesting finding is also a separation between the adversarial and non adversarial case. Indeed, the authors managed to prove an asymptothic lower bounds which shows that either $\\sqrt{H}$ or $\\log S$ must be paid in the regret bound while a $S$ independent horizon free regret upper bound can be obtained in the non adversarial case.", "questions": "I think that it is unclear that $I^k_h$ defined in Appendix C.2 is decreasing. After inspecting the proofs I think that what the authors need is that for any fixed $k$ than $I^k_h$ is decreasing with respect to $h$. Is this correct ?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "I think that the algorithm is original and well explained in the main text.\n\nThe result which entails a $\\log S$ dependence would not be very satisfactory in the function approximation setting but the author nicely shows that either this dependence or a $\\sqrt{H}$ dependence must be suffered.\n\nI also enjoyed the lower bound construction which considers a tabular deterministic MDP and reduces it to an expert problem.\n\nThe proofs look correct to me.", "weaknesses": "There are few clarity omission or missing definition in the submission. Hereafter, I list few of them:\n\n- I think it should be clearer that also homogenous transition dynamics are required for obtaining reward free bounds. Therefore, the Bellman optimality equation at page 3 should not have $h$ in the footnote of the operator $\\mathbb{P}$.\n\n- the value function $\\overline{V_{k,1}}$ is never formally defined in the paper. So it is difficult to understand what it denotes when reading the regret decomposition in equation (6.1).\nIf I understood correctly from the Appendix, each mirror descent iterate $z_k$ induces via the marginals a transition kernel $\\overline{p_{k}}$ and a policy $\\pi_k$. At this point $\\overline{V_{k,1}}$ denotes the initial value of policy $\\pi_k$ in the MDP endowed with reward function $r_k$ and transition dynamics $\\bar{p}_k$. Can the authors confirm that this is correct and if yes add it to their revision ?\n\n- The definition of Regret at page 3 is a bit unclear. Indeed saying that $V^\\star_k$ is the optimal state value function could make the reader believe that $V^\\star_k = \\max_{\\pi} V^{\\pi}_k$, that is the regret we control has the maximum inside the sum. \nHowever, the regret controlled in the paper has a fixed comparator policy which might not be optimal for any of the reward function revealed at each round.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "rQzJSLOfNk", "reviewer": "Reviewer_K64K", "summary": "This paper studies horizon-free RL in adversarial linear mixture MDPs with full-information feedback. This paper proposes an algorithm that employs a variance-aware weighted least square for the transition kernel and an occupancy measure-based method for the online search of a stochastic policy. The authors show the algorithm achieves a regret with polylogarithmic dependence on $H$. Further, this paper provides a lower bound showing the inevitable polylogarithmic dependence on state number $S$.", "questions": "N/A", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The paper is the first work that studies near-optimal horizon-free RL algorithms under adversarial reward and linear function approximation. This progress deserves to be known to the community.\n2. The connection between the value function derived from occupancy measure guided policy updating and the other one derived from backward iteration (Lemma 6.1) is new as far as I know, which may inspire other studies for RL problems.\n3. The paper is clearly written and well-organized. The proofs are technical sound though I don't check the proofs.", "weaknesses": "1. The novelty of this paper may be limited. Most of the analysis follows from that of horizon-free reinforcement learning for linear mixture MDPs with stochastic rewards (Zhou and Gu, 2022). \n2. The occupancy measure-based algorithm is not computationally efficient as the running time has polynomial dependence on the state number $S$ and action number $A$.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (poster)