Minimax Optimal Adversarial Reinforcement Learning
Authors: Yudan Wang
Kaiyi Ji
Ming Shi
Shaofeng Zou
Venue: ICLR 2026 Poster (2026)
Keywords: episodic MDPs
adversarial RL
minimax-optimal regret bound
Primary area: reinforcement learning

Abstract: Consider episodic Markov decision processes (MDPs) with adversarially chosen transition kernels, where the transition kernel is adversarially chosen at each episode. Prior works have established regret upper bounds of $\widetilde{\mathcal{O}}(\sqrt{T} + C^P)$, where $T$ is the number of episodes and $C^P$ quantifies the degree of adversarial change in the transition dynamics. This regret bound may scale as large as $\mathcal{O}(T)$, leading to a linear regret. This raises a fundamental question: *Can sublinear regret be achieved under fully adversarial transition kernels?*  We answer this question affirmatively. First, we show that the optimal policy for MDPs with adversarial transition kernels must be history-dependent. We then design an algorithm of Adversarial Dynamics Follow-the-Regularized-Leader (AD-FTRL), and prove that it achieves a sublinear regret of $\mathcal{O}(\sqrt{(|\mathcal{S}||\mathcal{A}|)^K T})$, 
where  $K$ is the horizon length, $|\mathcal{S}|$ is the number of states, and $|\mathcal{A}|$ is the number of actions. Such a regret cannot be achieved by simply solving this problem as a contextual bandit. We further construct a hard MDP instance and prove a matching lower bound on the regret, which thereby demonstrates the **minimax optimality** of our algorithm.

Published as a conference paper at ICLR 2026
MINIMAX OPTIMAL ADVERSARIAL REINFORCEMENT LEARNING
Yudan Wang', Kaiyi Ji¹, Ming Shi & Shaofeng Zou'
'Electrical, Computer and Energy Engineering, Arizona State University ?Computer Science and Engineering, University at Buffalo Ellctrical Engineering, University Buffalo
(ywan1644 645, sou]@asu.eduu (kaiyiji, mshi24)ebuffalo..
ABSTRACT
Consider episodic Markov decision processes (MDPs) with adversarially chosen transition kernels, where the transition kernel is adversarially chosen each episode. Prior works have established regret upper bounds of Ö(VT+ CP), where T is the number of episodes and CP quantifies the degree of adversarial change in the transition dynamics. This regret bound may scale as large as OTT), leading a linear regret. This raises fundamental question: Can sublineur regrel be achieved under fully adversarial transition kernels? We answer this question affirmatively. First, show that the optimal policy for MDPs with adversarial transition kernels must be cestory-dependent. We then design an algorithm of Adversarial Dynamics Follow-ther nollow-the-Reguaaee theeReeularized--caaa Leader (AD-FTRL), and prove that it achieves sublinear regret of ((V([8) (()))TT))))))T where K is the horizon length, |8] is the number of states, and |A] is the number of actions. Such regret cannot be achieved by simply solving this problem as contextual bandit. We further construct hard MDP instance and prove matching lower bound on the regret, which thereby demonstrates the minimax optimality of our algorithm.
INTRODUCTION
Reinforcement learning (RL) (Sutton et al. 1998) is general framework for sequential decision- making, where a learner interacts with an unknown environment in order to learn the optimal policy over time. Consider the episodic setting agent and the environment a fixed number K in each episode. At each stage & E {o..... - the learner takes action a according to the current state s or histories h/ (8" a ...,,,. 1 s- )). Then, the learner observe the next state g s++1 which is sampled from a unknown transition kernel P(-|s* a²), and received loss f(s a²). The interaction terminates at the step K, then new episode starts. The goal of RL is to find a policy sequence to minimize the regret, which is defined as the gap between the total loss obtained during learning and under a fixed optimal policy.
example, where the number of interactions between the
Existing works mostly focus on MDPs with fixed transition kernel and loss function, which do not change across episodes (Sutton al. 1998 Auer et al.) |208)] et al.] 2017 Jin et al. (020b). subject to adversarial corruptions.
However, in practice, the environment can be time-varying Recent studies formulate this problem as adversarial MDPs, where loss and/or transition kernels may be chosen adversarially at each episode. One line of research focuses on the case with adversarial loss, where the loss function is adversarially perturbed but the transition kernel is the same across episodes
(Even-Dar et al. 2009 Neu al., 2010 Zimin & Neu 2013 Jin et al. 2020a 2021 Rosenberg & Mansour 2019). When the transition kernel is also adversarially chosen at each episode, the problem quite limited. For this problem, recent works (Jin et al., 2023) Wei et al. 2022) showed regret bounds that scale with a term of C.,, which quantifies the corruption level of the transition kernels. Notably, in the fully adversarial case, CP can be as large as (T"), leading to a linear regret. This raises a fundamental question:
becomes significantly more challenging, and studies on this problem
Can we develop an algorithm for RL with adversarially chosen transition kernels, and prove sublinear regret?

---

Published as a conference paper at ICLR 2026
In this paper, we answer this question affirmatively. Specifically, we develop a learning algorithm. Adversarial Dynamics Follow-the-Regulane Regularized-Leaaeee (AD-FTRL), that operates under bandit feed- back with unknown adversarially chosen transition kernels. We show that it achieves sublinear regret bound of ( [[(|||])) where K is the horizon length, |S] is the number of states, and [A] is the number of actions. Furthermore, we demonstrate that this regret bound is minimax optimal by constructing a matching lower bound, thereby establishing the minimax optimality results for MDPs with adversarially chosen transition kernels.
1.1 CHALLENGES
In standard episodic MDPs with fixed transition kernel, it is proved that there exists a Markov policy that is optimal (Sutton et al., 1998). However, the same may not be true for adversarial MDPs, though some existing works (Jin et al. 202T 2023) consider Markov policies for simplicity of analysis. A simple example can be constructed as follows. Consider the case where the initial state reveals the transition kernel chosen by the adversary; then the optimal policy must be history dependent (i.e., it depends the initial state). Therefore, need to search over the more expressive class of history-dependent policies, which is more challenging to tackle.
Designing algorithms for distory-dependee policies, noting that the history space can be significantly larger than the state space. Moreover, the learner operates with bandit feedback and lacks knowledge of the transition kernels {Pa hetry. which are chosen adversarially and may vary arbitrarily across episodes. Estimating these transitions is infeasible, and even estimating their average P is insufficient, as the optimal policy for P may be far from optimal for the sequence { This mismatch introduces an unavoidable regret penalty, quantified by the CP term in existing analyses (Jin al., 2023 Wei et al. 2022 Chen al. 2021 Lykouris et al. 2021 Wei et al. 2022). To address these challenges, we avoid estimating P altogether and instead propose an approach based on importance sampling and trajectory-level occupancy measures (a type of visitation measure). Furthermore, we carefully design regularization term to ensure a sublinear regret bound, as the occupancy measures are affected by the time-varying transitions a complication that does not arise in settings with adversarial losses but fixed transition kernels (including fixed kernel with corruption).
policies is substantially more difficult than Markov
However, we notice that our bound is still exponential in K, which is less favorable. This also naturally raises another question: Can the regrer of ||) be improved? To answer it and also understand the minimax optimality, we face two major technical challenges. First, in adversarial RL settings, the study of history-dependent policies is still searce. As result, the lack of structural understanding of such policies makes it particularly difficult to construct an appropriate hard MDP instance for minimax lower bound derivation. Second, deriving tighter lower bound requires reducing the regret minimization problem to a composite hypothesis testing problem- a necessity imposed by the adversarial nature of the transition dynamics. This reduction forms the core of our technical contribution. However, unlike binary or multi-hypothesi. testing scenarios commonly studied in standard RL, composite hypothesis testing and its corresponding regret analysis present significantly greater challenges, is widely acknowledged.
1.2 CONTRIBUTIONS
1. Characterization of the Optimal Policy. We first prove that the optimal policy that minimizes cumulative loss with adversarially chosen transition kernel must be a history-dependent policy, instead of a Markov one.
2. Algorithm Design for Adversarial Chosen Transition Kernels. Under the challenging setting of bandit feedback losses and unknown, adversarially chosen transition kernels, we propose a Adversarial Dynamic Follow-the- wewheeeegllrizedd-eeeeeeoee Leader (AD-FTRL) algorithm that updates policy. Moreover, with a carefully designed regularization term, we prove that our algorithm achieves sublinear regret bound of ([(([ without requiring prior knowledge of the transition kernels.
3. Minimax Optimal Regret Bound. We carefully design a hard instance of MDPs with regret lower bound of ([ algorithm, which shows the minimax optimality of our results. Compared to the lower bound presented in (Tian al. 2021), our result is tighter and explicitly shows that the
order, matching the regret upper bound of the AD-FTRL
2

---

Published as a conference paper at ICLR 2026
regret scales with both the state and action space dimensions. This optimal minimax regret bound confirms the fundamental difficulty of the problem and the minimax optimality of our algorithm. In our proof, we introduce time-varying transitions using information-theereti tools from composite hypothesis testing. Our newly constructed hand instance of MDPs and accompanying analysis framework provide a unified and complete solution for the minimax optimal regret bound of adversarial RL.
analytical approach for handling adversarial or
1.3 RELATED WORKS
Firstly, we introduce the work for the regret against fixed optimal policy among the total episodes. For the case with adversarial loss functions but a fixed transition kernel,
Upper Bound Analysis.
adversarial RI. has been widely studied in previous works (Even-Dar et al., 2009 Zimin & Neul 2013
Neu et al. 2010 Dick ct 2014 Jin & Luo| 2020 Rosenberg & Mansour 2019]Jin et al. 2020a;
2021 Rosenberg & Mansour 2019 Chen & Luo 2021 Luo et al., 2021 Dann et al., 2023a b).
Luo
Among these works, with bandit feedback of ad adversarially chosen losses and fixed but unknown
transition kernel, the works (Jin et al. 2020a 2021) provide different algorithms obtaining a sublinear
((V(S)]AA()) regret bound, which also holds in fully adversarial losses setting.
However, when the transition kernel each episode is also adversarially chosen, the problem becomes challenging, and related studies are limited. The work (Abbasi Yadkori et al. 2013) provides an algorithm for adversarially chosen but known transition kernels. When the adversarially chosen
transition kernels are unknown, previous works (Jin et al. 2023 Wei et al., [022 Chen et al. 2021
Lykouris et al., 202T, Wei et al. 2022; Deng et al.) 2024) estimate the central/true transition kernel and update the policy based on the estimated one. The best regret upper bound from these works is
@(v|s||AA7 + CP), which performs well when the corruption level is sublinear in T. However, under fully adversarial setting, the corruption level becomes linear in T, ie., C O(T), leading to linear regret bound. In contrast, our method directly estimates the visitation measure to minimize regret.
the regret, and reaches a sublinear Ö( ([(([S) [|S||A)
Finally, we note another line of research on non-stationary reinforcement learning. These works also include different non-stationary measure terms in their dynamic regret bounds, such as the number of switches in the environment (Auer al. 2008; Gajane al. 2018), or variation/cooruption measures Wei & Luo, 2021 Cheung et al.) 2023 Li et al. 2024b a). However, most of them focus on dynamic regret, which evaluates the learner's performance relative to the optimal sequence of policies that may change over time, which are generally not directly comparable to ours.
Recent work has extended adversarial reinforcement learning beyond tabular settings. (Cai et al. 2020 analyzed adversarial rewards under linear function approximation, and (He et al.) (022) achieved near-optimal guarantees for adversarial linear mixture MDPs. More recently, Yee et al. 2024) studied adversarial corruption of the transition kernel under general function approximation, obtaining near-optimal regret bounds. However, these results are not directly comparable to ours.
Lower Bound Analysis. For standard RL with fixed but unknown transition kernel and loss function, Auer et al. (2008) provides a regret lower bound under the average-reward setting. Besides, (Azar et al. (017)) provides minimax optimal regret bound for finite-horizon RL problems. In the episodic RL setting, (Auer et al. 2008) claims a regret lower bound based on average-reward analysis, which is later improved by (Jin et al. 2018). However, neither work (Auer al., 2008 JJin et al. 2018) provides a complete or rigorous proof of the episodic RL problem. Recently, (Domingues ct al. 202I) offers unified and complete proofs for regret lower bounds, establishing that the regret must be at least 22 /(S||A/(T) in the episodic RL. setting.
Under bandit feedback with adversarial losses and an unknown fixed transition kernel, the regret lower bound for vanilla episodic RL is often stated as the lower bound for the adversarial loss setting. as in (Jin et al. 2020a). However, in the setting with adversarial transitions, the regret bound analysis becomes challenging As related setting, Markov game, a lower bound of 2()2 is derived in (Tin et al. 2021). However, it is unclear whether this bound is tight or achievable. Moreover, the bound does not specify the dependence on the size of the state space and/or action space. In our work, we present algorithm and prove that the minimax-optimal regret reaches Ω /(S( (T)
3

---

Published as a conference paper at ICLR 2026
2 PRELIMINARIES
We consider the episodic setring, where learner interacts with a sequence of adversarial episodic MDPs with time-varying transitions and losses, which can represented by the tuple (S,A, K, (Pt) hetr,, (e)))))) here [7] = {1,2,... 2, T).. All MDPs share the same joint state space S and joint action space A. We adopt layered MDP structure and assume, without loss of generality, that S is partitioned into K + disjoint subsets So ......t where S = (s*)) contains the terminal state and no actions are taken; A is partitioned into K disjoint subsets A ...... AK
Transitions are allowed only between consecutive layers. We define the history space at stage & S K as 7* = (#j<cS' Øjcck A²) 8 The environment selects the transition kernels (ET)) and loss functions {le Heer adversarially in advance. given the learner's s algorithm. These sequences remain fixed and unknown to the learner. In each episode f, the learner executes a history-dependent policy Te == K- mj. where oं. H² - ((A). Unlike Markov policies, each TH maps full histories to actions. The learner begins at sf. sets hg = { and at each stage k < K, selects P.(. of af), with updated
of ~ -T/(. 1ef), receives loss (s at) and transitions to it k+1 history + = hū {až, Le(sf af), sf+ 1)
Although the learner's policy is functions are Markovian, consistent with prior works such as (Jin et al. (023). The learner has no prior knowledge of these functions. After each episode, only the losses for visited state-action pairs are revealed (bandit feedback losses), and the transition kernels remain entirely hidden.
the environment's 's transition dynamics and loss
To simplify notation, assume that each layer has a fixed number of states and actions: |S| |8*| |AI = [Ak] for all k < K. Additionally, we define a = null and set the terminal loss as E(s ax) := {(s Then, let = {s} ....................... St K K -a 3 s denote the trajectory generated at episode under transition kernel Pt, loss function 4, and policy æ. Define the trajectory space as C. = (0)=KS) & A,) @ Sk, and the cumulative loss of a trajectory as Σk K
(s*t a²)) Given a history-depender policy æ, the value function is defined as Vi(TT) == (T) = E (T)) Pt, x], which is the expected cumulative loss when executing π in the t-th MDP. The regret against any policy π is then Regr(T) = E E (Ve(T))) - (V(()))(((++)))) Let nt denote optimal policy in the history-dependent policy class that maximizes this regret, i.e., Reg, (T*) = max (x).
(T(T)
For simplicity, we write Reg, == (TT" as shorthand. Therefore, the aim of the algorithm is to minimize the regret Reg, under bandit feedback losses and unknown transition dynamics setting.
WARM-UP: CHALLENGES AND SOLUTIONS UNDER ADVERSARIAL DYNAMICS
Tistory-Dependers Policy Class. In this paper, unlike prior work such as JJin et al. 2023 we update policies within the distory-dependee policy class rather than the Markov class. Below, explain the motivation for this design choice. Generally, the Markov policy can be regarded as a special case of history-dependent policies. For standard episodic MDPs with fixed transitions and loss functions, (Sutton et al. 1998) proved that the optimal policy over the history-dependent class is Markovian. Consequently, many subsequent works optimize within the Markov policy set. In the adversarial loss setting with a fixed transition kernel, the problem can be reduced of learning under a sequence of loss functions herrer to optimizing against the average loss ? = # Everry fe, where optimal Markov policy is similar to the standard episodic MDP setting.
However, under adversarially varying transitions, existing studies remain unclear whether the optimal policy remains Markovian. We present a counterexample (Figure I showing that policies can outperform Markov ones. Under the transition sequence (Pi, Pz, P1, P2, P1 ), let:
arg min Markow Markoo policy class
(TT).
This
arg min * Deistory-Depemdenn policy class
((T).
At stage 1, the optimal Markov policy sets Markoo (s² و o) = 0 and achieves V (TTMuttoo)) - In contrast, a distorr-deeendder policy that sets The (s o, a 0. *, = 0, s² = o) 0 and
(s (5 o, a. 0, st o, at 0, s² = o) = 1 achieves ((Tiss) 0.
4

---

Published as a conference paper at ICLR 2026
This demonstrates that the Markov optimal policy can be strictly suboptimal, with non-vanishing gap in expected return. Motivated by this, we restrict our analysis to history-dependent policies throughout the paper.
5"
1(5
5/5 =0)=0
Occupancy Measure. The occupancy measure widely used concept in adversarial RL, which quantifies the visitation frequency over the proba- bility space (e.g., the sate-action pairs). For fixed transition kernel P and stochastic pol- icy x, the state-action occupancy measure pr.= S x A + [0, 1] defines the probability of visiting each (s, a) pair.
5
115
1139
In adversarial reinforcement learning, the goal to minimize the total regret: Regr
S*
119 -)
Ex= V((T:))V((TT) To better illustrate the chal- lenge this setting, we consider a simplified ad- versarial setting where the loss function l is fixed, but the transition kernels {P:) vary adversar- ially. In this case, the regret can be rewritten as:
R
P
Regr Ei= (pr,,, pr..==, f)- Minimizing this regret requires access to the state-action occu- pancy measure pr... . for policy and each tran- sition kernel Pt. However, under adversarial and unknown transitions, estimating these quantities is infeasible: the learner only observes sampled sete-action-nextee
Figure 1: Counterexample: states o, *, A; ac-
tions 0, 1; transitions alternate between P1 and Pz.
triplets (s): af + from interactions with the environment and cannot access the full transition dynamics. Instead, the learner can only estimate the average transition kernel P = Σi= Pt and use it to compute the corresponding occupancy Pp.., which is often treated as proxy for the true dynamics in prior works (Jin et al., 2023).
However, the average occupancy measure P.: + E P = is generally inaccurate and differs from the occupancy under the average transition kernel, i.e., Pa * pp. As a result, for any fixed policy æ, there exists gap introduced by the mismatch across T episodes:
Σ (T)
(p- P).
It further introduces additional corruption term OCCP) in regret bounds. On the other hand, the average occupancy measure 7x may not even correspond to any realizable transition model, further limiting the effectiveness of transition-based estimation approaches in adversarial settings.
To overcome this, we directly estimate the average trajectory occupancy measure, avoiding reliance on transition estimation. Define the trajectory-level occupancy qP. C, [0, 1], where for
T = (s"; aa.....s* K aa sK-1)): QP (T) = Pss II K-1 <(a h*) P(s*+1 $* Unlike prior methods that estimate state-action occupancy via known transitions, operate directly in trajectory space. We estimate (T) using trajectories generated under a behavior policy n, via importance sampling. The following lemma provides an unbiased estimator:
Lemma 3.1 (Trajectory Occupancy via Importance Sampling). Let we E Cr.e be the behavior policy at episode and let (s",a" ..... s a sK+1) Cr, where Cr. is an c-greedy class (i.e., min a (aa h²) 2 e).
Then for any target policy æ:
T(a htt I
Exioqer
Tr,
= (T).
me (e(af h+)))
This gives unbiased estimator for any æ, bypassing the need estimate P.
5

---

Published as a conference paper at ICLR 2026
Given trajectory Tt Pt. we further construct:
क (
htt)
Pn =
-,-r
l = (le(T)) In.rtrre,.
Te (af kt))
rec.
The estimated return at episode / can be written as: Ve(T)) = (i (i) = Pe,, Ce), which is unbiased: [T]] = VT(TT) and Fl Qr.P. Therefore, rather than estimating adversarial transitions, we can directly estimate trajectory occupancy using importance sampling. Next, we will show that this technique avoids the corruption penalty from estimating P. enabling sublinear regret under adversarial dynamics and bandit feedback.
Remark 1. A tempting idea solve adversarial dynamic episodic MDPs is to reduce them bandit problem (considering a nontrivial horizon H > 1). However, in our setting, the transitions are unknown and they cannot be estimated accurately because the averagee occupancy measure differs from the occupancy measure under averaged transitions, i.e. Pn # Pp.. Consequently, the standard mapping from an episodic MDP with known transitions to a bandit model does not apply. Another strictly sub-optimal approach is to treat each policy as an arm, thereby reducing the problem to multi-armed bandit (MAB) setting. However, this leads to extremely large regret because it ignores the intrinsic structure and dependencies within the MDP. A remaining approach treats each length H action sequence, (ag...., QK-1), as a single arm which yields a bandit with |A| arms. However, the best open-loop sequence is strictly suboptimal since it cannot exploit state feedback within the episode. More broadly, actions influence future state distributions, so the contexts observed later depend earlier actions, which violates the contextual bandit assumption that the context law is exogenous. Together, these facts imply that adversarial dynamic episodic MDPs with unknown transitions cannot, in general, be solved by reducing them to bandit problems.
ADVERSARIAL DYNAMICS FTRL ALGORITHM
Under adversarial dynamics, the Follow-the-Ree Regularized-LLadd (FTRL) framework is well- established and powerful method for deriving online learning algorithms, particularly in settings where the environment changes time. In our work, we adapt the FTRL framework to control changes in the trajectory occupancy measure, rather than the conventional state-action occupancy measure used in earlier works. This is essential in our setting, as the occupancy induced by a policy must account for both the policy's 's history dependence and the adversarially changing transition dynamics.
Assuming access to accurate trajectory occupancies P. and trajectory loss function vector 4, the ideal FTRL update rule with regularizer & (((,,),) is given by:
Te = arg min f(x) = Σ(er,, (.) 1 (((r))) T)t
where Tx. = Eiet Jx.P, p. represents the cumulative trajectory occupancy up to time t. However, in the bandit feedback setting with unknown adversarial transitions, we do not have access to the true occupancy loss functions. Instead, we must rely on their estimators: E.er âr, and É.. A naive application of FTRL with these estimates inside the regularizer would lead to high variance and unstable updates. To mitigate this, exploit the structure of the trajectory distribution and carefully rewrite the occupancy and regularization terms. Specifically, we decompose the averaged trajectory occupancy measure as:
(T,( == [
1 1 1 Σ q..P. = - (1,(())
Σ (1) _1,
where we define (T) = -I rtaa
P.(*+1 st a²) and {a+} U
(NF) C T. This decomposition allows to isolate the dependence the policy which appears only in (T),,, while treating (T( as fixed with respect to policy optimization. This structure motivates our design of the regularization term +.
Regularization plays a central role in FTRL-style algorithms, directly influencing the convergence and stability of learning. However, since the distributional term F, : is unknown in our setting,

---

Published as a conference paper at ICLR 2026
define the regularizer using only the volicy-dependent part. Specifically, we set:
Σ [1, (II, TEC.
where a is the trajectory distribution induced by the policy и. This Shannon entropy regularizer encourages stability between successive policies while retaining theoretical tractability. Given this regularizer, we rewrite the FTRL update rule as:
Wi = arg min Σ (mm,P, (.) + (ūr,t))) = arg min OCt TEC,
1
Σ Σ
(+) + 1 (
7/t
1/2
arg min
(II, L.) + (II() [ arg mi,, T.) + - -1,,,1I,, (IIm);
1/t
1/t
where we define
K- II k=
- = P(+))
P. (3t,a)))(7)
(I)
and (+(r)= Eier
This formulation allows to perform efficient updates over policies while avoiding variance inflation from estimated transitions. Importantly, also enables regret analysis under adversarial dynamics, as shown in the subsequent sections.
Algorithm 1 Adversarial Dynamies Follow-the- Rew.eeeegglaiizeeeeeedddde (AD-FTRL) algorithm
Initialize: No, To. TT
2: for 0, 1, T 1 do
3: Observe 8f ~ P (.): Set hi = {s]}
4: for k = O....,
do
5: Take the action: at Tt( ht))
6: Observe the loss le(ot, at), and next state stt1 Pel. | at)
7:
end for
8: Observe the loss (
9: Get Te = as "f. of
k-1 K J.
Ce(stia
10: Update: L. 7+[l (1t
11:
T.+1= T, + Lre
12:
Te+ = arg minnect..
(M.. Pe+i) + 1 Pe+ (IIx) Me41
end for
Building on the discussions, we derived the adversarial dynamic FTRL update rule. Building on this foundation, we now present our AD-FTRL algorithm. The algorithm begins by initializing history-dependent policy mo, an estimated summation estimated trajectory-loss vector To, and the corresponding vector To
At each episode f, the learner follows the policy to select actions, receives a loss, and observes a sampled trajectory. Since the policy n. known, the associated distribution vector 1l, can be computed directly. To update the summation trajectory-loss estimate, use unbiased estimator for L., given by
E.
[Ir=nilEEc.
(2)
II ne (e(a
n+)
where 7 > 0 a small constant added for numerical stability and importance weight clipping. Next, the algorithm updates the cumulative vector Y,41 and computes the policy T++1 according to the adversarial dynamics FTRL rule. To ensure the importance sampling estimator is unbiased, the updated policy #1+1 is required to belong to e-greedy history-dependent policy class Cr,c, where
7

---

Published as a conference paper at ICLR 2026
min (-) 2 c. A typical choice is J. The regularizer used in the update is the Bullback-Leibble divergence,
Σ [T (11, (T))
TEC,
which encourages smooth updates in the trajectory distribution. This procedure is repeated iteratively for each episode.
Remark 2. Compared with prior studies on FTRL-based algorithms, our approach shares the principle of using FTRL to encourage smooth updates in the trajectory distribution. However, the key novelty in our method lies applying the trajectory occupancy measure-rathen than the traditional state-action occupancy measure-to constrain changes in the policy. This shift is crucial in the adversarial setting, where transition dynamics may vary arbitrarily. Moreover, we carefully design the regularization term to avoid dependence on unknown quantities, thereby preventing inflated variance in the regularizer and ensuring stable learning.
THEORETICAL RESULTS: OPTIMAL MINIMAX REGRET BOUND
In this section, we first provide sub-linear upper bound for our AD-FTRL algorithm. Next, we prove that our regret is indeed minimax optimal, i.e., matches the minimax lower bound we will show later.
Theorem 5.1. For AD-FTRL algorithm. under adversarial bandit feedback loss functions and unknown adversarial transitions, set 17 ( &
log(|5]|A|) 7 2(5 it holds that
Regr S Ô (IS]IAA) K/2 VT).
Under the fully adversarial transitions setting, the corruption measure of transitions achieves the (TT) order. Under this setting, the regret bound in previous works (Jin et al. 2023) linear in T (where the regret bound is larger than O(C*) O(T)). But in our AD-FTRL algorithm, when the total episodes T is larger enough, the sub-linear regret can be achieved.
Next. provide the lower bound of this problem under fully unknown adversarial transitions and bandit feedback loss functions.
Theorem 5.2 (Minimax Regret Lower Bound), For any algorithm Alg, there exists an MDPs such that for T > 4([S][A))) log it holds that
MA = AS,, (K,))e,
RegT (Alg. 2
VISS|AB)
(V(ISTAATT)) For 4([S||AA)) log there exists
128
Regr (Alg, M 2 (TT).
When T < |AI log T, the regret upper bound is trivially O(T') due to bounded rewards. When T' 4())||A) log T. the regret lower bound matches the upper bound rate. Consequently, the rate min(T, (I) characterizes the minimax-optimal regret for this adversarial RL setting. This result establishes that, without structural constraints on the transition dynamics, regret of order min A)) is both unavoidable and achievable.
Under related setting of Markov Games, TTia et al. 2021) established lower bound of /2K However, their result does not specify dependence on the state or action space dimensions. In contrast, our result explicitly characterizes them in the complexity of learning under adversarial transition dynamics.
In prior adversarial RL works, importance sampling is often avoided due to its high variance and its negative impact on regret bounds. However, our results demonstrate that, despite these challenges, importance sampling can still achieve the minimax-optimal regret rate in adversarial dynamic RL settings. We acknowledge that our FTRL-based algorithm may have limited applicability in practice, particularly in low-data regimes; however, it is still promising. First, the structure of history-depende policies generalizes across settings, broadening the potential applications of our method. Moreover, with the great advancement of quantum computation and other computational resources, our algorithm has the potential to be applied more widely in practical reinforcement learning scenarios. For more details, the compulational cost is provided in the appendix.
Remark 3.
8

---

Published as a conference paper at ICLR 2026
6 PROOF SKETCH OF MINIMAX LOWER BOUND
In this section, we present the construction of a hard MDPs instance and provide a sketch of the minimax regret lower bound proof. We begin by describing the structure of the hard MDPs.
af
A A
Figure 2: One of Hard MDPs: MDP with transitions P,, here the trajectory
{s", a0.0 st.0, a .... ,..,,k K-100 KK-10 s good]. ((good) = 0, ((bad) = 1, and lis a²) 1 if & K. The state transitions in this trajectory occur with probability I. Other branches model deviations and are included with stochastic transitions (e.g., uniform distribution over next states when actions differ from those in the trajectory).
Let be deetore- policy. We define the set of successful trajectories under I(x)= {T : K good E r, I1 (T) * 0}. From Figure 2 we observe that each trajectory T induces a corresponding MDP with transition kernel P... To construct the minimax regret lower bound, design sequence of adversarial transition kernels. Given a deterministic history-dependent policy [(x'), a corresponding transition kernel P, using the process illustrated in Figure 2 Then, for each episode E [7'] the transition kernel Pt is sampled uniformly from the set {I", 7 [(mr)). The loss function is fixed and follows the structure defined in Figure As result, the MDP instance faced by the algorithm is drawn from the class:
x², we define, for each trajectory
MAlg E {SS,,, ( (Pthert P) P. E [P, : IT [TE((T)))
In this construction, the hard MDPs are designed such that the policy x is optimal for every MDP (S, A, K, Pt, E) in the sequence. Based on this hard instance, an optimal history-dependee must select optimal actions using the observed trajectory history h -1 For histories 1, that prefixes of some r E T(x*), ). choosing the correct action is critical. This reduces the problem to a possible
policy
contextual multi-armed bandit with S
K contexts and |A|] arms each corresponding history and action the last stage-yieldee yielding regret lower bound of order 52( /|S] [A
To match the regret upper bound of our algorithm, however, we aim to prove tighter lower bound of Q (((((I))|))) (T). Achieving this is non non-trivial due to dependencies across different trajectories. For instance, if the algorithm knows that a trajectory belongs to [(m'), can correctly infer parts of the optimal policy, such as T' s9), which introduces dependency between options. To formally establish the tighter lower bound, we reduce the problem to a composite hypothesis testing task. By leveraging Assouad's Lemma and Fano's method, analyze the mutual information between the learner's s observations and the composite hypothesis class (detailed proof is provided in the appendix).
7 CONCLUSION
In this paper, we first analyze the structural properties of the optimal policy under adversarially changing transitions and prove that the optimal policy must be history-dependent, instead of Marko- vian. Motivated by this observation, we introduce the concept of the trajectory occupancy measure and develop the AD-FTRL algorithm, which effectively operates under bandit feedback and adver- sarial transitions. We further show that our algorithm achieves sublinear regret bound of order
o ((()))A))K)). even in the fully adversarial setting, standing for the first sublinear result under

---

Published as a conference paper at ICLR 2026
this setting. Furthermore, construct example and establish matching lower bound, proving our regret is minimax optimal. These results collectively demonstrate both the necessity of handling history dependence and the fundamental difficulty of learning under adversarial transition dynam- ics. Our study provides the first comprehensive understanding RI. with adversarially changing transitions.
ACAKNOWLEDGEMENT
The work of Y. Wang and S. Zou supported in part by DARPA under Agreement No.D25AP0019: and by National Science Foundation under Grants BCCS-2438392(CAREER and CCF-2438429, The work of K. was generously supported by the NSF Career Award under Grant No. 2442418, NSF grants CCF-231 1274 and
10

---

Published as a conference paper at ICLR 2026
REFERENCES
Yasin Abbasi Yadkori, Peter L Bartlett, Varun Kanade, Yevgeny Seldin, and Csaba Szepesvári. Online learning in markov decision processes with adversarially chosen transition probability distributions. volume 26, 2013.
Peter Auer, Thomas Jaksch, and Ronald Ortner. Near-optimal regret bounds for reinforcement learning. In Advances in Neural Information Processing Systems (NIPS), 2008.
Mohammad Gheshlaghi Azar, Ian Osband, and Rémi Munos. Minimax regret bounds for reinforce- ment learning. In International Conference on Machine Learning (ICML), pp. 263-272. PMLR, 2017.
Qi Cai, Zhuoran Yang, Chi Jin, and Zhaoran Wang. Provably efficient exploration in policy opti- mization. In International Conference Machine Learning (ICML), pp. 1283-1294, PMLR. 2020.
Liyu Chen and Haipeng I Luo. Finding the stochastic shortest path with low regret: The adversarial cost and unknown transition case. International Conference on Machine Learning (ICML), pp. 1651-1660. PMLR, 2021.
Yifang Chen, Simon Du, and Kevin Jamieson. Improved corruption-robust algorithms for episodic reinforcement learning. In International Conference Machine Learning (ICML), 2021.
Wang Chi Cheung, David Simchi-Levi, and Ruihao Zhu. Nonstationary reinforcement learning: The blessing of (more) optimism. Management Science, 69(10):5722-5739, 2023.
Chris Dann, Chen- Yu Wei. and Julian Zimmert. A blackbox approach to best of both worlds in bandits and beyond. The Thirty Sixth Annual Conference on Learning Theory (COLT), pp. 5503-5570. PMLR, 2023a.
Christoph Dann, Chen- Yu Wei, and Julian Zimmert. Best of both worlds policy optimization. In International Conference Machine Learning (ICML), pp. 6968-7008. PMLR, 2023b.
Junze Deng, Yuan Cheng, Shaofeng Zou, and Yingbin Liang. Sample complexity characterization for linear contextual mdps. In International Conference on Artificial Intelligence and Statistics, pp. 1693-1701. PMIR, 2024.
Travis Dick, Andras Gyorgy, and Csaba Szepesvari. Online learning in markov decision processes with changing cost sequences. In International Conference on Machine Learning (ICML), pp. 512-520. PMLR, 2014.
Omar Darwiche Domingues, Pierre Ménard, Emilie Kaufmann, and Michal Valko. Episodic rein- forcement learning in finite mdps: Minimax lower bounds revisited. In Algorithmic Learning Theory, pp. 578-598. PMLR, 2021.
Eyal Even-Dan Sham M Kakade, and Yishay Mansour. Online markov decision processes. Mathe- matics of Operations Research, pp. 726-736 2009.
Pratik Gajane, Ronald Ortner, and Peter Auer. sliding-window algorithm for markov decision processes with arbitrarily changing rewards and transitions. In arXiv preprint arXiv: 1805. 10066. 2018.
Jiafan He, Dongruo Zhou, and Quanquan Gu. Near-optimal policy optimization algorithms for learning adversarial linear mixture mdps. In International Conference on Artificial Intelligence and Statistics, pp. 4259 4280. PMLR, 2022.
Chi Jin, Zeyuan Allen-Zhu, Sebastien Bubeck, and Michael I Jordan. Is q-learning provably efficient? Advances in Neural Information Processing Systems (NeurIPS), 31, 2018.
Chi Jin, Tiancheng Jin, Haipeng Luo, Suvrit Sra, and Tiancheng Yu. Learning adversarial markov de- cision processes with bandit feedback and unknown transition. In Proceedings of the International Conference Machine Learning (ICML), 2020a.

---

Published as a conference paper at ICLR 2026
Chi Jin, Zhuoran Yang, Zhaoran Wang, and Michael I Jordan. Provably efficient reinforcement learning with linear function approximation. In Conference on Learning Theory (COLT), pp- 2137-2143. PMLR, 2020b.
Tiancheng Jin and Haipeng Luo. Simultaneously learning stochastic and adversarial episodic mdps with known transition. In Advances in Neural Information Processing Systems (NeurIPS), 2020.
Tiancheng Jin, Lihong Huang, and Haipeng Luo. Best of both worlds: Stochastic and adversarial episodic mdps with unknown transition. In Advances Neural Information Processing Sys- tems (NeurIPS), volume 34, pp. 20491-20502, 2021.
Tiancheng Jin, Junyan Liu, Chloé Rouyer, William Chang, Chen- Yu Wei, and Haipeng Luo. No- regret online reinforcement learning with adversarial losses and transitions. Advances in Neural Information Processing Systems (NeurlPS), 36:38520- 06338520-38885, 2023.
Long-Fei Li, Peng Zhao, and Zhi-Hua Zhou. Dynamic regret of adversarial mdps with unknown transition and linear function approximation. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 38, pp. 13572-13580, 2024a.
Long-Fei Li, Peng Zhao, and Zhi-Hua Zhou. Near-optimal dynamic regret for adversarial linear mixture mdps. In Advances in Neural Information Processing Systems (NeurIPS), volume 37, pp. 55858-55883, 2024b.
Haipeng Luo, Chen- Yu Wei, and Chung- Wei Lee. Policy optimization in adversarial mdps: Improved exploration via dilated bonuses. In Advances in Neural Information Processing Systems (NeurIPS), 2021.
Thodoris Lykouris, Max Simchowitz. Alex Slivkins, and Wen Sun. Corruption-robust exploration in episodic reinforcement learning. In Conference on Learning Theory (COLT)) pp. 3242-3245. PMLR, 2021.
Gergely Neu, Andras Antos, Andras Gyorgy, and Csaba Szepesvari. Online markov decision processes under bandit feedback. In Advances in Neural Information Processing Systems (NIPS), volume 23, pp. 1804-1812, 2010.
Yury Polyanskiy and Yihong Wu. Information theory: From coding to learning. Cambridge university press, 2025.
Aviv Rosenberg and Yishay Mansour. Online convex optimization in adversarial markov decision processes. In Proceedings of the 36th International Conference on Machine Learning (ICML), pp. 5478-5486, 2019.
Richard S Sutton, Andrew G Barto, et al. Reinforcement learning: An introduction, volume 1. MIT press Cambridge, 1998.
Yi Tian, Yuanhao Wang, Tiancheng Yu, and Suvrit Sra. Online learning in unknown markov games. In International Conference on Machine Learning (ICML), pp. 10279-10288. PMLR, 2021.
Chen- Yu Wei and Haipeng Luo. Non-stationary reinforcement learning with linear function approxi- mation. In Advances in Neural Information Processing Systems, volume 34, pp. 22931-2294 2021.
Chen-Vo Yu Wei, Christoph Dann, and Julian Zimmert. A model selection approach for corruption robust reinforcement learning. In Proceedings of the International Conference Machine Learning (ICML), 2022.
Chenlu Ye, Jiafan He, Quanquan Gu, and Tong Zhang. Towards robust model-based reinforcement learning against adversarial corruption. Proceedings of the 41st International Conference on Machine Learning (ICML), pp. 56982-57017, 2024.
Alexander Zimin and Gergely Neu. Online learning in episodic markovian decision processes by relative entropy policy search. In Advances Neural Information Processing Systems (NIPS), volume 26, pp. 5583-1591, 2013.
12

---

Published as a conference paper at ICLR 2026
THE USE OF LARGE LANGUAGE MODELS (LLMS)
We used large language models (LL.Ms) to assist with phrasing, copy-editing, and 1TE formatting. All technical choices, derivations, and results are our own; LLM outputs were reviewed and edited by the authors.
A UPPER BOUND ANALYSIS.
A.1 NOTATION AND PRELIMINARIES.
Firstly, we introduce essential notations used in our analysis.
We begin by reviewing the following definitions for trajectory (i..,......, sK a , sK+1z and histories h* {8", a
}::: ."
(r) == RI, (7) = I Te(a" h:):: the measure of generating trajectory t under history-dependent policy TT:
+ (T) = n. (T) II Ih== Ps(s++1 | sht,""): the measure of transitioning along trajectory under transition kernel Pa:
(((r) = [(()====0) k=o (s* a+): the cumulative loss incurred along trajectory т;
K
( (()): the munsttion-weighted loss for trajectory т.
We also define the normalized trajectory loss estimator:
(x(T)
(T)
(T(
This quantity is used in importance sampling when estimating the trajectory loss without requiring direct knowledge of the transition probabilities.
We now present key lemma used in our analysis:
Lemma A.1 (Trajectory Loss Estimation via Importance Sampling). Let Tr a trajectory sampled under policy and transition kernel Pt, i.e., Q..P, Then, for any E C,,
E Erynqer (T.)) Tn=r] -((T).
This lemma shows that (T) is an unbiased estimator of (G(T) when trajectories are sampled from Pt. Next, we define the cumulative trajectory loss:
(,(T) = Σ (T)
We use bold vector notation to represent trajectory-indexed quantities, such as: l, = ( and likewise for II, L,, Y,, etc. With these notations in place, we now proceed present the regret bound analysis for the proposed algorithm.
A.2 PROOF OF THEOREM 5.1
At the beginning, introduce the high-probability upper bound of our AD-FTRL algorithm. Theorem A.2. For AD-FTRL algorithum, under adversarial bandit feedback loss functions and
$
unknown adversarial transitions, set 1) = [ log((S][AA)) bility at least 1 8, it holds that
7 "( with proba-
T
RegT (TT")
Vi(TT) - -<(x')
log(1/0) 1 1og(1/5) +*KT(1S)AA11* + + + Kn
+ S) K (lo(([S][A(17)
27
2y 7
δ (1og(1/8)((5144) *VT).
13

---

Published as a conference paper at ICLR 2026
Then, will prove the Theorem 5.1 Firstly, review the definitions that
Vi(T)) = Vr, (x) = xITx, Ct)-
Next, denote by estimated value function V/2 (IIx, E.). Then, according Lemma A.1
[=)] (TT, (T Lx) Vi(m);
which means the (T( is unbiased estimator of function Vi(z)) for any policy x.
Next, simplex, we set II, 11x 11, = 1., We do the error decomposition of regret as follows:
Regr E
Vi(TTe) Va(TT)
IE
[1. 11,, Le)
T
T
E
(1l.. 11. Ee)
+E
(II Cs Ei)
[1I C.
Le)
(4)
reg
Error 1 Term:
Firstly, holds that error 1 < O. The Σ = defined is unbiased estimator, and EI (11 Lr
L.)l = 0. Since it holds that
Lx.
E. =
7 + k= Te (a stt
K-1
e, k== (a s4) [Ir=n)ec,
(7 k Te(afi st)) I Te Te(af st)
K
The [ Br=nkre..
+ ly [Tr=n]rec, I ti(at st)
(y + IT =o(a?) s()) Io= Te(at /
phe [.nnlrec. + Ze.
(7 + HI (T))
where inequality follows from that
(7
II mela (t), [T==dlee, - yhn [T==elre,, K=
K-1
(aa st) by [Lr=elrec,
Next, we can bound the error as:
T
?r. Ir=
E
U
C.
[x)
SE
Σ 1=1
[1 Ci - -Zo) - E
+ 1l (T))
1=1
Lh. 11 (T)
Y + 11 (T)
T
= *KT()S)AA)
(5)
1=1
where inequality follows from the fact that by < K.
Error 2 Term:
Then, for term error 2, we introduce the following lemma:
14

---

Published as a conference paper at ICLR 2026
Lemma A.3. For the sequence of vectors a1,...,ay de [0, [0, have with probability at least 8,
T
Σ
Σ ax(T)
- (C)(T)-
- log (
TEC,
From the Lemma A.1 and the fact II(T) I 1 and 2y11(T) 2 for all 11, r, we can easily get that with probability at least 8,
error 2 E
Σ M. Ee c2)
E 27
1
Σ
T
(2711,, Es Le)
log( 27
(6)
Error Reg Term:
Next, we analyze the error reg term. Firstly, we introduce a lemma for the convexity of the trajectory distribution set.
Lemma A.4. The (IIx : Cx} forms a convex
According to the AD-FTRL update rule,
11+ arg min (II,, E.)) + +II,.) = arg min MEC,
(I,, F.) +IIII,).
TEC, 15
Then, set 1 1/;
Tf 7). Denote the Bregman divergence with convex function F, i.e.
Dy(p,g) v) = F()) - F(g) (p 9, FF))). Combined with Lemma A.4 we can get the follows
equation:
1 (IT,
(
Σ 2.) <C
([1+1, Σ
E.) +
1
$ (I[+1)
(II+11 II,, Σ (.)
-II,
1
(ITe.
+ (o,(Tett))
1
17
"
"
a8t+1
( IIi, - L =V..
_ + 1 (l
< (11+11 Σ
Σ.) + (II+++1
1
1
(IT+1, Σ 2.)
+
Φ (I[+1) Diø, (II+
17
Σ.) P (IT+1) (T++1, Ex) + 1 n ([T-1) P141 (IT+11) D Dyo. (T1,11, IT.,,
Σ
11
18111
where the inequality comes from and convex property in Lemma A.4 and the first order optimality condition of [,, i.e. (TI++1 I1, Exse Z, I ( 0. 7
Taking the summation of above equation and we can get that
(I) Σ Σ.) + - (II) < (IT,
Σ Σ.) + TT+ (Il+((
7
<T++1
(
Dr (Il+z)) 11 d. (1((2))))
T
II 11 [1) Σ
Σ
D a. (Ie+1, It).
1=1
1=1
t=l
15

---

Published as a conference paper at ICLR 2026
Here, (II1, Ex<1 [.) = 0. Then, rewrite the error reg term as follows:
T
T
11,, E1) I1
Σ
[11 - 11,, 22) +
[1I+11
Σ
1 (II++(I++1)))
- (111)
1
1
77
t=1
1=1
T
1141 Li)
Σ
(Ilet))))
1
Σ
D (I1++1
n
1=1
T
T
T
(IT, 11 Ei) D Dio. (I1441, Ho)
Σ (I,, Ei) +
[IT+1,
Σ
E.
+
(1+1([I++))
"
[=1
1 (1l1) Σ (141(11(11) -1,(1++1)
T
1 +- (#I+1(II.) (II1))
(IIe 1141 Ed Dio. (I1++1;
Term
1 (11+11) - (Il++1))
Torm II
where the last inequality follows from the fact that:
T
H1+1.
Σ E. + Pr+ Pr+1 (II++1)
II.,
E.
+
1 17
Tr (II.).
1=1
Boundary of Term I:
Next, bound Term I. We relax the constraint II RISIIAA and get the following inequality:
III II, I1,
2,) -,,,,
D (II+,,, I.)
max NER(SIAA
{ - II, Σ.) -Dio. (II, n.)
Next, we define the optimal value vector IT, as follows:
Îi == arg max (n/ II. II, Di (II. n.)
Here, we need to remark that the condition MT+1 & (TI E C.r} may happen.
We begin by analyzing the optimal condition of the update, i.e.
i
1) < II, 2.) - Da, (II (II) = O.
We compute the derivative of the Bregman divergence:
Do. (I) =
(II +. - -II II, V4, - (IL,
011
Therefore, it holds that
(T.( - (II, -
Using the identity (II (II, log !!) = log II II. + 1,, we can obtain that:
(T,, - VIl, = log n LnL.
Above, we can get the expression of II, i.e.
π, II exp(-ppp -n)))-
16

---

Published as a conference paper at ICLR 2026
Next, substituting the definition of de, analyze the Bregman divergence.
Da, (I.) (II (II.) (II - I1,, v (II, log 11) - (11,, log 11,) - (11 11, log 11, + 1)
11
II, log
IIe.
(8)
TT.
We now continue the regret analysis by bounding the inner product term. Using the optimality of i.. we upper bound the above expression by:
(T,, - I1 Ex) (1,-11 (1) z { -T,, R.) - Do, (Ir, II.)
(II, [T,,, (he) - (IT,) + (TT, (IT, IT, (I,)
(a) (IT, - -TT (TT,
+
(TL, IT.),
(9)
where step (a) uses the fact that
(l, - (T. = T1
II, exp(-nīi.).
We now bound the term from Eq. 7 Recall that:
- II) 4(T) - S max (((T) K.
7+ (1(T))
Using this, the cumulative Bregman divergence is bounded as:
Ii, Il. + 11c
Σ Da. (1l, [i.) = 11,, log
11,
=II, (nā, + exp((n(i,) -1) -1)
T
T
Σ Σ
L.(7)² K Σ Σ 22 2,(7),
TEC
TCC
where the first inequality comes from the fact that y + V < 2² for all y -1 and n 2 -1
We now invoke a concentration result. Let (x(()) = 27, combined with Lemma A.3 with probability
least 1 - ō, we have:
ΣΣ
Σ 27. 27.(CC(7) (C.(T) s log (
(10)
rEC,
With probability at least 1 - 8, combining these gives
T
Da. (LL, (1.)) < K
Σ 1² Z.(T))
1=1
t=l TEC.
T
T
r²² La(r) + Ki) Σ Σ (2x(T) - L,(T))
TEC,
TEC.
(4)
log(1/5)
K
Σ
n2 L((T) Knn2
27
TEC,
K-1
Pi(sktl (st, )
(G(T) + Knp log(1/5)
K Σ
Σ 1
II k=
2y
(=1 TEC,
log(1/8)
< K2TT²² IA K + Knn²
27
17

---

Published as a conference paper at ICLR 2026
where (a) follows from the equation 10 and (b) follows from the definition of C in equation |
and
According to the above equation and equation with probability at least 1 - 6, we obtain the regret bound:
E ( 11+11 2i) 11+1,22))
Dio. (11++1,1,,) s KKTT |Al Kn log(1/6)
27
Boundary of Term I:
We consider the Term II: Σn= ( (II+1) - D (II(1)) in Eq. From the definition of regular- izer term in equation it holds that
P441 & (I1+1)) 0.
Therefore, Term II
Boundary of the Regularizer Terms:
We next bound @II for any II and by constant, where II {II, is 4-greedy policy class). Then, holds that
t (TI) = [T(() log (T((T) & Σ l(g
K (ogg(()]AA[))) (8)
S||AT
Therefore, with probability at least the error reg term can be bounded as:
Σ m. - -1, A + nk log(1/8)
- S
(log(((S))))))
(11)
2-
7
Above all, combining all error bound in equation error in equation and error reg in equation obtain that with probability at least 5:: 5:
Vi(mm) - Vi(==) log(1/8)
27
1=1
log(1/6) 2y + - || K log((S)|A[)7)
TIAII Kn
(12)
Bounding deviation in expected regret. from replacing x with x, is bounded as:
We also observe that the difference in expected regret
T Σ Vi(m)) - Vi(TT) S Σ V((m)) s KT.
Now setting
7. we bound the expected regret:
T
Regr = E
Σ
Vi(T)) - Vi(TT))
1=1
< + log T
+
+ + *T((SS)AA)) K
+ Kn
log T
+ |s| K (l
1
2y
2y
n
Optimizing the learning rate and sampling rate y. Set the parameters as follows:
S
K/2
log((S||AA)
7=
A
VT
((S)|A)) K/2 VT
Then the regret becomes:
Regr <K + ([S]IA)) K/2 VT T - ([S]A)) K/2 V K
2
+ K² (IS]AAI) K/2 log(()]|A]) + K (ISIIA)) K/2
Fogg T + (/) K/2 VVolog
<0 (11))AA)) K/2 VT)
18

---

Published as a conference paper at ICLR 2026
A.3 DISCUSSION: ALTERNATIVE REGULARIZATION VIA KL AND MIRROR DESCENT.
We briefly discuss the effect of switching the regularizer. In particular, one can replace our default regularization with Kullback-Leibler (KL) term and perform mirror descent instead of AD-FTRL algorithm. Concretely, given the similar step, the KL-regularized mirror step is defined as:
--1 = arg max (Te (g. 11,)
{
D KL (IL ||L,)
NEC,
where regularization term 4k.. (II [II,) plays the role of a KL-type divergence,
P1+1 (Il) == ΦKL, (Il [[[,] = [Ir,,oo -Kur,)
1L
log
TT
Although it resembles the KL divergence, it is only KL-like since 11, is an occupancy measure rather than normalized distribution.
Remark This formulation can be viewed as mirror descent with the negative entropy of occupancy measures as the mirror map, where FKL serves as the corresponding Bregman divergence. Intuitively, balances exploitation of the gradient direction 9t with proximity the previous iterate II in the KL. geometry. From theoretical standpoint, the analysis follows the same high-level structure in our main framework (via one-step potential inequalities and telescoping arguments). However, the non- normalization of 7 introduces additional technical difficulties, making the analysis considerably more involved. These challenges are addressed in detail the above proof.
Algorithm 2 Adversarial Dynamics Mirror Descent (AD-MD) algorithm
1: Initialize: To. To. II,,
3: Observe of ~ Pe((): Set hg = {8]} 0,
....,... T 1 do 2: for 1 0, 1,1,....
4: for k ....., do
5:
Take the action: at ~ TT(- htt)
6: Observe the loss (s a ), and next state st41 Pt( st,at)
7:
end for
8:
Observe the loss (
9: Get T2 = {88 of
81
K . lr. = E le(st: att
Update: C. T+ Te(at(1f)
[rr.lrec.
11:
Tel = arg min
(Iq. En)
+ I Pz+1 (IIp)
M--1
end for
A.3.1
COMPUTATIONAL COST DISCUSSION
Here we discuss the computational cost of the algorithms. The major computational cost lies in the Line 12 of Algorithm [ and Line 11 of Algorithm 2 In Algorithm [ the computational cost relies in solving optimization problem defined over a space of size ((STA)) This step dominates the overall computational cost of the algorithm.
In the Algorithm the Line 11 can be rewritten as the policy optimization (PO) method.
By applying the KKT conditions and noting that É, contains only one nonzero entry, we obtain the following update:
T (a+ ( x (=(aa()*)) exp(-mff.) (.C.)
Hence, for all a, h, the policy can be iteratively updated as:
(a(aa118) copp(-mee,ta at) E T))
Te=i(a"(10) EnEat exp(-xe,p T((h a) E ET)
Under this formulation, the computational cost reduced from (((()|AA)) ") to (((]]AA Therefore, the proposed PO-based method offers more efficient alternative.
19

---

Published as a conference paper at ICLR 2026
2
14
a
aEa
aed
Figure 3: Illustration of the MDP T {s", a0.0 ,7,0 at.0 K -110) The top row shows the trajectory induced by deterministic history-dependent policy my. The state transitions in this trajectory occur with probability 1. Other branches model deviations and are included with stochastic transitions (e.g., uniform distribution over next states when actions differ from those in the trajectory). The loss is received only in the terminal states, i.c., {(G) = 0 and ((B) 1, where G denotes the "good" state and B denotes the "bad" state.
B LOWER BOUND ANALYSIS.
B.1 HARD MDPS DESIGN.
In this section, we provide the detailed Hard MDPs design process for further proof.
Let be a history-dependent policy. define the set successful trajectories under и as I(x) = (T k good E т, (T) A 0}. From Figure corresponding MDP with transition kernel P,, i.e.
2 we observe that each trajectory T induces
(1 1 a = 1, if (s a., *t1] CT;
1> aaa)= 1
| s a, 7 &T;
( a²
jst if s TT.
To construct the minimax regret lower bound, we design a sequence of adversarial transition kernels. Given deterministic history-dependent policy n', define, for each trajectory E 1'(x'), corresponding transition kernel P- using the process illustrated in Figure 2 Then, for each episode t E [T]. the transition kernel Pt is sampled uniformly from the set {P, function is fixed and follows the structure defined in Figure As a result, the MDP instance faced by the algorithm drawn from the class:
[(x')]. The loss
MAlg E {S,A, (Pr)ee))))) (
In this construction, the hard MDPs are designed such that the policy x' is optimal for every MDP (S, K, Pt, the sequence. Based on this hard instance, an optimal history-dependee must select optimal actions using the observed trajectory history h k- For histories d that prefixes of some т E TTT**), choosing the correct action is critical. This reduces the problem to multi-armed bandit with |S|K arms cach corresponding a possible history-yielding a regret lower bound of order Φ2 (2//1S) (T), which lower than the target minimax optimal lower bound.
policy
B.2 MOTIVATION
In this section, we introduce the proof sketch and motivation. At the beginning, we introduce theorems concerning the regret and loss lower bound of parameter estimation.
Theorem B.1 (Theorem 31.2 (Assouad's lemma) (Polyanskiy & Wu 2025 Assume that the loss function satisfies the a-triangle inequality
{(0o 01) I a (E(0o, 0) e(O1,0))
20

---

Published as a conference paper at ICLR 2026
Suppose @ contains subset Ø' {0, b E (), indexed by the hypercube, such that E(Ob. 0v) 2 dd 8) for all b, b' and some B > Then
3d
TV(Pos, Ponl)
inf sup E0 0) z 6EB
1
max )=(b))))=1
(13)
4a
Theorem B.2 (Theorem 31.3 PPllanskiy Wu 2025 ). Let d be a metric on θ Fix an estimator 0. For any T C ④ and >> 0,
P | 0)
C(T) + logg
2
(14)
log (MT,d,e)
where C(T) sup I(0; X) is the capacity of the channel from 0 to X with input space T, with the supremum taken over all distributions (priors) on T. Consequently,
(2'(1= log lo, TC0
( log C(T) +
inf sup Eg (o(((,,0) 0)"] BeB
sup
(15)
In our work, we aim to provide the lower bound with order ((([S]AA $ VT). For this tighter lower bound, simple Fona's Two points method is not enough. Therefore, combine the above two theorems to provide the regret lower bound.
B.2.1 DESIGN 8 AND 0
Firstly, parameterize the cistory-dependee deterministic policy Ta, here 0 E R LAD We prove that there exists a one-to-one mapping from policy π to parameter 0, i... for T E C,, denote by [[r] the entry of the vector 0, then, the mapping from policy æ to parameter vector is:
K II maa"l")) k=
[r]
To(a
Σ
O, #0
HattAACCT
Based on the above definition, we define the parameter set as follows:
(0 me is deterministic history dependent policy)
Next, we introduce the policy optimal trajectories follows:
r(0)= = l'(T)),
[(x) = (T' 11(T' + 0, EC,,
where
K-1
[[T,,)) = II 0=00
T(a |laa 3 CT).
Remark:
If the trajectory T E [(mo), then under our constructed hard MDPs Me. the expected loss o minimized. This implies that any sampled trajectory belonging [(ma) corresponds to an optimal trajectory.
Next, denote trs (s s! .!....,, R E SK the state trace. Then, we can find one-to-one mapping
[[S] + Cin- = 2 == Sk, for any number E []
(n) = trs, s.t. T n1
where Cin is the state trace available set and function T-1 is the inverse function of Tir-
Next, introduce function to find corresponding trajectory, i.e.,
K-1
[(Tss -
II
mo | 1, (ds C
where state trace indicates that all states in trs appear in the trajectory in the same order.
21

---

Published as a conference paper at ICLR 2026
One transition kernel P, is constructed based on the transition kernel generated by the trajectory shown in the first row Figure
Specifically, the set (a includes all |S| deterministic trajectories that consistent with the policy Tp. Each such trajectory generates a distinct transition kernel.
Then, hard MDPs Ma are defined using these transition kernels, sampled uniformly from the set of all kernels induced by I( Formally, the transition probability of MM is given by:
~ Mo from [(mo): P+(**+1 saaa")) for k = 1.... K 1
where P. is the transition kernel induced by trajectory MM is uniform distribution over ((TO). Here, the transition kernel in episode is assumed be the same.
Remark 5. Here, discuss the adversarial disturbed nature of the MDP process: in each episode, the MDP samples a transition kernel from a reliability set. The transition kernel remains fixed throughout the episode but may change between episodes.
Remark 6. The hard MDP Ma has the following properties:
E arg ming Vr, (T), here PP, E MM. Then, set (M = Ep (Vr, (T)} To E arg ming VMo (TT).
Ve, (Te) =
and VoO(TT) = -6
Therefore, under the hard MDPs Mo. optimal history dependent policy ma. The sample complexity analysis problem can be transferred to the following estimation process - Ma + 1 - Ô. Here, I' is the histories up to episode the I' {I*} is the set of possible histories up episode t. The algorithm tries to estimate the value of from the sampled histories I"" However, the regret-bound analysis
challenging. The problem should be transferred to the following estimation iteration:
0 (Ma; 0.) I' 0.+1. In general, the sample complexity lower bound analysis is fundamental to the regret lower bound.
Therefore, let us review the Theorems and From these two theorems, we could that it is the first step design mapping from 6 0, our work, where E {0, (0.ss Since b a vector, general idea for designing a mapping is to set 0 as a baseline.
Then, define function to find the corresponding trajectory:
k-2
()) + 77;
s.t.
II
no
I19) TO To(A 1 |1--1) 1,
where ht U (at-1) CT. Here, set the function (+) as follows:
Sahie-1, 8 ahillat, i=
A (ak ....
Al(attt) (..,",
Next consider any E (0, (1 o, [
bdd gdd, ba 0,0) = ((Tmssd) g(d.ba = 1,0) = (T)Tss Set a Th. as follows:
T (a 12t)
Te(a" 1²), for k K 1
ner - ( = {1, 1, aft g(d, ba, where ((trs((h*1)
0, otherwise
Then, it holds that
0g.b = 0(TT))
Define the parameters set: O5 = (0r.5 10, 1)(s()
pus uniform distribution over {0, 1) 8
22

---

Published as a conference paper at ICLR 2026
Above all, we design set Mag (Gg. mo). By revising Theorem B.1 the problem be reduced to estimating & from the set θg. Applying Theorem B.1 and B.2 we could obtain sample complexity lower bound. However, establishing a regret lower bound requires further analysis, as discussed earlier.
B.3 EPISODE-HISTORY ANALYSIS
Now, define the episode information 1' = (T:))()T)); where l is the total loss at step t. From the Figure 3] the loss structure is defined as:
((G) = 0, ((B) 1.
That is, the loss distribution only depends on the trajectory Tt. i.c.,
P((e = Tτ) F(l, = 110-1, Te).
meaning the loss at step depends only on Tr.
Here, we define v = j' {0] ae:....... . st) and use Alg/ wt)) E A(A) to represent the algorithm's 's action at step l of round Here, Alg (- vt) denotes the distribution over actions induced by the algorithm. Then, the joint probability of observing sequence of episode information ff under the transition kernel sequence (which is unknown for the estimator) p1 pl...., p2 is:
T
P(I" =TT PI...... Pr)
II
II A=
Alg. (a |1/)) (s (tt
Pilee m))
t=1
T
K
II Algi (at (1)) P((Te)
where vxt - .f...., } and P((T.) = Io (s s at)
Now, take expectation over the randomness of the transition kernel sequence under prior Mo:
P.o (1T = ( = Ep. Mo [IP(T" i (I.....,Pr))
T
K-1
II
II
Alg vt))
P((T)) ax)
1=1
A=
II k=
Alge (at 189)
Ep Pree
II [P(T)R())T))
term
Now consider the inner expectation term:
term = P. Py
E Mo
II P(T) (7) PI. Pr
T-1
Ep MM
Ep II ((TT)P((A)))
1 (Pr(T)))) [r)) |
(16)
Lemma B.3. Define the joint distribution
(M)(T) = EP [P(T)] and Pmo (T, EP-MO [P(T)
where P(r) = Ii P(sh+1 | s a.), st, ar sh+l E
Then, it holds that
PMa (T)
c) if I(Ta)
Pmo (T, (-
otherwise.
3 7
23

---

Published as a conference paper at ICLR 2026
Recall the expression for term in Eq. 16
T
Term = Epp,.... .... Me
II (((e))((((T))) T1)
==1
Ep Ma
I P((.))P((e(I mb)
(T)
II (m,
We then obtain the full marginal probability:
K-1
Alge (at vt)) (mo((t)
PM, =
II Am/
II k=
where
u (2 +e),
E r(To).
Pmo(T1,4:=0) 0)
3 2 otherwise.
B.4 REGRET ANALYSIS
Firstly, given fixed I = if the regret is defined as:
T
T
Reg (I" Mo) Σ
l
Vi(TT)
1m1
tm1
I(T = T)I 0) - - -c)T.
TET(#g) t=1
Now consider the expected regret:
Reg(Ma) = E [Reg (I" = (
T
= E Σ
Σ
I( = =T] =0]=) =0) - - -cT
(ET(F t=1
Σ
EyraPMo
[T = T]] 0)] -2 - -c)
7EI((T)) 1=1
(a)
Σ EyTnFMa
Σ I( =T)==)PPp PM = = 7) - c)
rET(Fe)
1==l
Σ I(TE = r)
Σ
EsTsPMr
-t- - -)
rET(TT)
ESToPMo (xT()))
Σ
Σ Il 7)
1
1=1
=T - Σ
EYTwRMa
Σ I(TT =
TEL(FO)
1=1
where (a) follows from the fact that 72 [(mT), then
P(le 1 (1)))
P(4 = o 1
6,
24

---

Published as a conference paper at ICLR 2026
otherwise,
- 2 P(4 = 1 | Tτ) = P(4 01 ..)
Next, define Nv, = -G Et= I(Te- 7). Then, it holds that:
Reg S - ByyT.Pan [NG(TT)]
rEI(Ne)
B.5 REGRET LOWER BOUND PROOF: O([S} VT).
Consider fixed 0, b E {0, 1j and define
θg (0..0:b be {0. 1) }.
where 1b(bb 6) 2
Then, holds that
max Reg(MM) 2 Epn (Meg BE6
Epp -
Epr Min [N+(T))
T
= cT - cBps
ByTwPMie [WG(T*]] r
Next, let us review the definition. The function to find the corresponding trajectory is defined as:
K-1
[(Tnc(d), = T, s.t.
II aa (1tt) 1, (ds(d) Cr,
k=
II Taaa n1²) TO (o (at)) 11--11 1,
(T(Tnsd))0) + 75, s.t.
where h U 11 r.. Here, the function A is defined as follows:
fatri- i i |ahilaMi, i=1
A k. Al41), Aaahttt)
Next consider any E (0, 1|1s 0 o d [||]
g bu 0, ((T
g(d, ba = 1,0) = (TTTn(dd)
Then, we could get that:
18 EFT [N((T))
Σ
Σ Err [otdbnee d=1
(17)
(ET(ME)
For any 0b g(d, ba, 0) E l'(TA,)) ). If = g(d, ba, 0), then IIk- To(a 11*) = 1 and h C T.
Since |[r g(d, ba, 0) d [| | and all such T, the set is well-defined.
25

---

Published as a conference paper at ICLR 2026
Apply Eq 17 the last inequality, it holds that
max Reg(Mg) 2 eT E.E,,
EF mr (NG(1T))
0
T
Ryr (N ((aba.))
IS K
T
E (gg(bhu + o
2
d=1
where we used that (bu 0) Mbbbb 1) =
Define the joint distribution of histories 7 under conditional marginal:
TP(T" ba = =1 = Ey [((TT) Mo ba = 1.0)
Then, holds that
|s|
max Rcg(Mo) 2 eT
max
(N Ep(r" (b==0 (
2 d=1
Next, define
N No(d.0 = N -No(d,b==1,)) + +N (o(d.bu=0,6)
Set event:
No Ng(a,) 5
21
Aa
|
Lemma B.4 (Bounding Visit Counts and Concentration). IfT 2/8| " VTlog then 1-IP(Aa) S Ts for any algorithm.
Next, consider the following upper bound term that arises in the regret lower bound derivation.
S
E (xgrr/as =p( (N ((d,b2=0,8))
1=1
This term quantifies the expected number of visits to the constructed trajectories under both possible values of the binary indicator ba. We decompose this using the indicator event A. == (Noodd,0) S
2T IS| }:
SS K
E Eecr (i + Ep g(dd
d=1
1/2 1
Epir Sprrr/oassn// + BBpr
Sy
(Berr Eecrr b==
bn W No [I( [[AA)]]]]
26

---

Published as a conference paper at ICLR 2026
We now bound the second term. Since the number of visits NG T deterministically and the event complement probability P(AA) 73 by Lemma B.4 we get:
|S) K
Ep(r (o (1 + Ep(r Ngg
2
d=1
(B + Ep(r by m) M (o + |S|K
Σ
T2
Now, on the event Ad, we know:
2T
2T
aadd.b==1.8) < [
Ngld.b=00.))
S
To control the average visit count under the mixture distribution P(ITT 0). we use:
P( 0) ( T ba 1,0) + JP(T" ba = 0,0), where g(d, ba 0, 0.0)= trs.
Thus, the total expectation becomes:
EperT (bu= [N o(dd + E2(
[N go.d S Reer (b a(d.by [(Aa)) + + Ep(rT g( [Aa)] + Bp( W o,
We now apply the fact that [[[((A)) S AeB and bound the remaining terms as follows:
Ep((T WN - (
Ex(rT 1b,=0) W (. EpirT (N
b(d.bb=1.0))))) p1 [Aa))] + (p( (N No [(Aa)) + #.
Next, using the upper bound N g(d, T[ (Aa)) <
27 T we have:
Sp(r7|ba=11) (N
1(,,6,=1,0)) + Ep(r by [N o(d,b,
Eg(r" b==1) W (d T[ (Aa)) + Epçr" (b)= W T(Aaaal + +
2T
|S|
<
Ep(r" b-=1)
N
aid.bb=1, T( T(Aa)
[S] k
2T
2T
|Sk K
+ [
E EE(IT (e(ITbb.=))
N
0, (Aa) + Tz.
2T
Finally, by Pinsker's inequality lp g12 S KL(pllg) and the fact N No S TST we
conclude:
2T
|SIK .v Noc0b0=1,0)(AAa)
|S NV
Bp(Tbb==1)
-Epr 1
2T odddbb==10 T(aa)
2T
2T
| V
(LP ba 1)) 10))-
Similarly, it holds that
2T
S
ISK K
R
2T No(dbb=0..)TAAa) T(Aa)
Nv.
E (0)
2T o,) T(Aa))
N
2T
(LP(((T (b PP] (0))
|
27

---

Published as a conference paper at ICLR 2026
Above all, could conclude that
(Bp(rT 9( + Eeerr o
Bearmba-1) 1err + t (ggt 1s
7"
B (N( + NN N, +
1St
7
KL(P(I2) 0) ba= 1)) +
2T
KL(P(IT [ ba ba=0) 0))
1
1
Is|
|8|
< 2 (
No(d.bu11.)) + +N No(d.bu=000)
72
ISI
2T K
(LL(PIT () ba 1)) + KL(P(IT () ba = 0))
term
IS|
T
SKK
+
V2T
Σ
(term I+ term II).
T
S||K
Next, consider the term and term 11, we introduce the following lemma: Lemma B.5.
KI(P(I" [I] ba 1,))) Ep(rrio) [Noccoo=100) (oaioi))NWWWo...a
No ( (2+0()+))
KL(P(IT [0] ba = 0, 0) Epprrio) [ + N godd (()))
Next, consider the following upper bound term that arises in the regret lower bound derivation:
S
(o (N
(18)
Therefore, applying Lemma B.5
Σ
EpprT (N + EpcT () W (ggdss)00)))
1=1
S)x x
<
2T.
Veeur o7 o/ + N Noldbe=o,o))
According to the fact that N Ng(d,bs=1.0) + N Wold,bu=0.0) ST:
K
1/4
EecT ( oidd (p( (N (o.
+
K
7
+
TT 1
S) /T
skk +
0/2
18|872
28

---

Published as a conference paper at ICLR 2026
Next, the regret lower bound becomes:
[8] K
max (oeeg((Mp 2
T 2 d= 1
EperTT (b W (odd + Ba(TTba-0 /Nv (oleba=ooo)))
2 T
T
I
/279/22
T
k//
|s|
|s|K
Let
/T
32//222
then if
7
< 8
the
T c S 8
S|
max (Mg
S K/2 k|/ VT (T
T
T
T
32
B.6 PROOF OF THEOREM 5.2
To add the |A| K/2 term, we first introduce the following lemma:
Lemma B.6. Let 0, 0, 8, c. and let X
{II...., IN):
Define the probability follows:
) (2,,0
PI(X = (1 + =) -6)
Ij Beml 0,e).
Fz.
i=
Further, it holds that,
(x 1
2M P1 2M -
Po(x
2M
PMo (x Po(x"), PM, (x))
_
1
)
M -
P)
M
M
Then the KL divergence can be bounded follows:
N
Ne²
KL(PM||PMMM) <
22 (L(P 2
2M2
Next, define the policy class:
V( = {To : 0 E Ob.))
Then, find a policy class cover:
2(0) (100)) such that:
(1) [2(0)] = 1A|K-1 No:
(2) Any 01, 0g O, satisfy (00) n (B,) = 2 or ((1) = [((2);
(3) (0) E (()).
Define the joint parameters set as:
θo 10 [Np], s.t. exists map yp + 0,p ((())
(EN(
For any b E (0, l to simplex, set Pp.b 00.0_ Then, the parameters set θ is defined as:
θ = (Go.p |pe [Np), e (0. 1)1s1").
Next, Hbg is the uniform distribution over [N₂] {0, 1118
29

---

Published as a conference paper at ICLR 2026
Then, it holds that
Reg) 2 Bo (Mou.))] AE
max
Then, the regret satisfies the following equation:
Regr (Ma..)
= [Reg (I" M]
T
[ T, 1==111 1)] - ( e) T
tET(x)
T
EING]
|s
E Nocdbaathool
T
Next, we take the expectation of regret bound, and it holds that
Eo,, -
(Regr(Mes.e)) )]
No
1
[Regr (Mon.)))
Ng
18 k
E. (Ngttaeewl) )
1
E
T
Σ
N
Φ #=1
N₂
cT
(Bp(rTb==1000))) (Nocbb=1.0..))
2T
N
1=
+ 0.)00.))) (M(csso
Next, 1a. uniform distribution over [N₂] x 10,1)
Then, holds that
max RMg) 2 Eog.b [Regr (Mo oc
Further, we can rewrite the regret as:
(Mg.b) = E (I" ,Man.b)]
[T = T, 1)] (2 (2) T
rET
=6
T
Σ
B[NG]
|
T
ELN ba, 0oww0]
d=1
30

---

Published as a conference paper at ICLR 2026
Next, convenience, we rewrite Ny ba, 0b.0) = [d, bu, 0v). Then, it holds that
No
Egg boppo [Meg.(Moog.t]]
No
N₂
1S)
M [ ba, 0+)) )
Eb-ras
6
T
w=1
d=1
N
1
eT
1
1, 1,0
2T
N
d=1
==1
+. ba 0, (,0)))))
Set:
N q Σ 0()10)), q( ba 1,0+)
Σ
P(. 0b) 1
P(. ba 1,0g) (resp. bd 0).
Nop
No
Then, the regret lower bound can be bounded as: max Regr(Mo)
8
Nº
N
1
cT
1,)
N
No
|
N
cT
1
(T, + Be bo=0.8,)
2T
term 1
Term I Estimate. From the Lemma B.4 and proof in the previous section, could bound:
Term LN [,,,(d,b
2T S
(VEccelle d, = 1,0,)) + (L I b, = 0, 0.0w))
+
+ 73
Then summing over all d, 1/:
SS|
N
1 No
IS|KNg (I,,(d.b==18)))) + (Ng(d))=000w) + T2
Term < E.g
d=1 V=1
P=1
[SIK No T
T
VEg
Eg [Ng(( INC(aha /T
T
|S|
N₂
Next, we define the joint distribution as follows:
1
S I
2 2/15T ))
ET VT
VT
max Reg, (egg((MM)
2 eT
1
T
8E0
2T
T
|S|K
No
eVT
ET
273
V
/2/8
K K
Here, set e
if Z (IS|IAA)* K log T. then
AVT
AVT
V2
V(SS|A))
max Regr(Mo) AE
2
( - f)
128
31

---

Published as a conference paper at ICLR 2026
IfT Σ |(( x log T' frozen some states, i.e. Nos I |5h lctiive and 2Nss (A K log T 2
T 2 4N5|AAK log' T' Then, with similar proof process,
VN
2Ns|AAlt
T
max (Mg) 8cô
128
128 log
128 log 2
T
The proof completed.
C PROOF OF LEMMAS
Proof of Lemma A.3 Here, provide the proof of Lemma A.3 we do error decomposition as follows:
We set Xr and X = 2. Then,
(L,
(T()) = (x(T) (((7).Imm <
((TT) I
[1.
(T) + (T) (l((T)
3
1 +
(6,(r) (T)
From the inequality 14s/2
= I loo(1 + 2) for all 2 2 0, we have:
(T( s B 1 log 1+ Ble(T) 17=7.
(1,
Then, to simplex the presentation, we rewrite E, (P Combining with the inequality 21 log(1 + 22) s log ((1 + 21) for 21 < 1, we can get:
E, exp Σ Eaa (((())((()))
E,
exp
Σ
Ce(T)
B
log 1+ B. B.G((T) II=TI (
I1((T)
AEC,
TEC+
(0)
(e(T) -e((T) -Irmre
Ey,
1l+(T)
(6)
(1((T) -(((T) -I
E2
[T((T)
TEC.
(x(T) (((() II
=1 =1 E
11,(7)
LEC,
(c) + Σ (x
TEC,
Σ au(r){((1)))
exp
(19)
TEC,
where (a) from the constrict that a.(r) and (b) follows from the fact that 27
1 I,,, =0
Irr Ir=,
The (c) follows from the Lemma A.1
32

---

Published as a conference paper at ICLR 2026
Then, can further get
(((())-((1)) log (!)
P
Σ Σ ax(T)
TEC,
$ 81
exp
(x(T) (Zi(t) -((T))
TEC
Σ Σ as(() (Zi(t) - ((i(t)-C((t)) c((7)) E
= 8E
exp
exp
Σ
az((T) (Er(T)- Cr(T))
t=1
TEC+
TEC,
(a)
Σ ar(T) (Z,(T) c((tt)
S 6E
exp
Σ
TEC,
S 6... 6,
where (a) follows from the Eq.
Therefore, get that
Σ
Σ ar(T) ((((7)-f((7)) s log ( rEC,
Proof completed here.
Proof of Lemma A.4
For any two policy n,, n' E Cx and any T E Cr, holds that
K-1
K-
(T) = II
त(a 1+*) 1. (T) = II x' h*t). k=
k=
For II, AII, + A) where X E [0, 1], we can get the स from II.. For convenience, 11(h² a²² = I1; π (a²) It²) and u(h**) = En. 11(h", a²). Clearly, given the vector 11, we can get the value of TT(h" a²) and (T(**) easily by the iteration IT(h" aa*) ITI++1),, h at C h and I1(h+= Ear 11(h* (()).
Next, set
the policy corresponding to the vector II, we next prove that ((a+)/+)) AlI, (k* and #(a E Cr. AII, (11)+(1-A)),))))))0 (a*)
Firstly, it holds that
= Σ AL a A)TT (N& a²))
(l+) + X)II (h/))
ah
ab
Arn 11, (h + (1 Eox 1h ( )+)
XIT + (1 - (h+t)
III (1+*
+ (1 (1-))) =
Ah* + (h
Therefore, the स is a policy.
Moreover, since policy and n' e-greedy policy, i.e. TT(a ((()))))))()(() 2 it holds that
A1= a + (1 x)Il (h+t, (h*ka**) a²
2 min { Th (nt,,a ,a Th (hi att) } (h*) 11
T(a at min n (a+ (a= 2c.
XII (1 A)II, (h+)
Therefore, the is e-greedy policy. Above all, the policy स Cz.
33

---

Published as a conference paper at ICLR 2026
Besides, have that II(h a²))
I1 for 1d-1 htt Then, if {ht a C for
O,.... K 1. T C,, we can get
K-1
K-1
( a²) + (1- - A)lll. a
II 7(a
II
ALL + (1 2)ll (1²)
k=0
k=
K-
XIl (1+ ( (1 A)ll (h"
= (ATT a²) +1 (1- -) (h. (h",a") aa))
XTT A ( + (1 X)TI (1it-1, (h aah-1)
= (AII+ -1 a --= + (1 X)ml (h
-a=k-1)) (T) + -
Policy the policy corresponding to the vector IT.
Above all, proof completed here.
Lemma C.1. Define the averaged distribution
(M)(T) = PP-Mo [P(T)] and (M. =- Ep [PG)P(77]
where P(7) = II=o P( | a0t, st at sbtl E
Then,
(T) 18|2
+c)
E otherwise.
(M,
18
|S|
Proof of Lemma C.1
Next, consider the hard MDPs described in the figure/definttion.
If E T(To), then
(T)
1
Σ
P+(T)
1
|51K
S|
('E((TN)
1
Pmo (1)==
2 +
|
Define the set K I i.c.
K
k (TT)
Te (a 11²) = 1
T
k=
K
2
p (TO) A
Te (a 118)) = 1, (a 1 =0).
K-1
k=
k-1
T (*00)
II
(a h1*) =1, II no ka |1 0
k=
Remark 7. A trajectory in this set means: at the K-th step, the action is not optimal.
If trajectory r' E K I'EIK-I(TT) (TT)) then
PM (T)
Σ P+(T))
|87
('ET(FO)
Σ
I(T' # T, hK c t and K-1 C CT)
|
r'E((TT)
[S]
|
[S]
S
34

---

Published as a conference paper at ICLR 2026
Here, the event (T' # T, r, T, h C r') indicates that the current trajectory is consistent with the past optimal actions except the final step.
We now evaluate the probability of suboptimal trajectory r' & [(TT) under the averaged distribution.
PMo = |8| TET((T)
Σ P+(T')
(IS) - 1)K 1 ([S) 1) |8|K
8 K
The individual term inside the sum is
P+(T))
(IS) 1)K- 1(7' is available in Pr),
where availability means the trajectory is reachable under Pr.
The total number of such trajectories satisfies
Σ
I((r' is available in P.) ([S) R
(m))
Thus, the expected joint distribution for a suboptimal trajectory is
PMo (T) S and (T, 2 R if & ((m)).
Above all, the proof ends here.
Proof of Lemma B.4 Firstly, it holds that given any I",
(d. Σ o 1,0) +
Σ I g1
From the definition g(d, ba, 0), both forms are instances of (d) 0).
Set
Nus I(trs(TT) trs).
We observe that
(T:T= g(d, by 0)} S (r : trs(() = trs(d))
Therefore, we need to prove that
P(Nss
2T T5Tx
for T> T 2|81* /TlogT. 7
Next, we prove:
(1) P(NNsss = (1NNs,, i.e., trs i.i.d.
(2) ((trs(T) trs) T
35

---

Published as a conference paper at ICLR 2026
We compute:
B[ = E
T(trs(T)) us) =ts)
[[(Irs(T))) = urs)
Σ
(IT
I= T.CC, (rs((r)) Tr
K-1
II Alg(a ( v&)) (T)
1=1 EFEE
k=
T
(T)) Ssk
Thus, Nus ~ Binomial 1 KK k: T). Therefore,
VT
Var(WNrs) T (Ttx)) (1- 1/x
S||1/2'
Using Bernstein Chernoff bounds.
P (Nis-
T
T K
<
P
NNix >
27 (
S exp
T 1
S
<exp
((3lgg S 7.
n
3
36


Reviews:
[{"review_id": "ElnseywHRO", "reviewer": "Reviewer_rRoE", "summary": "This submission introduces (to the adversarial RL community) the key observation that the optimal policy in episodic MDPs with adversarial trantisions and rewards is not necessarily Markovian. Following this observation, the authors give a FTRL-type algorithm achieving the optimal regret $\\tilde{O}(\\sqrt{|\\mathcal{S}|^K|\\mathcal{A}|^K}\\sqrt{T})$. The authors also certificate the optimality of the standard FTRL routine with a novel lower bound construction, simutaneously manifesting the exponential-in-$K$ dependency of $|\\mathcal{S}|$ and $|\\mathcal{A}|$.", "questions": "- Given the existence of EXP3.P in the literature that achieves high-probability guarantees, do the authors plan to argue about the dfficulty for proving a high-probability regret bound for (potentially certain variant) of their Algorithm 1?\n- The lower bound construction is more significant than the upper bound analysis. In fact, is it more appropriate to reduce the length of the description of the relatively standard FTRL-type routines in the main text and elaborate more on how the authors successfully manifest the dependency on $|\\mathcal{S}|^{\\Omega(K)}$ and $|\\mathcal{A}|^{\\Omega(K)}$ simultaneously in the lower bound analysis?\n- Though it is relatively standard for adversarial RL papers to assume the state space to be disjoint for different steps, it is a bit interesting to also assume the action set to be disjoint for different steps. How does this later assumption simplifes the proof?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The employment of non-Markovian policy as the correct class to consider is a novel and significant observation\n- The construction beyond constant many arms is novel for proving the lower bound\n- Lemma B.3, which justify the convexity of the set of trajectory distributions induced by $\\epsilon$-greedy non-Markovian policies, appears to be novel", "weaknesses": "- Algorithm 1 a relatively familiar to the adversarial RL community, if not standard. \n  - It is intuitively likely that history-dependent policy has been considered in different contexts but also under the algorithmic framework of occupancy measure; with that said, I respectfully question the originality of Lemma B.3. The authors can correct me if that is not the case.\n  - Since Lemma B.3 seems to be the major technical novelty in the upper bound analysis, it is more appropriate for the authors to justify its originality.\n\n\n### Minor weaknesses\n\n- On Figure 1: There is as a typo because the authors may want to design the initial state in $P_1$ to be $\\star$.\n- Theorem 5.1: $O$ -> $\\tilde{O}$\n- Line 320: The first $\\pi$ on the RHS should be $\\pi_t$\n- Line 226: Occupancy measure has been introduced in very classical literature, e.g., those regarding the linear programming formulation of RL in MDPs. I mean this is definitely not a concept that was introduced for the first time in the 21st century.\n- Line 169: It seems that the loss function considered within one episode is time-homegeneous, right?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "96l3PNtgtT", "reviewer": "Reviewer_jyEJ", "summary": "The paper studies episodic RL with fully adversarial transitions and bandit feedback. At every round the environment can pick an arbitrary MDP (transitions + losses) from a hard family; the learner only observes a trajectory. The authors propose a trajectory-level FTRL algorithm that maintains a distribution over trajectories and uses importance-weighted loss estimates. They prove a regret upper bound $O((|S||A|)^{\\frac{K}{2}}\\sqrt{T})$ and then match it with a lower bound of the same order. Thus, the minimax optimal rate is derived for this model. They also show Markov policies can be suboptimal: optimal strategies must be history-dependent.", "questions": "See weakness.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper give sharp information-theoretical result. Upper and lower bounds match with order $(|S||A|)^{\\frac{K}{2}}\\sqrt{T}$ so the rate is tight for fully adversarial model.\n\nBy working directly on trajectory occupancies instead of state–action occupancies, the paper pinpoints where previous bounds picked up a linear term in the transition variation.\n\nThe example showing Markov policies are insufficient in this adversarial setting is useful and interesting.", "weaknesses": "Both the regret bound and computational complexity is in exponentially order. Although this is correct and tight in theory, it makes the algorithm less practical. \n\nIn previous papers where $O(\\sqrt{T} + C^P)$ regret is derived, it gets sublinear regret when the change of transition is small. This paper, however, always suffer  $(|S||A|)^{\\frac{K}{2}} \\sqrt{T}$ regret no matter how the transition changes. Thus, the new algorithm is better when $C^P = O(T)$ and $T >  (|S||A|)^{K}$, which is a very restrictive regime.\n\nThe change of transition is obliviously adversarial, what is the additional challenge for adaptive adversary?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "a0pOsJqtBC", "reviewer": "Reviewer_sqJH", "summary": "This work studies how to learn MDPs with both adversarially chosen transition kernels and loss functions. Prior studies only obtain a regret of $\\mathcal{O}(\\sqrt{T}+C^P)$, where $C^P$ is the degree of adversarial change of transition kernels. This work proposes an FTRL algorithm, which operates over the space of trajectory occupancy measure and achieves a regret of $\\mathcal{O}\\left(\\sqrt{(|\\mathcal{S}||\\mathcal{A}|)^K T}\\right)$. The authors also prove a matching lower bound for this problem.", "questions": "1. In MDPs with unknown yet fixed transition kernels and adversarially chosen loss functions, we can devise a policy optimization (PO)-based algorithm, which is more computationally efficient and easier to implement. Is it possible to devise a similar PO-based algorithm for the problem considered in this work?\n2. Typically, using FTRL with Shannon entropy may lead to suboptimal factors of $\\log A$ in adversarial bandits and of $\\log (SA)$ in adversarial RL. Why FTRL with Shannon entropy can lead to the minimax optimal regret without having similar factors in the result?", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "1. **Novelty**: The idea of the trajectory occupancy measure in this work is simple yet powerful. The matching lower bound is also very interesting.\n2. **Presentation**: Most parts of this work are generally well-written and easy to follow.", "weaknesses": "1. **Computation efficiency**: If any, I feel that operating over the space of the trajectory occupancy measure makes the algorithm computationally inefficient. Also, I seemingly cannot find any discussions relating to the computational efficiency of the proposed algorithm. That said, I personally do not think it is a significant drawback, considering that this work proposes the first minimax optimal algorithm for this challenging problem.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "1yphPfLoYT", "reviewer": "Reviewer_jRLS", "summary": "This paper addresses Adversarial Reinforcement Learning (RL) where both the transition kernel and the reward function exhibit adversarial dynamics across different episodes. To tackle this, the authors propose AD-FTRL, a novel algorithm based on occupancy measure analysis. This method achieves a regret bound proportional to the square root of the number of episodes ($\\sqrt{T}$). Furthermore, the authors include a counterexample to suggest the optimality of their proposed framework.", "questions": "1. The preliminary discussion (\"WARM-UP\") primarily focuses on the adversarial transition kernel. While it is true that learning transitions in a stochastic environment is often harder than learning the reward function, the analysis should address the additional challenges and complexities that arise when combining adversarial rewards and adversarial transition kernels simultaneously. A deeper discussion on this interaction is warranted.\n\n2. The current framework assumes the action and state sets are non-overlapping across different stages, and, more specifically, assumes uniform sizes such as $|A^k|=|A|$ and $|S^k|=|S|$. What is the regret bound without these simplifying assumptions? The paper should discuss the impact of varying state and action space sizes across stages.\n\n3. Several key related works on Adversarial Reinforcement Learning are missing and should be included for proper context and comparison:\n\n(a): Fully Adversarial RL (Under Function Approximation): The analysis of fully adversarial RL extends beyond tabular settings when incorporating function approximation:\n\n[1] \"Provably Efficient Exploration in Policy Optimization\" (ICML 2020) considered the adversarial reward function under linear function approximation.\n\n[2] \"Near-optimal policy optimization algorithms for learning adversarial linear mixture mdps\" (AISTATS 2022) later extended the results to achieve optimal guarantees within the linear function approximation setting.\n\n(b): Adversarial Corruption (General Function Approximation): In the setting of adversarial corruption, work has also addressed robustness with complex function classes:\n\n[3] \"Towards robust model-based reinforcement learning against adversarial corruption\" (ICML 2024) studied adversarial attacks on the transition kernel with general function approximation, achieving a near-optimal regret guarantee under the adversarial attack model.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. This paper tackles the challenging problem of fully adversarial Reinforcement Learning (RL), where both the transition kernel and the reward function exhibit adversarial dynamics across episodes. The proposed framework comes with a strong theoretical guarantee of $\\mathcal{O}(\\sqrt{T})$ regret.\n\n2. The authors provide counterexamples that demonstrate the necessity of non-Markovian policies and further illustrate the optimality of their proposed algorithm.", "weaknesses": "1. Even though the lower bound suggests that the regret is optimal, the regret bound has an exponential dependency on the size of the state-action space ($|S||A|$). Consequently, the regret bound is non-trivial only when the number of episodes ($T$) is sufficiently large (specifically, $T > |S||A|^k$). This exponential dependence significantly limits the framework's practical application to large-scale problems.\n\n2. Some claims regarding related work are improper. Specifically, concerning the Upper Bound Analysis, it is crucial to note that prior analyses for adversarial reinforcement learning or bandits operate in three distinct settings, each with a different regret definition. It is unfair to make a comparison without clearly stating these differences.\n\n(a). Fully Adversarial RL: This work falls into this setting (discussed in Lines 118-119), where there is no limitation on the adversarial dynamics, and regret is calculated against the best fixed policy across all episodes. Prior work in this setting did not consider a dynamic transition kernel.\n\n(b). Adversarial Corruption: This setting (Lines 128-129) focuses on corruption where a base reward function and transition kernel exist, and only a small corruption is added. Regret is calculated against the optimal policy in the base model and is efficient only when the total corruption level ($C$) is sublinear in the number of episodes.\n\n(c). Non-Stationary Environments: In this setting (Lines 134-135), the regret is measured against the optimal action in each episode (not fixed across episodes), making the guarantee strictly stronger than the guarantee in this paper. However, this comes at the cost of having a limitation on the cumulative dynamic.\n\nOverall, it is necessary to clarify the different settings to accurately establish the contribution of this work.\n\n3. The claim in Remark 1 is incorrect. There still exists a trivial method that treats each Markovian policy $\\mathcal{S} \\times \\mathcal{H} \\to \\mathcal{A}$ as a distinct bandit arm or agent, which yields $|\\mathcal{A}|^{|\\mathcal{S}|H}$ different arms. Even though the result from this trivial method is non-optimal, the authors still need to clarify the mapping.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)