Policy Optimization via Adv2: Adversarial Learning on Advantage Functions
Authors: Matthieu Jonckheere
Chiara Mignacco
Gilles Stoltz
Venue: Accepted by TMLR ()

Abstract: We revisit the reduction of learning in adversarial Markov decision processes [MDPs] to adversarial learning based on $Q$--values; this reduction has been considered in a number of recent articles as one building block to perform policy optimization. Namely, we first consider and extend this reduction in an ideal setting where an oracle provides value functions: it may involve any adversarial learning strategy (not just exponential weights) and it may be based indifferently on $Q$--values or on advantage functions. We then present two extensions: on the one hand, convergence of the last iterate for a vast class of adversarial learning strategies (again, not just exponential weights), satisfying a property called monotonicity of weights; on the other hand, stronger regret criteria for learning in MDPs, inherited from the stronger regret criteria of adversarial learning called strongly adaptive regret and tracking regret. Third, we demonstrate how adversarial learning, also referred to as aggregation of experts, relates to aggregation (orchestration) of expert policies: we obtain stronger forms of performance guarantees in this setting than existing ones, via yet another, simple reduction. Finally, we discuss the impact of the reduction of learning in adversarial MDPs to adversarial learning in the practical scenarios where transition kernels are unknown and value functions must be learned. In particular, we review the literature and note that many strategies for policy optimization feature a policy-improvement step based on exponential weights with estimated $Q$--values. Our main message is that this step may be replaced by the application of any adversarial learning strategy on estimated $Q$--values or on estimated advantage functions. We leave the empirical evaluation of these twists for future research.

Published in Transactions on Machine Learning Research (05/2025)
Policy Optimization via Adv2: Adversarial Learning on Advantage Functions
Matthieu Jonckheere
matthiens-jnccheeredlaaa..
LAAS, Université de Toulouse, CNRS, Toulouse, Prance
Chiara Mignacco
chiara malanacco Pnanberrsic--arris-sallaa Université Paris-Saclay, CNRS, Inria, Laboratoire de mathématiques d' d'Orsay, 91405, Orsay, France
Gilles Stoltz
Université Paris-Saclay, CNRS, Inria, Laboratoine de mathématiques d' d'Orsay, 91405, Orsay, France
Reviewed on OpenReview: https: // opt.revveeervv.e...ommoo net/ farmm? id= Qyuesg10Ed
Abstract
We revisit the reduction of learning in adversarial Markov decision processes [MDPs] to adversarial learning based on Q values; this reduction has been considered in a nunber of recent articles as one building block to perform policy optimization. Namely, we first con- sider and extend this reduction in an ideal setting where an oracle provides value functions: it may involve any adversarial learning strategy (not just exponential weights) and it may be based indifferently on Q Q-values or on advantage functions. We then present two exten- sions: on the one hand, convergence of the last iterate for a vast class of adversarial learning strategies (again, not just exponential weights), satisfying a property called monotonicity of weights; on the other hand, stronger regret criteria for learning in MDPs, inherited from the stronger regret criteria of adversarial learning called strongly adaptive regret and tracking regret. Third, we demonstrate how adversarial learning, also referred to as aggregation of experts, relates to aggregation (orchestration) of expert policies: we obtain stronger forms of performance guarantees in this setting than existing ones, via yet another, simple re- duction. Finally, we discuss the impact of the reduction of learning in adversarial MDPs to adversarial learning in the iractical scenarios where transition kernels are unknown and value functions must be learned. In particular, we review the literature and note that many strategies for policy optimization fcature poliey-improvement step basod on exponential weights with estimated Q values. Our main message is that this step may be replaced by the application of any adversarial learning strategy on estimated Q-values on estimated advantage functions. We leave the empirical evaluation of these twists for future research.
1 Introduction
In this article, we revisit specific approach in policy optimization for adversarial Markov decision processes [MDss] in the episodic setting, namely, the closed-form design of policies selected over time (which change incrementally) based on estimated value functions. In virtually all previous work, these policies computed via the same adversarral-learning strategy, referred to under possibly different names: exponential weights, weighted majority, Boltzmann reweighting, or online mirror descent, to name a few. It turns out that different adversarial-learnin strategies may be used, which may have important consequences in practice.
Put differently, this article aims to formally establish the mathematical consistency between the study of adversarial MDPs and (plain) adversarial learning, and to effectively bridge these two important areas of learning theory.

---

Published in Transactions on Machine Learning Research (05/2025)
1.1 Brief literature review
Before reviewing in detail our contributions, we first provide a concise overview of the related literature and justify some claims contained in the previous paragraph.
Adversarial MDPs / Reduction to adversarial learning. The setting of adversarial MDPs was introduced by Even-Dar et al. (2009) and Yu et al. (2009). As in the standard episodic setup, the transition kernels dictating the evolution of the states are unknown and constant over time. However, the reward functions vary over time and may be chosen by some adversary; they are possibly revealed at the end of an episode. Both references were also the first ones to introduce reduction of the control of adversarial MDPs to standard adversarial learning (a sctting also called expert prediction; see for an overview thereof). In this article, we will be interested in closed-form policy optimization, and not in approaches relying on so-called occupancy measures (introduced by Ziimin & Neu 2013), which solve a complex convex optimization problem at each episode, without resulting in closed-form expressions for the output policies (see, e.g.. Rosenberg & Mansour 2019).
& Lugosi 2006
Policy optimization. Policy optimization refers to designing policies to be used at each episode, often obtained by sequential incremental updates, and may be opposed to value-based learning in MDPs, which focuses on estimating and improving value functions rather than directly constructing policies. Several approaches were considered in policy optimization, for instance, (natural) policy gradient (Sutton et al.,
2000 Kakade & Langford 2002), and variants like Trust Region Policy Optimization Proximal Policy
Optimization (TRPO and PPO, respectively; see [Schulman el al. 2015 Schulman el al. 2017). We will
rather be interested in the closed-form policy design relying on estimates of valvelue functions. This vein of rescarch includes the works by Shani et al. (2020). Cai et al. (020)) He et al. (2022). Zhao et al. (2023)
Tiapkin et al. (2025) to name & lew representative contributions (see also AAbaasi- Yadkori el. al., 2019
The settings differ in these articles depending, among others, on the feedback on the reward functions (full
monitoring or bandit feedback) and on the structural assumptions, or lack thereof, on the transition kernels.
However, all cited references have one thing in common: they rely on the same adversarial--earning strategy to process the estimated Q-value functions (except Tiapkin et al. 2025 which builds on the present work).
strategy, based exponential weights. This same adversarial- learning strategy is known under different names and relies exponential weights; for instance, Agarwal ct al. (2021] Section 5.3) refers to it as multiplicative weights updates, Abbasi-Yadkori et al. (2019), as the Boltzmann policy Shani et al. (2020) and Zhao et al. (1222)))) as online mirror descent (with a Kullback- Leibler regularization). Cai et al. [2020] and He et al. (2022) do not write any explicit strategy name for the corresponding step of their policy-optimization approach, but refer to the same closed-form update considered by carlier references; they obtain it by resorting some ballow-th-rogguariizdddd leader approach
A single adversarial-leariien
with an entropic regularization (known to lead to exponential weights, see Freund al. 1997
Kivinen &
Warmuth 1999 Audibert, 2009).
Interestingly, this strategy based on exponential weights aligns with the concept of natural policy gradient for non-adversarial MDPs when the policy parametrization is softmax: both approaches involve the same update rule on the weights (this explicit update rule was, for instance, derived in Agarwal et al.) 2021 Scction 5.3, see also Kakade 2001). This specific case, as the intersection of two optimisation paradigms, leads to remarkable theoretical guarantees in non-adversarial MDPs; see, in particular, the recent work by Müller & Montúfar (2024) and references therein.
Two exceptions to the use of the exponential-weight strategy are provided by Even-Dar et al. (2009) and Yu et al. (2009), which resort to a strategy called follow- selow-the-perturee per-trree---lddeer (Kalai & Vempala 2005); but their setting and objectives are somewhat different from those considered in this article and the previous references.
Abbasi- Yadkori al. 2019: even states that "the choice of the Baltzmann policy is not arbitrary", but one of the points of the present article actually show the contrary: many other choices aelversarial-eeamiii strategies are suitable.
2

---

Published in Transactions on Machine Learning Research (05/2025)
Previous reductions of learning in MDPs to adversarial learning. We provide a specific analysis of the strategy based on exponential weights in Section
G obtaining improved regret bounds compared to the analyses provided in the mentioned references. These analyses range from a few-line-long proof performing a direct reduction to adversarial learning in [Shani ct al. (2020) (a proof that we copy in Scction 3.2 but that can be improved in the specific case of exponential weights), to longer proofs (possibly several pages, see, o.g., Zhao et al. 2023 Appendix A.1). The typical proofs are between these two extremes. In particular, to the best of our knowledge, no other proof than the one by [hhani et al. (2020) clearly identifies a reduction, and all other proofs rather mimic and adap the analysis of exponential weights in adversarial learning, in Agarwal et al. [2021] Section 5.3) or Cai et al. (2020). We note that the cited references actually run the exponential-weight strategy on estimated Q values: more details are provided in Section
In a nutshell, among all cited references, Shani et al. (2020) already clearly identified how to reduce learning in MDPs to adversarial learning, but only leveragod this fact for one specific adversarial learning strategy.
1.2 Contributions and outline of this article
In Section
we formally define the setting of episodic adversarial MDPs and state our objective: the minimization of cumulative regret, defined as the sum of the differences between the value functions of the best stationary policy and of the output policies.
2
Section 3 recalls the reduction of learning in MDPs to adversarial learning as clearly stated in the course of a. proof by Shani et al. (2020). We state the reduction in the ideal setting where an oracle provides, at the end each episode, the value functions corresponding to the policy played a restriction that we discuss and mitigale later in Section We essentially replicate the proof by (hani et al. (2020), based on the performance difference lemma, and actually generalize it by considering broad family of possible adversarial learning strategics, not just exponential weights with constant learning rate. For instance, the ML-Prod and ML-Poly strategies (Gaillard et al. 2014 Gaillard et al. 2021 are suitable adversarial-learning strategies that exhibit in general much better empirical performance than exponential weights. Another observation is that the theoretical guarantees hold when adversarial- eeversarial-lerminng -earrnnn strategies are fed with advantage functions instead of Q Q-functions, which constitutes a second possible source of improved empirical performance.
We then discuss three extensions (convergence of the last. iterate, stronger forms of regret, aggregation of policies) and present two twists: special-case analysis for exponential weights with improved bounds, and how to use the general theory developed in practical scenarios where advantage functions must be estimated (in particular due to the transition kernels being unknown).
Extension 1: convergence of the last iterate. In the case where reward functions are constant over time, [ a regret called simple regret, which measures the difference in performance between the best stationary policy and the last policy selected. Agarwal et al. (2021] Section 5.3) controlled this quantity for exponential weights with constant learning rate (in the discounted setting). We show how to extend their argument to a large class of adversarial strategies satisfying a natural property that we call "monotonicity of weights".
Extension 2: Stronger forms of regret. Section 5 shows that the general reduction studied in Section 3
also works for a stronger notion of regret called strongly adaptive regret and consisting of studying the sums of differences in value functions over sub-intervals of time. As a consequence, the so-called tracking regret may also be controlled: thercin, the comparison is made not to the best stationary policy, but to the best sequence of policies with few shifts. To the best of our knowledge, the control of such improved forms of regret for MDPs is an original contribution.
The special case of exponential weights. Section 0 leverages elements from Extensions 1 and 2 to show that when the adversarial learning strategy consists in using exponential weights with a constant learning
TTypical proofs usually consider the analysis of exponential weights based on telescoping Kullback-Lcibler terms (as in Freund Schapire 1999.. but note that shorter analyses exist, egg, based on Hoeffding's lemma (see Cesa- Blanchi &
Lugosi
2006 Section 2.2
3

---

Published in Transactions on Machine Learning Research (05/2025)
rate, the (cumulative) regret may be bounded by the mumber of shifts in the reward sequence. This provides yet another ceneralization of the results of Agarwal et al. (202) Section 5.3). In addition, the proof technique by Agarwal et al. (2021 Section 5.3) seemed highly specific to the discounted setting: we provide instead a treatment for the episodic setting.
Extension 3: Aggregation (orchestration) of expert policies. Adversarial learning is sometimes called prediction with experts (see Cesa-Bianche & Lugosi 2006). Section 7 considers the case where policies selected over time are no longer learned in direct tabular setting, but are obtained by (state-by-state and slage-by-stage) convex combinations of some expert policies. The aim is to mimic the performance of the overall best such convex combination. This methodology, which we call aggregation (or orchestration) of expert policies, is also referred to learning from multiple oracles (which may be understood a specific paradigm in the vast imitation-learning literature); see, for instance, Cheng et al. 2020 and Līu et al. 2023, We show that to address this problem, it suffices to consider expert policies as actions in a lifted MDP and apply all results described earlier in this article. We obtain stronger performance guarantees than in the cited references.
Empirical impacts as future research directions. Section puts into perspective the design of policies studied in this article: in practice, advantage functions are unknown but may be estimated, so that the strategies studied earlier in this article should be run on these estimates. We review the literature of policy optimization to explain how and why the strategies proposed in the literature may be modified: their poliey-improvemmnt step, stated with exponential weights, may in fact rely on many other adversarial- learning strategics. This modification has no impact on the theoretical guarantees but could be impactful on the practical performance. We however leave the assessment of that potential practical impact for future
research.
2 Setting and aims
Notation. We denote by P(X) the set of probability distributions over some set X, either finite or given by an interval of R in the sequel. For an integer n >> 1, let [n] = [l.....n] nn denote the set of the first n integers.
Setting. We consider an H -piposoiiic and (obliviously) adversarial Markov decision process [MDP] with finite state and action spaces S and A, of respective cardinalitics $ and A: each episode t > 1 is of length >> and is governed by transition kernels T = (Th)Re(H-1), where Th : S x A + P(S), and by reward functions R2 = (Re,))eeHH) where Re : S x A + P(o, The transition kernels are constant across episodes, while the reward functions R2 vary between episodes; they may actually be picked by an adversary in an oblivious manner, ie., the entire sequence (Ri))z determined by the adversary before the first episode takes place.
We denote by FLA A > [0, the mean-payoff function associated with Re, ie., (e, a) is the expectation of the distribution Re, (8, a), for each 8 E S and a E A.
A (stationary, or one-shot) policy π (πл)еенн is a sequence of mappings Ta : S - P(A); we denote by ( (s) the probability distribution over actions that the policy uses in stage h and state s. The learner should determine a policy म, at the beginning of each episode > 1, based on the information gained from rounds r < 1; that information includes at least the states obscrvod and actions played therein, as well as the rewards obtained. In some scenarios, additional observations may be performed, which we will explicitly detail; for instance, the learning system may observe, among other things, the mean-payoff functions r- = (rr,))eε[H) at the end of episode r.
At the beginning of each episode 1 > 1, the same initial state 8t,1 = 81 is sel. Then, al each slage h E [H 1], the learning system draws an action orD ~ (x,((((s,)) after which it obtains and observes a stochastic reward drawn independently from ( ar,)), while the environment moves to a new state drawn as st,4+1 [ a,,)). In the final stage, only an action a,h T. (s, drawn, and a reward drawn independently from Re, a (8,,), is obtained and observed. We do not introduce pieces of
1],
4

---

Published in Transactions on Machine Learning Research (05/2025)
Box A: POLICY OPTIMIZATION; FOR DIRECT TABULAR LEARNING
MDP parameters: state space S, action space A, initial state 81 E S, transition kernels T Initialization: The environment picks a sequence (Ri)ez of reward functions
For episodes ....
1. The initial state is set to 8t,1 $1
2. For stages ===....... I...., H:
(a) The learner picks a policy Te, : - P(A)
(b) and draws action dt, TT,a(( (18c,))
3. The learner receives and observes a reward drawn independently from Re,, with conditional expectation (",,, a1,))
4. If h < H 1, the next state st,b+1 ~ Th( (18,,,, (e,6)) ) is drawn
Goal: Minimize the regret RT max
RT. Vi (s1)
notation for the rewards actually obtained as all arguments in this article will be based on value functions, which, by the tower rule, only depend on the mean-payoff functions.
More precisely, by the tower rule, the value function V,,.R. of given stationary policy π (TT))EE(M) episode t and started at stage h (H] equals, for all E ES,
11
R. V Vr (s) = E. Σ res(s)5)))
8n
(1)
where the piece of notation T indicates that actions an and states 8h in the expectation are governed by the policy æ and the transition kernels T, as described above.
2.1 First aim: direct tabular learning
We evaluate the policies n, picked over time in terms of their value functions and are interosted in mimicking the performance of the best stationary policy in hindsight. More precisely, the learning system aims to control
RT max Σ EVVI. (T. (s1) -V," (T....(ss)).
VT >
where the maximum is over all stationary policies т. We write "VT' > 1 to indicate that either the time horizon T unknown or the rogret should be controlled for all time horizons. The regret R involves sum essentially because the reward functions R, evolve over time in a possibly adversarial way; when they are constant over time, then convergence of the last iterate (i..,, of the T' th term in the sum above) may be achieved, see Section 4
The aim described above is called direct tabular learning policies are picked by determining, for each stage h and state s, the entire probability distribution (- The terminology is borrowed from Agarwal
let al. 2021 Section 3.
The setting above is summarized Box A.
Alternative aim in Section 7 The aim described in Box may be difficult to complete when the number A of actions is large. In addition, the learning system may sometimes have some prior information
5

---

Published in Transactions on Machine Learning Research (05/2025)
given by finite set of expert policies among which some policies could perform well (the subsets of these good-performing policies could possibly depend on the state). We therefore introduce an alternative aim in Section / called aggregation (or orchestration) of expert policies, but actually show that resolving this objective equivalent in some sense to the aim described in Box A.
2.2 Additional notation
For later use, we define Q values and advantage functions, and use the same notation as in D to that end. For any pair of stationary policy æ and reward functions R, we define its Q- V-value function at episode E [T]. and started from stage h E [M]. as
2% R.
B Σ )z)())
8h =8, ag
and its advantage function as
h R.
Ex R,, (s).
(3)
We only keep in the notation Vh, Qh, and An the parameters π and R, that vary, and omit the transition kernels T. We use the short-hand notation
R. (s, -) (A, (s, a)) aEA
(4)
to denote the vector of advantages of a stationary policy for given episode t and given stage h.
3 Methodology and core result: adversarial learning on advantage functions
Contributions of this section. We recall how strategies designed to control the regret in the so-colled adversarial setting, i.e., satisfying guarantees as described in Definition | below, may be used to construct policies so as lo control the regrel in lerms of value funclions. This observation was essentially already made in the literature, at least for exponential weights; see, for instance, how Shani et al. (2020, Section 6) handles the quantity colled term (ii) in their proof.
Before formally stating our main result, we briefly recall what the adversarial setting consists in, mostly to set our notation. We assume that the reader is familiar with the fundamental concepts and results of adversarial learning and refer to the monograph by
& Lugosi (2006) for more detailed exposition.
3.1 Reminder on adversarial learning
We provide description where K > 2 refers to the number of options that the learning strategy has (the number of experts with the classic terminology of adversarial learning). In Section 3.2 we will identify this set [K] of options with the set of actions A.
At each round > 1, based on the information collected during past rounds, a learning strategy picks a convex combination Wt (w..1..... wr,k) E P((K]) while an opponent player simultaneously picks, possibly at random, a vector 9: (g..,..., It.k) ) of signed rewards. Both w, and gi are revealed the end of the round. More formally, we mean that a learning strategy sequence yp = ((r))a) of functions yo. ((-11) P ([K]) and that wi = se: ((+))+=)) for > 1. This formula means particular that the initial vector wn = 5 (6) is constant.
Definition 1 (adversarial-learning regret bound). sequential strategy controls the regret in the adversarial setting with rewards bounded by M > 0 if there exists sequence (Br,)Tra of positive numbers with BT.K/7 T + 0 and such that, against all opponent players sequentially picking reward vectors in M, M]
VT > 1,
max K
Bt.k
Wij Ir. & 2M Br,K-
JE(K]

---

Published in Transactions on Machine Learning Research (05/2025)
The optimal orders of magnitude of Br,K VTIn (see Cesa-Bianchi & Lugosi 2006). In Definition the strategy may know M and rely on its value. On the contrary, the number 7 of rounds is unknown and in fact, for the sake of exposition, Definition requires control of the adversarial regret for all T > 1, which imposes a mild restriction.
Two simple examples of strategies abiding by the constraints of Definition | are instances of the potential- based strategies by Cesa-Bianchi & Lugosi (2003). They are defined based on sequence of non-decreasing functions @ R [0, +00); they resort to Wi,k & 1/K and
(-1 UtA = 0, E Ir. -
Ut,6
ΣΣ [=]je]k]
AA 3 2,
We.k
where
WTJ0TJ
(5)
JE[K]
Example Cesa- Bianchi & Lugosi 2003, Section 2) show that the strategy based on the constant polyno- Zin
mial potentials 4; 4 (max (x. 0)) provides the control BT,K- /6T in K for the regret in the adversarial setting.
2002) studied exponential potentials Ft(x)) = exp(næ) with time-varying learn- Example 2. Auer et al.
ing rales Th = (1/M)V (In K)/t. This sequential strategy controls the regret with BT, = VTnn in the adversarial setting.
A third example is of a different, not potential-baset based, nature.
The greedy projection algorithm of Zinkevich (2003) relies on a sequence (Ne)a1 of positive step sizes and sets Wr+1 = proj(w, + 9t) for 3 1, where w1 (./KK and where proj is the conver projection onto P[[K] in the Euclidean norm. For the choices th = (1/M)//1/(K3) this strategy controls the regret in the adversarial setting with BT.K- = V2KT.
Example 3.
Dozens of strategies satisfying the guarantees of Definition I
exist.
3.2 Policy optimization via adversarial learning on advantage functions
This section presents rather standard material and must be read accordingly. Indeod, what follows is a reduction that was essentially known, though it has previously been applied only with exponential weights and on Q- Davalues rather than advantage functions. The proof follows the one by Shani et al. (2020) Section 6) see also Agarwal et al. (2021 proof of Theorem 16) i.c., based on the performance difference lemma.
We present the reduction in the ideal setting, where oracle provides at the end of each episode the value functions of the policy H. and of the reward function R, selected by the learning system and the environment, respectively. (The reward function R2 does not need to directly be revealed, though, but only indirectly through the value functions.) We consider this ideal setting throughout this article, except in Section g where we explain how to leverage in practice the results developed in the ideal setting.
Oracle 1. At the end of each episode 3 1, an oracle provides, for each h E [H) the value functions
2R R. A 10,H VTT - 10,1--+11] ATT.R. SSA -
of the policy n. and of the reward function R2 selected by the learning system and the environment, respec- tively.
For each stage E [H], we fix a sequential strategy Ph. (Pr,)) in the adversarial setting, relying on reward vectors bounded by Mj, H strategics the advantage functions, in stage-by-stage and state-by-state manner, as follows: for all t > 1,
and of dimension K A, i.c., indexed by A. We run these
Wh E [H]. e
Tene ( (-1s) = Pr,t ((AM (s, (s,) 1)
(6)
where we used the notation defined in adversarial learning advantage functions.
We refer to this strategy as (Ph)ne(M)) Adv2, for (Ph)ne(m)

---

Published in Transactions on Machine Learning Research (05/2025)
It constitutes "theoretical" strategy, it relies on the oracle knowledge of the advantage functions- issue that we discuss and mitigate later in Section S The strategy could be run instead on Q Q-values, see Remark [ below.
Theorem 1. In the setting of Section 2 where rewards lie in [0. 11. if. for all h [H], the sequential strategies 9ph control the regret in the adversarial setting (Definition [ by BT, for A dimensional reward vectors bounded by H - h+ 1, then the (Ph))eeMm) Add2 strategy defined in (6) controls the regret as:
VI (s1) ViT..Ri (si) H(H 1)
VT 1,
max
As indicated above, following Shani et al. (0200 Section 6), the (short) proof of Theorem relies on the so-called performance difference lemma, which we recall next. For the sake of completeness, references for this lemma and a proof thereof are provided in Appendix
Lemma 1 (Performance difference lemma). Let pi u. be the distribution of the state Sy of the h' stage, starting from the state 31 in the first stage, following the stationary policy and the transition kernels T. In a MDP with transition kernels T, for all pairs π, nt of stationary policies, for all reward functions R, and for all stages h E [H],
H
Σ TT (s) (V) VI (s) = Σ
Ph
Σ
HW
(s)
Σ aEA
(al() AT R (s.
SES
hs=
In porticular, for h = 1,
"1
ViT (81) - V/ V (81) = Σ
T...T
(8)
Σ
(als) Aw A (s,
h==1xES
acA
Proof of Theorem 1 We fix a stationary policy π throughout the proof and control the regret with respect to this π.
The first part consists of applying the adversarial-learning regret upper bound for each h E [M]. As the rewards take values in [0, I], we have that |A, RR. (s,a) < H| h + 1 for all 7, By the definition of advantage functions (for the equality to 0) and by Definition and the design the (Ph)nE(M) Adv2 strategy (for the upper bound), we have, for all 8 E.
T
T
max Σ REA
R. a)
Σ
Te, A R. (s, < 2(H - h +11 BT,A.
(7)
aEA
The second part consists of applying the performance difference lemma, i.e., Lemma I above with h 1, which guarantees that
H
V R. (51) -iT Ri (81) = Σ
Σ
8..,7 Mh
(3) Σ
(n(ss) R. as)
h=1 SES
aEA
Summing this equality over t and rearranging, we get
T
v R. (s1) - R.T.R.
RR
Σ
Pb
T
Σ
(a|s)
A T.. Re (s,
hm
SES
[=1
H
T
H
T.
A Ri (s,a) < 2 > (H - h+11 1) BIA (8)
Pb
max
A
h=
1 aES
[=1
h=1
2 Br,A
=H(H+1)
where we substituted 7 Here, we crucially used that the weights 1 R. (s) are independent of t as they only depend on the fixed benchmark policy म, on the common transition kernels T, and on the initial state s (identical for all t).
8

---

Published in Transactions on Machine Learning Research (05/2025)
3.3 Comments
In this section, comment and discuss the Adv2 stralegy (6) and its bound.
We first note that the regret bound of Theorem is independent of the size S of the state space; it only depends on the size A the action space, on the number T of episodes, and on the longth H of the episodes. Given that selversarial-eerning strategies have a per-round computationns complexity typically proportional to K (with the notation of Section 3.1p, the per-round computational complexity of the Adv2 strategies (6) are typically proportional to SAH as far the weight updates are concerned. The main computational issue lies in computing (or estimating, see Section [ the advantage functions A A,..R.
Second, for potential-based strategios 5 we note that the original definition
1 of Adv2 and the alternative
definition based on Q values,
((0T (s)-)) 1)sg--))
(9)
lead to the exact strategies. This may be shown by induction, based the fact that for all h E [H] and (s, E S x A, as in (7) for the first equality and due to the definitions of value functions for the second equality,
t-1
[-1
Σ A
Rr
Rr
(s.
Σ
(als( Art A (s, Σ
Ah
RR
(8
aEA
1-1
1-1
and Σ kr
Q
Ryy (s,a) Σ
Σ
T n Q% Qh- (s, = Σ
A
Ag..P
R. (8)
-EA
r=1
V. (s)
For general adversarial-learning strategies, the induced strategies (6) and 9 may differ, though they achieve the same regret guarantces, as detailed by the following remark.
Remark 1. An inspection of the proof of Theorem | shows that it would also work for the strategies of the form 9 Indeed, the incquality therein would be replaced equivalently by
=V
Re (N)
T (s a),
2(11 - BT,A
max aEA
T. R. (s)
Σ
Te.h (als) Q RI
(8, max aEA
A R.
while the rest of the proof would be unaffected. However, using the advantage functions is preferred in practice, as it procides a greater remerical stability, as well as possibly lower variance when the value function are estimated (see Section 5)
4 Extension 1:
Convergence of the last iterate for some adversarial learning strategies
Contributions of this section. We generalize an argument of Agarwal et al. 22021 Section 5.3), which was provided for exponential weights only (in the discounted setting): the aim to control the convergence of R
the last iterate, i.e., upper bound max V (81) V R (s1), when (mean) rewards functions are constant over time.
To do so, we introduce concept of independent interest: monotonicity of weights for adversarial- stralegies.
More precisely, for aaatersarial-learnin strategies yp satisfying this property of monotonicity of weights, and in case reward functions do not vary over time (or even just mean reward functions do not vary over time, see Remark 2 the result of Theorem may be strengthened into a convergence result of the last iterate, rate faster by factor of 1/T compared to the convergence of the cumulative regret Q

---

Published in Transactions on Machine Learning Research (05/2025)
Definition 2 (monotonicity of weights). A sequential strategy v (ft)es1 in the adversarial setting satisfies monotonicily of weights if against all opponent players sequentially picking K K-dimensional reward veclors the conver weights output by are such that
9r =
3 1,
Wi+1k
91.k
Σ JE[K]
3 0,
KE[K]
where we recall the notation (we,))kE = pe(g))..... 9t-11 and ([]+1))) = (t)
The proof Lemma 2 below explains why the property of Definition 2 is termed monotonicity weights, and why is natural property of an adversarial learning strategy: indeed, the property is satisfied soon as weights for components & associated with a good (respectively, bad) reward dt in the previous round increase (respectively, decrease), where good or bad is determined by the sign of what is called the instantaneous regret with respect to component & in round L:
Jr,k Σ JEKK]
Wt.gtt
Lemma 2. The potential-based strategies potential functions D, 4 (like in Example and the greedy projection algorithm (Exomple of Zinkevich 2003) satisfy monotonicity of weights.
5 of Ceso- CesscBiianchi & Lugosi (2033) with constant, non-decreasing
Proof. We start with the potential-base strategies 55 in case of constant, non-decreasing potential function 4 = Q, and use the notation defined therein. For each / 2 1, since is non-decreasing, we have, for all & E [K].
1t Ut
Ut.k Σ
Wi,gHt. 2 0,
thus
(V2-1, v2,k)) Jt.k Σ
We.ghes 20 0
JE[K]
SE[K]
in all cases. Therefore,
Σ KE[K]
Ut+1,6
Jt.k
Σ
Σ kE[K]
2t.k Bt.k
Wiights
=0,
JE[K]
jEIK]
where the equality to 0 and the final result of Definition are obtained, respectively, by normalizing the 12+1, and Ur into W1+1. 1. and Wr,
For the greedy projection algorithm (Example 3) of Zinkevich 2003), we note that by a property of Euclidean projections onto a convex set (here, w++1 is the projection of w, + 7) 9r onto the simplex, and uy also belongs to the simplex), the following Euclidean inner product non-positive:
0 > (we Wh+1, (we + ne 91) - wi+1) lw, w 11 + newwe Wi+1, 9t)
so that (W++1 We, gt) > 0, which is exactly monotonicity of weights.
We are now ready to state our result of convergence of the last iterate, which generalizes an argument, of Agarwal et al. 22021 Section 5.3).
Theorem 2. Assume reward functions do not vary over time and are all equal to some R. If, for all h E [H], the sequential strategies iph satisfy monotonicity of weights (Definition 2) and control the regret in the adversorial setting (Definition) [ by Br. for A d-dimensional reward vectors bounded by 1, then the last iterate of the (ye)ne Adv2 strategy defined
G satisfies
H(H + 1) Br.A
VT > 1,
max V.ah (..R(()) - ( <
T
10

---

Published in Transactions on Machine Learning Research (05/2025)
The bound by Agarwal al. (2021 Section 5.3), where the exponential weights with constant learning rate are considered, corresponds to this theorem but is stated separately in Corollary 2 for reasons that will be made clear in Section 0 As the proof of Theorem is concise, we provide in the main body of this article.
Proof. Given the definition (6) the monotonicity of weights (Definition 2 and the definition advantage functions, we have that, for all > 1, for all E [H] and & ES,
Σ (als) A.. (s.a) > Σ
R (s, 0. (al(s A
AEA
aEA
Therefore, the performance difference lemma, i.e., Lemma 1 above with h = 1, shows that
H
Vi VT (81) - Vy (s1)
(s))
11+1. (T))
Σ
Tt41A(a|s) R (s. 20.
R=
aEA
0
(This is the part of the proof where we crucially use that reward functions do not vary over time.) Thus,
(s1) max R (s1) - Vi (s1) & max ViTh 1st:)(s1)
Σ T V1
1
T
(51) &
H(H + 1) Br.A
T
E=
where we applied Theorem for the final bound.
Remark An inspection of the proof above shows that what actually matters is only that mean reward functions r, (rEA) be conslant over time. Indeed, the value and advantage functions only depend the R2 through the rı; this fact is also illustrated in the proof of the performance difference lemma which only requires identical mewn reward functions, not the identily of reward functions.
5 Extension 2: Stronger forms of regret
Contributions of this section. We push the logic of the reduction of the control of MDPs to adversarial leurning, and leverage stronger forms of regret in adversarial learning. This section thuss presents new regrel criteria for learning MDPs.
Definition 1 considers the simplest definition of adversarial regret. However, several stronger notions of regrets were proposed in the literature. The proof of Theorem [ shows that the vanilla notion of adversarial regret of Definition 1 may be transferred into the vanilla regret (2) in terms of value functions. Actually, this proof may be mimicked to transfer stronger notions of adversarial regret. We illustrate this possibility with two notions of adversarial regrets that replace the comparison to single global policy with local comparisons (strongly adaptive regret) by global comparisons sequences of policies (tracking regret).
5.1 Strongly adaptive regret and tracking regret adversarial learning
We use again the notation for adversarial learning introduced at the beginning of Section 2.1 The first extended notion of regret, called strongly adaptive regret, measures performance simultaneously over each given sub-interval of time with respect to the best component over that sub-interval. It was introduced by Daniely et al. (215),, based on the concept of adaptive regret from Hazan & Seshadhri (2009) itself
based on the work by Littlestone & Warmuth (1994).
Definition 3 (strongly adaptive regret in adversarial learning). sequential strategy controls the strongly adaptive regret in the adversarial setting with rewards bounded by M > if there erist positive numbers BT,K,T, where T 2 and [T], such that, against all opponent players sequentially picking reward veclors in [|
to+--1
1047-1
VT' > 1, VT [T).
max
max KE[K]
Jt.k
Wi It.l
< 2M BT.K.
WE -7+1
t=
t=
JE(K]
11

---

Published in Transactions on Machine Learning Research (05/2025)
BT,K.- and
sup rE[T]
T 00.
It follows from Daniely et al. 2015 Theorem 1) that the strongly adaptive regret can be controlled with bounds KT of order VT up to logarithmic factors.
A closely related notion is the tracking regret, introduced by Herbster & Warmuth (1998) (see also Cesa- Bianchi Lugosi 2006, Chapter 5.2), where the comparison is taken over all time steps but against sequences ki.T (k1, k2 .... kr) with values in [K], and containing most C shifts (i.e., C time steps such that ke o 1)- The tracking regret involves
T
T
Σ
Σ
Σ JE[K]
Kt.ke
Wr 9t.j
There are strong links between strongly adaptive and tracking regret, see Adamskiy al. (2016). In partic- ular, explain, in the context of regret. with value functions, how strongly adaptive regret with KT,K, of order V up to logarithmic factors entails tracking regret of order vCT; see Corollary
5.2 Transfer of strongly adaptive regret bounds
Based on Definition we obtain the following regret bound in terms value functions and policics.
Theorem 3. In the setting of Section 2 where rewards lie in 10, if. for all h E [H], the sequential strategies
9hh control the strongly adaplive regrel in the adversarial selling (Definition 3 by BT for dimensioonl
reward vectors bounded by H h+ + 1, then the (PP))E)H) Adv2 strategy defined in (6) ensures that
1ot--1 Σ
11 E
(vT:R.(s1) t=
Vy V.
(61)
H(H + #1 Br,A.
The proof of Theorem 3 is obtained by direct adaptation of the proof of Theorem 1 which basically consists of considering sums sub-intere aub-intervaas only instead of sums over all time periods. Again, since the proof is concise, we provide it here.
Proof of Theorem We fix stationary policy throughout the proof and control some adaptive regret with respect to this π. By the design (6) of the Adv2 strategy, which operates stage by stage and state by state, we have that for all h [H] and E S, the following holds, by Definition 3 for all T > 1 and 7 E [T].
tot--1
1ot-
max 60 -1+1
max aEA
A
R: (s,a)
Te, (als) A R. (s,
2(H h 1) BI.
aEA
The same application of the performance difference lemma in the proof of Theorem
entails that for all
T > 1, E (T), and to E [T - 1],
to+--1
to+r-1
Σ
R.T. (s1) - (it..
Ph
T
(8) Σ
(alss)
Σ
A
R. (s,
t=
A= 1ES
aeA
t=
H
1o+r-1
Hh
$1.
(s)
max aEA
A T R. (s, < H(H 11H+11 +1) Br.A..
A=
1
xES
t= to
32(1-b++1 BT.A.
Here again, we crucially used that the weights 14 .1. (s) are independent of The claimed bound follows by taking the maximum and over [T + +1.
12

---

Published in Transactions on Machine Learning Research (05/2025)
5.3 Tracking regret bounds
We detail a consequence of the bound of Theorem in terms of tracking regret.
We consider sequences x(1:1) (T<(1, π instead of single stationary policy. We define the number of shifts c(T(1:1) of such sequence as follows:
xe (() of stationary policies as comparison points,
the smallest integer c' such that there exist c' - 1 integers 12...,9 with values in [I'] such that, denoting
71 = and Te+11 = T +1
eie (2....,d++1) WE , }};
(+)) π (
(10)
The tracking regret against sequences x (1:T) of stationary policies with most C shifts is defined as
Σ t=1
VT , Re ((())
Σv Vm..Ro (s1))
max (1:7)) much that (
We fix 1 1CC and a sequence H (1:T) of stationary policies, with at most shifts, occurring at episodes = < T2 E ... E TC. (The inequalities are strict if there are exactly C shifts.) We introduce TC+1 T + and partition time into the C' intervals [Ti; T++1 1), for i E [C]. The values successively taken by the sequence n (1:T) consist of the π(-), where i E [C]. By applying the bound of Theorem 3 on each of the C intervals [T,, T++1 - 1), we obtain the following corollary.
Addv2 Corollary Under the assumptions of Theorem 3 the (ph)ne(M) Adv2 strategy defined in that VT > 1, AC E [T].
6 also ensures
((/T) max (LT)))
VT RR (si)
R((s))
Σ V Re (01) < H(H+1)
max I=n & STeKTCH-T41
BT. BT.AM
In particular, if BT, r & E[T,, K) VT, where K) is logarithmic in T and K, which is a standard bound, then by Jensen's inequality for v.,
C TTe 1-T+1
max 1= STO 1=
Σ
BT BT.A ())
max &
TH+1 <((TK))CCT VCT.
< (Crer1-n)--ar
6
The special case of exponential weights: improved regret bounds
Contributions of this section. The literature (see Section 1.1 essentially focuses on the adversarial learning strategy given by erponential weights with constant learning rate 17. It turns out that this strategy does not satisfy the requirement of Definition because of a tuning issue: the adversarial regret bound is of the form In N/n + mMM/2 (see, e.g.. Cesa-Bianchi Bianchi & Lugossi 2006, Theorem 2.2) and cannot be simulltneeussy optimázed for all values of T. The literature typically assumes that T is known and obtains a VT regret bownd for MDPs by laking 1) of order 1/VT; see, for instance, among many others, CCi et al. (2020) and Shani et al. (2020). A notable exception, in the discounted setting and for constant reward function, can be extracted from the proof of Agarwal et al. [2021] Section 5.3)-they handle convergence of the last iterate but their proof technique also applies to curullativ regret. We extend their result to the episodic setting and show that it is not essential that. the reward functions be constant over time: we provide an upper bound in terms of the numbers of shifts in the sequence of reward functions.
We study in this section the strategy 6 of Scction 3.2 where the adversarial learning strategies are given by the strategy
(5) based on constant exponential potential &. Φ +> exp(1æ)) This strategy takes
13

---

Published in Transactions on Machine Learning Research (05/2025)
the following simple form: for all t 1,
A R. (s,
exp
11
vh E [H), E, Va Va A, Ten(als)
(11)
1-1
Σ
AT.. Re (s,
exp
d'EA
r=1
with the understanding that sum over no term null, L.e., m,,n(a)s) 1/A.
Agarwal et al. (2021] Section 5.3) showed that the strategy above corresponds to the natural policy gradient [PG] strategy based on softmax parametrization. They proposed a direct analysis (in the discounted setting) with reward functions constant over time. We adapt and extend this analysis to (obliviously) adversarial sequences of reward functions. We also claim a more transparent proof scheme, consisting of a suitable adversarial bound (finer than the uniform bounds considered in Definition [ which in this case would be linear in T, as recalled in the introduction of this section) applied to policy learning along the lines of the proof of Theorem [
Our result is stated in terms of the number R of regimes shifts in the sequence R....., Rr of payoff functions. More formally, R is the smallest integer such that there exist R - integers T with values in [T] such that, denoting T = and TR+1 +1,
Vk E R R+ vt E (TK-1...., 1}, R. = R
(12)
(The case R = corresponds to single regime, i.., the reward functions R, are independent of time.)
The proof of Theorem below may be found in Appendix A It is more complex than the proof by Agarwal ct al. [2021 Section 5.3), which could use a simple argument specific to the discounted setting, with discount lactor 7: that distributions over states induced by a starting state 80, a policy, and a transition function, put probability mass at least 1 1-7 on So, no matter the policy and the transition function. See Remark 0 for more details.
Theorem 4. In the setting of Section where rewards lie in 10, 1], the policy learning strategy the regret as
controls
max Σ (VT.R. - ( v. < H + H(H+1)
T
2
where R is the number of regime shifts in the sequence R,,...,, Rr of payoff functions.
The bound of Theorem has a smaller order of magnitude than the one of Theorem which typically of order VT, as soon as the number of regime shifts satisfies R VT. (In general, up T regime shifts may occur.) In particular, the regret upper bound of Theorem is smaller than constant when the reward functions do not vary over time. Of course, as already mentioned at the beginning of Section 3.2 this observation is somewhat secondary in the absence of an oracle for value functions, when value functions have to be estimated and when these estimation errors are the main contributors to the regret bounds; see Section X
By Lemma and (the proof of) Theorem 2
we have the following corollary Theorem 4 in case of a constant sequence of payoff functions. It corresponds to the bound of Aggawal et al. 2021 Section 5.3) with H playing the role of 1/(1 - therein.
Corollary 2. In the setting of Section where rewards lie in [0, 1], if the reward functions do not vary over lime and are all equal to some R, then the last ilerale of the policy learning stralegy
salisfies
H 4l A nT
H(H +1)
max n. - (81)
2T
As Agarwal et al. (2021, Scction 5.3), the bounds obtained in Theorem A and Corollary 2 suggest choosing 77 as large as possible. While this is the choice recommended by theory, practical performance may be affected: in Section recommend to conduct empirical evaluations to investigate this issue.
14

---

Published in Transactions on Machine Learning Research (05/2025)
7 Extension 3:
Aggregation (orchestration) of expert policies
Contributions of this section. Adversarial learning sometimes called prediction with experts (see Resa-Bianche & Lugosi, 2006). We further pursue the idea of the reduction of the control of MDPs to adversarial learning and now rather aggregate eapert policies. The aim is to můmic the performance of the overall best conver combination of expert policies (which is, in particular, better then the performance of the best policy taken in isolation), which corresponds to an aggregation (or orchestration) of eapert policies. This setting was also termed learning from multiple oracles (which may be understood as a specific paradigm literature) by Cheng al. (2020) and Liu el al. (2023). We oblain stronger forms of performance guarontees than in the latter references, see Remark 3 to the standard tabular case for lifted MDP.
the vasl imiitalion-eeure
We do so via some reduction
We return to the considerations of Section 2. and consider finite number K of stationary policies. We denote by 1I = {TI..... n the set of these policies and refer to them as expert policies. Furthermore, for given stage h E [H] we denote by 1I, = [ .... kK,. the set of the corresponding policies.
We combine expert policies over time through state weights p, = (pr,a)neTH) E ([K]) [H]S where Pt.a( [s) E P([K) may be interpreted either as a probability distribution over the policies in π, or as providing convex weights for the aggregation of the policies in I4, More precisely, for each episode > 1, we denole by p.Il = (pn.lln)ne( the stationary policy such that, for all stages h E [M]
PL : SEE - P.. = E (La(()))TTAM (1)) E P(A). kE[K]
(13)
Picking an action a' according to Pt. (T.. amounts to performing a two-stage randomization: first, drawing a policy index ~ (-))(, then drawing ~ TT,a(- This remark is important in the cases where is difficult or computationally complex explicitly write the (g.n(-1s) but where it is easy simulate them.
As indicated above, the set of all possible state-stggedependde weights q corresponds to P((K)) [8]xS We consider the class C(II) of all possible stationary policies defined according to (13
C(II) qلl q ((IK))
and aim to learn a good policy in this class. To do so, the learning strategies pick weights p. E P((K)) [M|x over time and output π. PIII. We will minimize the corresponding regret criterion:
T
VT 2 1,
R max Σ
(vqll.R. (81) - V.P.I. R. (s1)).
Remark 3. To the best of our understanding, the recent contributions by Cheng et al. (020)) and Liu et al. ) mentioned above consider more restrictive setting with constant reward function and, in addition, target a weaker notion of regret, correspording to
max V. II, KE[K]
(81) max I.I.I ( EE[T]
where each ōū collection of State-stggedeeeender weights that are all given by Dirac masses on expert k; i.e., V. R.
Actually, the total regret Ry defined in Section 2.1 may be decomposed into some approximation error, i.c., how good the policies in C(II) are in terms of values, plus the regret with respect to C(II):
Pr max
Re
(.. (81) R.T. (51) max R.
RR (s1) max
V
qIl R. (s1) R4.
approximation error
15

---

Published in Transactions on Machine Learning Research (05/2025)
In this section, we aim to control Ry only and will assume that the approximation error is small due to proper choice of IT. This situation is expected to arise frequently, as explained in the following remark.
Remark 4. Denole by Tt' a slationary policy achieving the mazimum in the defivition of RT- Given that expert policies are combined through seate-stage-eependee weights, the approzimation error defined above is wull as soon as
Ah H], As ESES, S, E
E P((K])
s.t. T.(.1s)
E (k(ss) Tp.()ss)) kE[K]
In particular, it suffices that there exists Jh. [K] such that ( - M Put differently, it suffices that at each slage h E [H] and for each state & E S, one of the expert policies (bul not necessarily always the same) coincides with an optimal policy. This observation motivates the use of expert policies in the cases where finitely many easy-to- aasytto-identijy distributions are candidates to be optimal distributions for each given slage-stale pair (h, 8).
Summary. We provide in Box B summary of the settings and aims considered, here in Section and earlier in Section 2.1 (the left-hand side of Box B corresponds to Box A of Section 2.1
7.1 Equivalence between direct tabular learning and aggregation of expert policies
We explain why any learning scheme minimizing the standard regret Rr induces learning scheme minimizing the regret Ef with respect to finite set II of expert policies, and vice versa. In nutshell, the equivalence stems from considering the indexes k E [K] of expert policies as meta-actions, i.c., actions in a sequence of lifted MDPs.
As a consequence, for the sake of clarity and completeness, we will re-state the counterpart our main result, Theorem in the sctting of policy orchestration: see Section 7.2 For now, we prove the claimed equivalence.
Direct tabular learning aggregation of expert policics. We set K A and take as expert policies the Dirac masses on the arms; more precisely, for each A, and for all h E [H] and E S, we set Ta. (-]s)= = 8., the Dirac mass at a. This defines the expert policy Ag. We consider
A (A. a A} and C(A) (pA, p ((A))
C(A) is the set of all stationary policies, stated in their direct tabular form.
From direct tabular lcarning to aggregation of expert policies. Conversely, we note that aggre-
gation of expert policies in Il amounts to performing direct tabular learning in the following sequence of (lifted) MDPs: the action space is A = [K], the state space S = S, the transition kernels T and the reward functions R, are defined, for all > and h E [H], by
T : k2, ES [K]
Σ
(als) T (s,a)
aEA
and
Re (s,k) [K]
Σ aEA
(a.a(als) Rc.(s,)))
Direct tabular learning on the sequence of lifted MDPs defined above provides policies which correspond to the convex weights discussed above: for all t >> 1, h E [H], and E S, we use (-I) (-,((1 to aggregate expert policies in the original MDP. Denoting by Ry the regret suffered with direct tabular learning in the lifted MDP, we have: Rll = Rr.
Remark 5. In the final part of the proof of Theorem 1 we critically used that the transition kernels T do not depend on time. The expression above for T is indeed independent on time, which would not be the case if the expert policies were evolving over time. This explains why we restricted our attention stationary expert policies.
16

---

Published in Transactions on Machine Learning Research (05/2025)
Box B: POLICY OPTIMIZATION, POSSIBLY BASED ON EXPERT POLICIES
Direct tabular learning (Section 2.1
Aggregation of expert policies (Section
MDP parameters: state space S, action space A, initial state E S; transition kernels T
(No additional parameters)
Set 11 of K expert policies
The environment picks sequence (Ri)131 of reward functions For episodes & = 1,2,...
1. The initial state is set to $t,1 = $1
2. For stages 1,..., ,
(a) The learner picks policy Te, : + P(A)
(a) The learner picks weights PtA E P((K))
(b) and draws an action at Tt (sr,h)
(b) draws Kr ~ ( (st,)); the index of the expert policy,
(c) and draws an action On ~ Thena (sx)
according to expert policy ky,
4. The learner receives and observes a reward drawn independently from (St, ar,)), with conditional expectation Tr,h (St,ns ar,x)
5. If h < H 1, the next state st,h+1 ~ Th (tt, dr,n) is drawn
Goal: Minimize the regret
RT VT.RR. (81) V. (s1)
R max
Vgll.R. (. -VP.IR. (s1)
7.2 Adversarial learning on advantage functions for aggregation of expert policies
The counterpart for aggregation of expert policies of the strategy defined in Section 3.2 is defined as follows, given the equivalence stated above.
For each stage E [H] we fix a sequential strategy ş사 (sP,))es1 in the adversarial setting, relying on reward vectors bounded by M₁, H h and of dimension K.
We run these strategies the advantage functions of the lifted MDPs described above: for all > h [H]. and 8 E S
A (8, .)= R.
(s,,k) (P...R(.ss)))
where
A R.
(8,
Σ
(kn((a)s) A.R.RR (s,a).
(14)
kE[R]]
More preciscly, we run the strategics (Pn)ne(M) in the following stago-by-stage and statc-by-stato manner: for all / 1,
P.((.188 Fr. (AAh (AP..R.. (8, (8)))))))-1)
(15)
17

---

Published in Transactions on Machine Learning Research (05/2025)
We refer to this strategy as Adv2--Agrr for ( adversarial learning advantage functions for aggregation of expert policies.
Theorem immediately entails the following performance guarantee, given the equivalence proved in Sec- tion
Corollary 3.
In the setting of Section 0 where rewards lie in [0. if. for all h [H], the sequential [ by BT.K for K dimensional reward
strategies 9h control the regret in the adversarial setting (Definition vectors bounded by H + 1, then the (Ph)NE(H) ( Aggr strategy defined in 15 over the set II of K expert policies controls the regret with respect to C(IT) as:
AA >1
RT
max
(. - V.P.I. (5)) & H( + Br,
t=1
8 Empirical impacts as future research directions
Contributions of this section. We review in greater detail how the literature resorted or should resort to adversurial learwing stralegies in pructice: value functions are typically not observed and must estimated. These considerutions coll for future empirical research.
This final section relaxes the assumption of oracle providing value functions, stated at the beginning of Sontion 3.2 and first. recalls how the literature (see, e-g-: [Abbasi-Yadue et al. 2019 Shani et al. 2020 Cai
jet al. 2020 He et al. 2022 Zhao et al.) 2023) typically performs the eolicyimproveement step for learning adversarial MDPs: by resorting to the exponential-woight strategy of Section D based on estimated Q-values.
We provide a concrete example in Figure]] D
More precisely, the most popular approach is build optimistic estimates Ø of the true Q value functions Qh: i.e., estimates that upper bound the true values with high probability. The main issue in doing so is that the transition kernels T are unknown; whether the reward functions R2 are fully revealed (full- information feodback) or not (bandit foodback, where only actual rewards are observed) at the end of an episode may be handled (see, among others, Shani et al. 2020p. Also, these optimistic estimates Qh may or may not rely on structural assumptions (e.g., Cai et al., 2020 and He et al. 2022 assume some linear representation of the transition kernels) and are specific to cach article mentioned.
However, what is common these articles, is the way the poliey-improvement step is performed based Yadkori et al. (2019) even states that
these estimated Q values; this way is illustrated in Figure [ AbbasiiYaddkri "the choice of the Boltzmann policy is not arbitrary" in this step (where "Boltzmann policy" is synonym for the exponential-weight strategy).
The point of the present article is exactly to question this common practice and show that other choices are possible (as detailed in Section 8.1), with no impact on the theoretical guarantees proved in these articles (see Section These observations call for future empirical research (see Section 8.3
8.1 Other choices for the policy-improvenne
step typically considered in the literature
As stated above and illustrated in Figure 1 the literature on adversarial MDPs (see, c.g., Abbasi-Yadkori
et al. 2019 Shani et al.] 2020 Cal et al. 2020 He et. al., 2022 Zhao el. al. 2023 typically considers policy-imppii woaproveeen
silcy--ipoovmeentt steps of the form, for some 17 > 0,
4A 12 1, yA E (H), V Va A
(h(3,0))
exp
(als) exp(n Q1
(4114
(16)
Σ (a'(ss)ss) exp(1 Q (s,
Σ exp
Σ (k())a))
d'EA
a'EA
r=1
18

---

Published in Transactions on Machine Learning Research (05/2025)
Strategy by Shani et al. (2020)
Alternative formalations
Algorithm 2 Optimistic POMD for Stochastic MDPs
Require: 1x. æ1 is the uniform policy.
for k 1,.... K do
Rollout a trajectory by acting # Policy Evaluation
ys S, V (5) =0
for vh = H .., do
for vs.a E S A do
ck (s, c
(s, a) by (s. a). Eq. (6.1)
(s) max a a)
=x (s, Ph
end for
for Vs e S do
(s) (s, )), 2 s))
for all (h, E [H] x 8 do
end for end for # Policy Improvement
T (-1s) = P ((-Q7(s, -))
Vh, 8, a E [H] S A do
or, based on estimated advantage functions defined as in Assumption !
[[([)s) Q
k1 11 [a|s) E.. cxppa #B
k+1 (. = pxttin ((-A7(s,)) -)),a)
end for Update counters and empirical model, me, e end for
Th
end for
The strategy considered and studied by Shani et al. 2020). as stated therein (left part): our results focus on considering alternative formulations of the ppproveitpo step, based on other adversarial- learning strategies than exponential weights, and possibly based on estimated advantage functions rather than estimated Q values (right part). Shani al. (2020) considers costs instead of rewards, hence the negative signs appearing when feeding adversarial learning strategies yp designed for rewards.
Figure 1:
We propose alternative formulations, based on advantage functions obtained from the Q values as described by Assumption [ This assumption satisfied as soon as value functions are also obtained by the same convex combinations, which is the case in all references mentioned above, but would not be the case for other approaches, for instance, for Q learning or similar methods that would define (x(s) as max Q (s,
d'EAA
Assumption | also imposes boundedness of the estimated value functions, this is key for the theoretical analysis of performance (and is coherent with the fact that the true value functions are also bounded, by known bounds).
Assumption 1. The estimales Dú are defined based on estimates Q% of Q value functions, using the policy He selected: for all s E S and a E A,
(s) def Σ (allss Q1 (s, and (s, del (
a'EA
In addition, the estimates Qh and AS are bounded, i..,, 0 < Q < Mn and Ab| < Mu for some quantily Ми (typically depending on H).
Formally, we propose replace updates of the form 16 with the updates based on the strategy Adv2 as stated in (6) or its variant based on Q values stated in
1t 1, Vh [H], Vs E S
Te,a sen (AA,(s, ()) 1)
44 1, Vh H
Ws E S,
Te,n (1)s) spc. (107(s, -))=5())
19

---

Published in Transactions on Machine Learning Research (05/2025)
Empirically, updates based estimated advantage functions should perform better.
8.2 Preserved theoretical guarantees with these alternative choices
When the sequential strategies ンp control the regret in the adversarial setting (Definition I by BT.A for A dimensional reward vectors, the same argument as in (7. together with Assumption for the equality 0, shows that the strategics defined above satisty: for all E [H] and s S,
as,
E 1=1
T (al (s, (ss,a) & 2M BT,
aEA 1=1
1EA
thus, for all h E [H] and 8 E S
RT
def
Σ
Hh
T
(s) Σ
nA (a|s)
Σ
(s.
< <M BI,
(17)
h=S
REAA
1=1
Specific arguments (see detail below) then relate the quantity above to the target quantity, stated as
8
RT max
(e..R((s)) - (.T..R((ss))
(a(ass
A Σ t=l
R (s)
(18)
k=1sES
aEA
Typical examples. For instance, in the theoretical analysis by Shani el al. regret Ry decomposed as sum of three terms, where term (ii) therein exactly 17 but terms (i)
Section 6), the total 2020
and (iii) bounded in some specific way.
The same may be mentioned for the other references, where the total regret Ry is also decomposed into three terms, with Rr being one of the three terms: in Cai et al. (2020)) term (i); in He et al. (2022), term T1; in Zhao et al. (2023), the "OMD regret term".
Again, the adversarial-learning strategy (PN)Retm considered all these references is the exponential po- tential with a constant learning rate (see Section (), possibly seen as an instance of online mirror descent, and bounds of typical order V are achieved on the term corresponding to Kg. Thus, considering other adversarial-leaninng strategies, in the forms described in Section 8.I would not hurt the final regret bounds achieved on Rr, as the errors stemming from the control of Ry are the main contributors to the final regret bounds achieved in these articles.
An exception. In general. Rp not equal a sum of differences of value functions. An exception is be found in Tiapkin et al. (2025): they obtain the estimates Q% as the ezacl Q-value functions (obtained by dynamic programming) corresponding to the policies π. to some reward functions R2 (based the actual reward function R, revealed at the end of the episode plus some bonus function), and to some estimated transition kernels T. (that are constant over subintervals of episodes and are only updated from time time). Tiapkin et al. (2025) decompose the total regret in four terms, where term (B) corresponds to Ri.
Note that Tiapkin et al. (2025) refers the present work and is therefore able to present the analysis in a more modular way than many of the references mentioned above (some of them re-dcriving regret guarantees in terms of Q-value functions by mimicking proofs of adversarial regret bounds for exponential weights, reviewed in Section 1.1
8.3 Future research: evaluation of the empirical impacts of these alternative choices
We explained in Scction 8.2 that the modifications proposed in Scction 8.1 for the iolicy-improvement step preserve the theoretical guarantees (essentially because this poliey-impoovement step is at all the main blocking point in the analysis).
20

---

Published in Transactions on Machine Learning Research (05/2025)
Yet, different formulation of this poliey-improvement step may dramatically affect the practical perfor- mance obtained by these strategies. Many adversarial-learning strategies exist, and exponential-weight strategies are often not the best-performing ones. The R package Opera by Gaillard et al. (2021) implements several Saaversariallcaarinng strategies, some of which (for instance, ML-Prod and ML-Poly. introduced by Gaillard el. al. 2014) oflen achieving superior empirical performance compared to exponential weights (see the empirical studies Gaillard 2015).
Therefore, in opinion, an interesting avenue of empirical rescarch would be the following. Consider the experimental designs provided by, create experimental designs corresponding to, the settings of Abbasi- Yadkori ct al. (019)) Shani et al. (2020), Cai et al. (2020). He et al. (2022). Zhao et al. (2023). Compare the performance of the strategies introduced therein (with their original policy-improvemeet steps, based on
exponential weights) to alternative strategies differing only in their policy-ine deliyy--ppovementt steps (based on the pevoosarialllaamiing strategies implemented in the Opera package, used either with estimated Q-values or with estimated advantage functions). Also, for exponential weights, as mentioned after Corollary P would be interesting to the effect of the learning rale y on the empirical performance. We leave these studies for future research.
References
Y. Abbasi-Yadkori, P. Bartlett, K. Bhatia, N. Lazic, C. Szepesvari, and G. Weisz. POLITEX: Regret bounds for policy iteration using expert prediction. In Proceedings of the Thirty- Sixth International Conference on Machine Learning (ICMI,'1)) volume 97 of PMLR, pp. 3692 3692-3702, 2019.
D. Adamskiy, W.K. Koolen, A. Chernov, and V. Vovk. A closer look at adaptive regret. Journal of Machine Learning Research, 17(23):1 21, 2016.
Agarwal, S.M. Kakade, J.D. Lee, and G. Mahajan. On the theory of policy gradient methods: Optimality, approximation, and distribution shift. Journal of Machine Learning Research, 22(98):1-76, 2021.
J.-Y. Audibert. Fast learning rates in statistical inference through aggregation. Annals of Statistics, 37(4): 1591-1646, 2009.
P. Auer, N. Cesa-Bianchi, and C. Gentile. Adaptive and self-confident on-line learning algorithms. Journal of Computer and System Sciences, 64(1):48 75, 2002.
Q Cai, Z. Yang, C. Jin, and Z. Wang. Provably efficient exploration in policy optimization. In Proceedings of the Thirty-Senn Sherth-Seventh pp. 1283 1284, 2020.
Seventh International Conference on Machine Learning (ICML (CM,)20), volume 119 of PMLR,
N. Cesa-Bianchi and G. Lugosi. Potential-based algorithms in on-line prediction and game theory. Machine Learning, 51:239 261, 2003.
N. Cesa-Bianchi and G. Lugosi. Prediction, Learning, and Games. Cambridge University Press, 2006.
C.-A. Cheng, A. Kolobov, and A. Agarwal. Policy improvement via imitation of multiple oracles. In Advances in Neural Information Processing Systems (Neurips'20) volume 33, pp. 5587-5598, 2020.
A. Daniely, A. Gonen, and S. Shalev-Shwartz, Strongly adaptive online learning. In Proceedings of the Therty-Second International Conference on Machine Learning (CCM..15), pp. 1405-1411, 2015.
Steven de Rooij, Tim Erven, Peter D. Grünwald, and Wouter M. Koolen. Follow the leader if you can, hedge if you must. Journal of Machine Learning Research, 15(37):1281 1316, 2014.
E. Even- Dar, S.M. Kakade, and Y. Mansour. Online Markov decision processes. Mathematics of Operations Research, (A(3))726-736 2009.
Y. Freund and R.E. Schapire. Adaptive game playing using multiplicative weights. Games and Economic Behavior, 29(1):79 (00, 1999.
21

---

Published in Transactions on Machine Learning Research (05/2025)
Y. Freund, R.E Schapire, Y. Singer, and M.K. Warmuth. Using and combining predictors that specialize. In Proceedings of the Twenly-Ninlh ACM Symposium Theory of Computing (STOC'97), pp. 334-33 3344-43, 1997.
P. Gaillard. Contributions online robust aggregation: work on the approrimation error and on probabilistic forecasting. Applications to foracasting for eneryy markets. PhD thesis, Université Paris-Sud, 2015. URL https://thesee: wtt..a..eeeieeeeeeeee0000000000.
P. Gaillard, G. Stoltz, and T. van Erven. A second-order bound with excess losses, In Proceedings of the Twentt-Seventt Conference on Learning Theory (COLT'14), volume 35 of Proceedings of Machine Learning Research, pp. 176-196, 2014.
P. Gaillard, Y. Goude, L. Plagne, T. Dubois, and B. Thieurmel. opera: Online Prediction by Expert Aggre- gation, 2021. URL htttp:://cakl projjeect wttppoojet.orgpppeeeeeeeeeeeeeee org/package-opera R. package version 1.2.0.
E. Hazan and C. Seshadhri. Efficient learning algorithms for changing environments. In Proceedings of the Twendy-Sicth Annuul International Conference on Machine Learning (ICML. pp- 393-400, 2009.
J. He, D. Zhou, and Q. Gu. Near-optimal policy optimization algorithms for learning adversarial linear mixture MDPs. In Proceedings of Twendy-Fiit Fifth International Conference Artificial Intelligence and Statistics (AIStots 222), volume 151 of PMLR, pp. 4259-4288 2022.
M. Herbster and M.K. Warmuth. Tracking the best expert. Machine Learning, 32:151 178, 1998.
S. Kakade. A natural policy gradient. In Advances Neural Information Processing Systems, volume 14, pp. 1531-1538, 2001.
S. Kakade and J. Langford. Approximately optimal approximate reinforcement learning. In Proceedings of the Nineteenth International Conference on Machine Learning (ICML '02), pp. 267 274, 2002.
A. Kalai and S. Vempala. Efficient algorithms for online decision problems. Journal of Computer and System Sciences, 21(3):291-307, 2005.
J. Kivinen and M.K. Warmuth. Averaging expert predictions. In Proceedings of the Fourth European Conference on Computational Learning Theory (EuroCOLT'99), pp. 153-167, 1999.
N. Littlestone and M.K. Warmuth. The weighted majority algorithm. Information and Computation, 108: 212-261, 1994.
X. Liu, T. Yoneda, C. Wang, M. Walter, and Y. Chen. Active policy improvement from multiple black-bor oracles. In Proceedings of the Fourtieth International Conference on Machine Learning (ICML '23), volume 202 of PMLR, pp. 223207, 2023.
J. Müller and G. Montáfar. Geometry and convergence of natural policy gradient methods. Information Geometry, 7(1):485 523, 2024.
A. Rosenberg and Y. Mansour. Online convex optimization in adversarial Markov decision processes. In Proceedings of the Shitt International Conference on Machine Learning (ICML'19) volume 97 of PMLR, pp. 5478 5486, 2019.
J. Schulman, S. Levine, P. Abbeel, M. Jordan, and Moritz. Trust region policy optimization. In Proceedings of the Thirty-Firr First International Conference on Machine Learning (ICML 15), pp. 1889-1897, 2015.
J. Schulman, F. Wolski, P. Dhariwal, A. Radford, and O. Klimov. Proximal policy optimization algorithms, 2017. Preprint, arXiv:1707.063477
L. Shani, Y. Efroni, A. Rosenberg, and S. Mannor. Optimistic policy optimization with bandit feedback. In Proceedings of the Phirty-Seventh International Conference on Machine Learning (ICML 200, volume 119 of PMLR, pp. 8604 5604-8613, 2020.
22

---

Published in Transactions on Machine Learning Research (05/2025)
R.S. Sutton, D.A. McAllester, S.P. Singh, and Y. Mansour. Policy gradient methods for reinforcement learning with function approximation. In Advances in Newral Information Processing Systems, volume 13, pp. 1057 1063, 2000.
D. Tiapkin, E. Chzhen, and G. Stoltz. Narrowing the gap between adversarial and stochastic MDPs via policy optimization. In Proceedings of Twenty-Eight International Conference on Artificial Intelligence and Statistics (ATStats 25), volume 258 of PMLR, 2025.
J.Y. Yu, S. Mannor, and N. Shimkin. Markov decision processes with arbitrary reward processes. Mathe- malics of Operalions Research, ((3):737-7551 2009.
C. Zhao, R. Yang, B. Wang, X. Zhang, and S. Li. Learning adversarial low-rank Markov decision processes with unknown transition and full-information feedback. In Advances in Neural Information Processing Systems (Neurips 23), volune 36, pp. 59107 59123, 2023.
A. Zimin and G. Neu. Online learning in episodic Markovian decision processes by relative entropy policy search. In Advances in Newral Information Processing Systems, volume 26, pp. 1583 1591, 2013.
M. Zinkevich. Online convex programming and generalized infinitesimal gradient ascent. In Proceedings of the Twentieth International Conference on Machine Learning (ICML '03), pp.
2003.
A Appendix.
The appendix provides proofs omitted from the main body of the article.
A Proof of Theorem 4 (analysis of NPG with softmax parametrization)
For the convenience of the reader, restate the result to be proved.
Theorem 4. In the selling of Section where rewards lie in [0, 1], the policy learning stralegy the regret as
controls
max Σ
V.T.. -
< Hna + R 2
H(H +1)
where R is the number of regime shifts in the sequence R1, Rr of pasooff functions.
As indicated in Section the proof below is based the analysis of the natural policy gradient [NPG] with softmax parametrization proposed by Agarwal et al. (2021 Section 5.3) in the discounted setting with reward functions constant over time. See Remark (6] for an explanation of why the proof in the discounted setting is significantly simpler than the proof in the episodic setting.
We extend the proof of Agarwal et al. (2021, Section 5.3) to the episodic setting and to (obliviously) adversarial sequences of reward functions. We also claim more transparent proof scheme, consisting of an ad hoe adversarial bound (Lemma 3 which is then applied policy learning along the lines of the proof of Theorem 1
More precisely, the first piece of the proof of Theorem 4 is to replace the uniform regret bounds considered in Definition | with some ad hoc, data-based, bound (of the same flavor as the bounds by de Rooij et al. 2014, Section 2 in terms of so-called mixability gaps). Indeed, the uniform regret bound that could be proved (see, e.g., Cesa-Biancih & Lugosi 2006, Theorem 2.2) for the adversarial strategy Lemma is Br,K In K/n 1e/nn+nn r//88 which not sublincar.
Lemma 3. The strategy 5 based on a constant exponential potential &; = $ x + exp(rxz), i.e. picking weights
1-1
Vt 2 1.
Wr,k
Σ Vt.j
Vi.k
where
VEA = exp
Σ JT.k
JE(K]
23

---

Published in Transactions on Machine Learning Research (05/2025)
with the convention that V1 1 and wi,k sequentially picking reward vectors in TR
1/K, satisfies the following bound: against all opponents
In
K
VT > 1,
max RE(K]
Σ
1. 9t.i
jC[K]
This lemma is proved at the end of this section and now apply it to prove Theorem 4
Proof of Theorem 4
We adapt the proof of Theorem by replacing 7 by the ad hoc bound stemming from
Lemma we obtain:
< In A + ΣΣ
wh E [H], E
A/
A...R.
(s,
R. a). (ts1,(a|s))A]) A7.
(19)
7
t=1 aEA
We fix a comparator policy л. The combination the obtained inequality the performance difference lemma yields
with the application S of
T
H
Vi n R.
(81)
1i Ri
<
Ph
max aEA [=1
A Ri. R (8,a)
1=1
1= SES
H In A
T
Te 1, A A...R. (s,a).
(20)
1]
bounded
We fix E [7] and h E [H] and define new one-shot policy #h (# (*++1, NE(M as follows:
{
Th if < h-1,
# #HLK
THILK
if > h.
As π and #ht1 coincide in the first stages, we have 14 ... (s) = U/ definition of # the definition of the strategy, Lemma 2 and the definition of advantage functions entail that for all & E S and all N > h,
11. (s). addition, the
R (8. Σ th (als) AN
Σ Te-
A R. (8,0)
Σ (alo(a)s) A7 R.. (R, 0.
aEA
aEA
REA
Therefore, the sum marked "to be bounded" in 20 can be controlled as
Σ
1h T.
(8)
(441s((a))) .. (s, = Σ
A
P
(8)
Σ
#h (a)s) A AT, (s
#ES
oEA
#ES
DEA
H
$1. 111T
sh #
1 (a|s) (3)5))17::300 RR.
NW
W=
SES
aEd
Σ T. 1h (s) (v)
Ri (s) Rits. (s))
(21)
#ES
where the final equality (1 follows from the equality of distributions ph:h "T. = Mb holds because π and / coincide in the first h stages) together with an application of the performance difference lemma (Lemma
s1 #
stage h (which
As A and πc+1 coincide in the last h stages, we have V * Ri(()) observation, combined with 21 entails
Vn V. R(())))))))))))))))))( for all s E S. This
Σ
T (als)(((s)) A A..R. (..
(s, < Σ
TT, (s)
(e., ( -V- R.T..(
BEA
24

---

Published in Transactions on Machine Learning Research (05/2025)
and we thus get, after substitution into
20
HIn A
H TT
T (s) - (s)
(81) - V (81)
ΣΣ
Pb
(s)
V/ V
(22)
h=
We obtain telescoping sums on regimes of payofis. More precisely, with the notation 12
vk E 12..... 1+
Σ
V 1
R. (s) (s) Vn m (s) Vn
(s) E H - h 1,
1=
where the upper bound follows from the boundedness of rewards in [0, 1]. Together with 22 we finally obtain
Σ {(vr (T.RR (81) 117 (
In A
ΣΣ
H
7
R+1 -
H
+ RH + +
PA
1ES
k=2
which leads to the claimed regret upper bound after taking the maximum over all policies π
Remark 6. The arguments between 20 and 22 may be bypassed in the discounted selling with discounl factor see Agaaraal et al. (2021, Section 5.3). More precisely, (with obvious notation, for value functions defined in the standard way for discounted rewards, and for constant reward function), for each E S,
20
T A as
T
hA
max aeAA
&
+
Th- (a|s) (s,
17
1=1
(=1
aEA
In A
I + VTTH (3) 1
T (5')
Σ
T (a
7
S'ES
<1/(1-7)
where the first inequality is by Lemma where the non-negalinily is guaranleed by monolonicity of weights (see Lemma () where the second inequality comes from the fact that distributions induced by starting state a given policy, and a given transition function put a probability mass at least 1- on no matter the policy and bransition funclion (this is the properly extremely specific to the discounted selling), where the equality to (s) (*++ (s) is by the performance difference lemma, and where the final equality is by telescoping. The inequality obtained above is the key; the rest of the proof merely consists of yet another (now standard) application of the performance difference lemma:
T
T
Σ 1=1
V=((s))
ΣE
Σ SES
(8) Σ
((aas)
&
Σ n
max aeA t=
Σ
A (s)
1-
t=1
aEAA
EES
Eln A1n///11//21/)
which is the bound claimed by Agarwal et al. (2021
Section 5.3).
We conclude this section with a proof of Lemma 3
Proof of Lemma 3. First, bound "å la Pisier" yields that for all sequences of payoffs go.s possibly signed and unbounded:
1
Ut.k
In
max exp jE(K)
1
tt.
KE
K
77
1 In
Σ exp
17
Σ
gh.
In
K
In
Σ [E|K]
wes exp(1ghs)
17
7
(E(K]
1=1
t=1
25

---

Published in Transactions on Machine Learning Research (05/2025)
where the equality follows by telescoping: indeed, by definition of the weights,
Ut+15
Ut exp(11t.5)
T
T
T K II 1=1
Σ
exp
1
=
JE[K]
K
]E[K]
was exp(ngt5)
Vt.j
Ur.j
JE|K]
jE[R]
Second, by the application of Jensen's inequality to the convex function x + x In
Σ
wey exp((g).)) In Σ
wey exp(nge3)
Σ
whs exp(ngt.)) In In(exp(ng(.)))
JE(K
jE|K]
JE[K]
that is, after rearranging and given the definition of the weights wj,t-1,
In
Wes exp(ngn.)
<
Σ
W 9t.
]E|K]
JE[K]
The claimed bound follows from combining the two inequalities obtained.
B Proof of the performance difference lemma
One of the first references stating the performance difference lemma (in the discounted setting) is Kakade & Langford 2002). Statements (possibly of generalizations) of this lemma for H --episodic MDPs are ubiquitous in the literature (see, e.g., Cai et al. 2020, Lemma 3.2 for simple statement, and (hanni et al. 2020 Lemma for an extension to approximated advantage functions). We state yet another, straightforward, generalization, in terms of advantage and value functions starting a given stage h; this generalization is useful in the proof of Theorem in Appendix A
Lemma 1 (Performance difference lemma). Let ph TT be the distribution of the state sw of the h' stage, starting from the state $1 in the first stage, following the stationary policy and the transition kernels T. In MDP with transition kernels T, for all poirs 't' of stationary policies, for all reward functions R, and for all stages h E [H],
H
ΣNT T
(s) VT
(s)
= Σ
Σ
T.
(8) Σ
Thllals) AT R (s.
Ph
SES
GEA
In particular, for h = 1,
"
ViT.R (s)R V
(s1)
(51)
Σ
T MK
(3) (s)
(als))) Ar (s,
W=
aEA
Proof. We denote by T the probability distribution underlying the Hl episodic MDP (51, a aH) starting $1, drawing actions according to π, and subject the transition kernels T. In particular, by definition, for any function S A R and all H (H),
M1 Σ
(alsss) f(s. a) = B... [f(ss,
SES
aEA
Letting successively be A for h H and using the definition
AW R AT.
QT/ R VTTRR R
Σ
... (s) Σ
(als)) ATT R (s,
TT
Σ
Q
RRss VT .R (S1:
(23)
M=h
AEA
26

---

Published in Transactions on Machine Learning Research (05/2025)
Now, by definition of the Q Q-values, recalling that denotes the mean-payoff functions associated with R, we have, for h' & 1,
Q @h R (s, - (r) - Σ
Thi (,,() VN (s')
(24)
s'ES
By definition the MDP, for any function g:S + -R.
Σ
The (s' Sw,aw) g(s') E... [g
LESS
Thus, letting 8 = sM and a = ag in 24 and taking expectations yields
1 ( (shrs aw)) E...,, [rw aw]] E.....7 [44 (sw+1)]
For h = H, we have QH (s, a) appears in the right-hand side of
(s) As a consequence of the equalities above, a telescoping sum 23
H
R T
(sw,ak) - V/ (sx)))
Lk
(sH +
Σ
V (sw, + W (Sw41))
Σ v
R (sw)
M=A
h'=h
H
R.
The (sw
R [V ((h)]
Finally, the tower rule shows that
H
Σ
rw (shr, aw)
E... [V (sn)
Ji=h
The proof is concluded by collecting all the bounds.
27


Reviews:
[{"review_id": "7Oc0UWPJom", "reviewer": "Reviewer_1AvV", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "This work investigates policy optimization in episodic MDPs, which is related to an interesting avenue of research in theoretical RL. The focus is on adversarially generated reward functions in the full information setting. I personally find such reward models quite relevant in (theoretical) RL but also believe that it could impact the practice in its applied side, too. (The authors did not discuss such things perhaps due to space limitation, which is fine. Nevertheless, I believe providing some brief pointers to such relevance could be useful for general audience.)\n \nThe paper is written very well, admits a clear organization and presentation, and is overall a nice read. It offers a rich literature review, carefully positioning its contributions to the relevant work and citing most relevant papers I am aware of. Also, short contribution summaries at the beginning of various sections appeared quite helpful. I must mention, however, that it lacks an epilogue (e.g., a ‘conclusion’ section) that could sketch some future directions to continue this research. \n\nRegarding technical aspects: the paper revisits policy optimization in adversarial MDPs (in the full information setting), focusing on works that build on adversarial learning strategies. While providing a technical overview of existing work, it does a good a job in identifying and proposing a systematic approach that encompasses a much larger class of strategies. Overall I believe it is a nice contribution although at first sight it may render incremental. The authors propose a number of improvements and extensions to the state-of-the-art which turns out to happen thanks to the modular form of the proposed Adv2 strategy. Especially, introducing and identifying strategies satisfying the weight monocity property is, to me, a novel contribution. \n\nMy major concern regarding the results is that the larger part of the paper assumes that value functions are known, shifting the focus onto tackling the adversarial nature of rewards. Of course, the authors eventually turn to the so-called ``practical case'' where the transition function is unknown (and hence value function) and explain how the regret under this case related to the regret with regards to the value estimates. But then it is assumed the algorithm would work with value estimates instead of true values. Put differently, the preceding sections were written as if there is a “value oracle” and Section 7 tries to account for lacking such an oracle. Arguably, much of technical hurdles in RL algorithms arise due to the complex nature of noise in value estimates (using direct or indirect methods), and the wording of the section sounds to me like an oversimplification of problem. Thus, my concern is that the claims of Section 7 could be perceived quite differently by different readers, and I am afraid the current execution of this very section could be fully misleading to some. \n\nOverall, excluding its Section 7, the paper may be nicely and consistently read while keeping in mind the existence of some “value oracle” throughout. That said, I do not really see what values the results/discussions in Section 7 may bring in, other than interrupting the previous flow. An alternative execution could treat the discussion in Section 7 for warming up future research which could investigate this in further depth.    \n\nAnother major concern is that the introduction and abstract do not make it clear that the paper considers full information setting and (mostly) assumes known values – unless I am missing something. This must be fixed accordingly. \n\nOther comments are listed below: \n\n- Regarding the sentence “the upper bound of Thm. 4 is smaller than a constant when the reward functions do not vary over time” (in p. 12), could you please elaborate whether this is of relevance when value functions must be estimated? \n\n- After Corollary 2, you conclude that $\\eta$ must be as large as possible. However, this could come at some sacrifice in other performance aspects. Is it correct?  \n\n- Some discussions in the proof of Lemma 2 – e.g., on top of p. 20 – are worthwhile to be included in the main text, considering the novelty of “weight monotonicity”. \n\n- p. 3: $r_{h,t}$ is used to denote both the mean reward and realization at stage $h$ of episode $t$. It would be better to avoid such a notation overloading. \n\n- Beginning of Section 3.1: $K$ is not yet introduced.  \n\n- $\\varphi_t: \\mathbb R^{K(t-1)}$ ==> It looks like that something is missing (e.g., a co-domain or range)\n\nPotential Typos/Grammar Mistakes: \n\n- p. 1: by by ==> by \n\n- p. 2 (and elsewhere): policies output ==> It appears to me that \"output policies\" is more accurate.\n\n- p. 2: for instance derived, in ==> for instance, derived in \n\n- p. 6: Euclidean norm ==> the Euclidean norm\n\n- p. 7: relies in ==> Did you mean 'lies in' or 'relies on'\n\n- p. 8: a possibly a lower ==> a possibly lower \n\n- p. 9: Definition 1 regret ==> To me, 'regret' is redundant\n\n- p. 9 (and elsewhere): ... replace ... by ==> replace ... with ---- Of course in the passive form, it would be '[to be] replaced ... by'\n\n- p. 10 (and elsewhere): subintervals ==> sub-interval (to be consistent with earlier uses)\n\n- p. 11: We consider sequences ==> Shouldn't it be sequence? Or did you mean for various $T$?\n\n- p. 12: more complex that ==> ... than \n\n- p. 12: regimes shifts ==> regime shifts \n\n- p. 12: $1\\sqrt{T}$ ==> $1/\\sqrt{T}$\n\n- p. 14: epochs ==> Did you mean 'episodes'?\n\n- p. 20: The calculation above show ==> ... shows", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper studies episodic reinforcement learning in the regret setting in adversarial MDPs, namely episodic MDPs with stochastic transition function but with reward functions that are arbitrary as if they were generated by an oblivious adversary. The paper revisits algorithmic approaches that fall under the umbrella of policy optimization. Such approaches in the literature mostly build on the celebrated exponential weights strategy that rendered efficient to yield order-optimal regret guarantees. Focusing on the full information setting, the paper aims to offer a unified view of the approaches presented in the literature that is presented under the name Adv2. This unification results in, among others, sharper regret guarantees (and convergence of last iterate) in some cases and extending some existing results to the case of more refined regret criteria – such as adaptive regret and tracking regret. The larger part of the paper assumes that value functions are known and focuses on how to tackle the adversarial nature of rewards. Finally, a variant of Adv2 is discussed and analyzed for the case of aggregation strategies.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "See above.", "broader_impact_concerns": "I believe there is no concern associated to the developments and results reported in the paper.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "50yGikr6Kr", "reviewer": "Reviewer_2ihs", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The current version has flaws in several aspects, which I detail in increasing order of importance. \n\n**Clarity: ** The structure of this work is hard to parse. Comparison with related works appears in the introduction, then again in Sec. 7 and others. Background notations and methods are all over. In terms of content, the study needs to be contextualized as soon as possible in the paper (abstract + intro). I cannot figure out the goal of this work, partly because I am unfamiliar with the notion of sequential strategies: How are they different from policy optimization? What is or is not a potential function? Why/when do they provide more practical methods for RL than other tools? Additionally, the way cross references to other works are used makes reading hard: these are often used to replace an explanation. The paper should be more self-contained, with all required notions explicitly described. \n\n**Motivation: ** I do not understand what problem this paper is trying to solve. Given that different notions of regret can be considered, what is a \"good\" criterion for adversarial learning?  What is the gap in previous work that this work tries to fill? \n\n**Novelty: ** I did not thoroughly go through the proofs, but all derivations seem to be based on one trick: take a strategy that depends on advantage functions. From thereon, regret bounds are more or less straightforwardly deduced from previous results (PD lemma). In other words, what are the technical contributions of this work? What are its technical challenges besides estimating the advantage function? On the other hand, I do not see any algorithmic contributions that may be tested on adversarial learning benchmarks.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper studies episodic MDPs where an adversary chooses a reward function at each step and episode. In contrast, transition kernels stay the same across episodes (although they may vary within one episode). \n\nThe authors describe adversarial strategies leading to sublinear regret bounds, then introduce a new sequential strategy based on estimated advantage functions. When the strategy is a Boltzmann distribution weighted by advantage functions, adversarial regret bounds become tighter than previous works. \n\nStronger notions of regret are then analyzed: strongly adaptive and tracking regret. The authors show that in both cases, their advantage-based strategy leads to sublinear regret. \n\nFinally, this notion of adversarial regret is studied in imitation learning, where similar bounds can be deduced from properly defined strategies.", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "No", "audience_explanation": "", "requested_changes": "I encourage the authors to perform a deep review of their work and clarify the following points:\n- what problem does this work solve that previous ones did not\n- what technical novelties are made to solve the aforementioned problem? \n- what are the shortcomings/limitations of the proposed method? \n\nThe authors should also rearrange the sections: one section - one idea. I think this will help in clarifying the authors' intents. \n- Introduction: \n-- Describe the context. What is an adversarial MDP? What is an adversarial learning strategy? How is it different from \"standard\" policy optimization? \n-- Shortly explain what's missing in previous work and why it is important to fill this gap.\n-- Shortly list the contributions (sec. 1.2 is too long). On a high level, what does this work bring? \n\n- Related work: \n-- it should be better distinguished with the introduction, perhaps make it a section on its own. \n\n- Preliminaries: \n-- All notations, methods from previous works, and background concepts should appear in one place. This will greatly help identify the contributions of this work. These are currently spread across Sec. 2, 2.1, 2.2, 3, and 3.1. \n\n- Contributions\n\n- Discussion: Another missing piece of this work is a discussion/conclusion. What is left to be done that this work hasn't addressed? \n\nPlease avoid referring back and forth to other sections if not needed. Explain your idea instead. \n\nNotations are sometimes confusing: \n- the mean payoff is denoted by $r_{t,h}(s,a)$ in Sec 2, §3, whereas in §5, it becomes a random variable $r_{t,h}\\sim\\mathcal{R}_{t}.$\n- Policies are sometimes stationary, sometimes not. In particular, the objective in Eq. 2 is unclear: Why maximize over stationary policies only? If the reward is adversarial and changes over time, can't $R_T$ be negative? Are $\\mathbf{\\pi}$ and $\\mathbf{\\pi}_t$ related? Or is $\\mathbf{\\pi}$ an \"absolute\" policy based on the inherent setup? From eq 3 to 4, why do policies become non-stationary? \n- In Definition 1, why are reward vectors in $[-M,M]^K$ and not in $[0,1]^K$ as suggested by the reward domain definition in Sec 2, §2? \n- In Definition 1, what is $w_t$? How should this bound be interpreted? What is $\\varphi_t$?", "broader_impact_concerns": "n/a", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "IGHgo6mJwO", "reviewer": "Reviewer_YrCU", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Adversarial MDPs are a crucial component of RL theory, and many existing algorithms have leveraged techniques from adversarial learning to address this problem. This work formally establishes the mathematical consistency between adversarial MDPs and adversarial learning, effectively bridging these two important areas of learning theory. Additionally, it incorporates various techniques from adversarial learning to enhance the theoretical performance and applicability of adversarial MDP methods.\n\nI do not see any major shortcomings in this work. However, in existing literature, it is common to compare methods through empirical evaluations. While not strictly necessary, incorporating some experimental validation would further strengthen the impact of the results. That being said, I highly appreciate the contribution this paper makes in bridging adversarial MDPs and adversarial learning, providing a formal and insightful connection between these two important areas of learning theory.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper provides a comprehensive study on reducing learning adversarial Markov decision processes (MDPs) to adversarial learning, emphasizing generality beyond conventional approaches. The authors extend previous work by demonstrating that this reduction is not limited to exponential weights strategies but can accommodate a broad family of adversarial learning methods, including those based on advantage functions rather than Q-values. These extensions enable broader applicability and improved theoretical performance.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Please see the above.", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper studies policy optimization in adversarial MDPs in the full information setting, by reducing to adversarial learning. Reviewers appreciate the greater generality taken by this work, as well as the several improvements and extensions beyond existing literature. On the other hand, the paper does not contain empirical work, which would have offered insights about the technical contributions in reality. Overall, the paper has nice results that are useful and interesting addition to the literature.

While the revised version has made substantial progress in enhancing presentation, the paper still has quite some room for improvement. I’d encourage the authors to take a careful pass and submit a revised version:

* Tighten the language to be less lengthy, remove unnecessary statements, or reword it to elucidate the points you’re making. Eg, “... do not write any explicit name but obtain ...”, “The typical proofs are one-page-long, do not clearly identify a reduction, and consist of ad hoc adaptations of ...”
* Clearer references for easier following. Eg, “Box A in Section 7” is referred to in Section 2 --- maybe consider moving Box A to Section 2, as the reader needs to understand certain parts of it in Sec 2. Another example: it’s unclear what item (ii) refers to in “... handles its term (ii)” (page 5).
Decision: Accept (poster)