Adapting to Stochastic and Adversarial Losses in Episodic MDPs with Aggregate Bandit Feedback
Authors: Shinji Ito
Kevin Jamieson
Haipeng Luo
Arnab Maiti
Taira Tsuchiya
Venue: NeurIPS 2025 poster ()
Keywords: online MDPs
aggregate feedback
best of both worlds
Primary area: reinforcement_learning

Abstract: We study online learning in finite-horizon episodic Markov decision processes (MDPs) under the challenging \textit{aggregate bandit feedback} model,
where the learner observes only the cumulative loss incurred in each episode,
rather than individual losses at each state-action pair.
While prior work in this setting has focused exclusively on worst-case analysis,
we initiate the study of \textit{best-of-both-worlds} (BOBW) algorithms that achieve low regret in both stochastic and adversarial environments.
We propose the first BOBW algorithms for episodic tabular MDPs with aggregate bandit feedback.
In the case of known transitions,
our algorithms achieve $O(\log T)$ regret in stochastic settings and ${O}(\sqrt{T})$ regret in adversarial ones.
Importantly, we also establish matching lower bounds, showing the optimality of our algorithms in this setting.
We further extend our approach to unknown-transition settings by incorporating confidence-based techniques.
Our results rely on a combination of FTRL over occupancy measures,
self-bounding techniques,
and new loss estimators inspired by recent advances in online shortest path problems.
Along the way,
we also provide the first individual-gap-dependent lower bounds and demonstrate near-optimal BOBW algorithms for shortest path problems with bandit feedback.

Adapting to Stochastic and Adversarial Losses in Episodic MDPs with Aggregate Bandit Feedback
Shinji Ito The University of Tokyo and RIKEN shinji mhinji@mist.. u-tokyo. ac. jp
Kevin Jamieson
Haipeng Luo University of Southern California haipengl laasc.eduu
University of Washington
j jamieson@cs. washington edu
Arnab Maiti
Taira Tsuchiya
University of Washington arnabm2@uv.c edu edu
The University of Tokyo and RIKEN tsuchiyafmist. wtw.:aammis......tooooooooooo ac.
Abstract
We study online learning in finite-horizon episodic Markov decision processes (MDPs) under the challenging aggregate bandil feedback model, where the learner observes only the cumulative loss incurred in each episode, rather than individual losses at each state-action pair. While prior work this setting has focused exclusively worst-case analysis, we initiate the study of best-of-bboth-ooll (BOBW) algorithms that achieve low regret in both stochastic and adversarial environments. We propose the first BOBW algorithms for episodic tabular MDPs with aggregate bandit feedback. In the case of known transitions, our algorithms achieve Ollog T) regret in stochastic settings and ((VT) regret in adversarial ones. Importantly, also establish matching lower bounds, showing the optimality of our algorithms this setting. We further extend our approach to unknown- transition settings by incorporating confidence-bart on combination of FTRL over occupancy measures, self-bounding techniques, and new loss estimators inspired by recent advances in online shortest path problems. Along the way, we also provide the first andivdual-gaa-deeente and demonstrate npar-optimal BOBW algorithms for shortest path problems with bandit feedback.
techniques. Our results rely
lower bounds
Introduction
This paper considers online learning problems for finite-horizon episodic Markov decision processes (MDPs) with aggregate bandit feedback [Efroni et al. 2021] Cohen et al., 2021). In this feedback model, the learner receives feedback on the aggregate loss in each episode, which is the sum of losses for all state-action pairs in the learner's 's trajectory of that episode, rather than individual losses for each state-action pair. The aggregate bandit feedback model naturally arises in various real-world applications where only trajectory-level outcomes are observable. For example, in personalized healthcare, sequence of medical treatments is administered, but only the final patient outcome (c.g.. recovery rate) is observed, without attributing effects to individual actions. Similarly, in application to the design of educational programs, students experience curriculum composed of multiple learning activities, while feedback is typically available only in the form of an overall test score.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

Table I: Regret bounds for episodic MDPs with known transitions. Here n²" is an optimal policy and S is the set of states that can be reached by x.. "TC" stands for computational time complexity and a checkmark (v) indicates that an efficient implementation is possible.
Algorithm
Stochastic
Adversarial
TC
Bubeck et al.
2012
| I log [A
V A |A|
Lancewicki and Mansour
2025
| LT LT log
S | log
Dann al.
2023a
Ito et al.
22024
P1A A log T
| log |A|
Amin
This study (T'allis entropy)
Enfse (Ftt" (8) Exjer
T
v AISIAALT
A(5,0)
Amin
This study (Log-barrier)
log
||T log
[[s,a]
Lower bound
Excs-, (:A((,))30 ((s.))
T
ASSTATTT
In the study of online learning for episodic MDPs, two different models of the loss (or reward) function are commonly considered: the stochastic model and the adversarial model. In the stochastic setting, it is typically assumed that the loss function & at each episode / is independently drawn from an unknown fixed distribution. contrast, the adversarial model makes no such probabilistic assumptions and allows the loss function & to vary arbitrarily over time. In various online Iearn- ing/bandit problems, including those with individual loss feedback in episodic MDPs, is well known that one can achieve instance-dependent Opolyylg r'grrtt in the stochastic setting, and Ö(VT)-regret -regret in the adversarial setting, where T is the number of rounds/episodes and the Ö(-) notation hides logarithmic factors in parameters. However, to the best of our knowledge, prior work on episodic MDPs with aggregate bandit feedback has focused exclusively on the worst-case analysis (i.e., O ((vT))
best), and no algorithm is known to achieve instance-dependent (polylog 7'') -rerrttt under the stochastic loss model with aggregate bandit feedback and unknown transitions.
This paper focuses on the design of algorithms that can effectively handle both stochastic and adversarial loss models. More specifically, we aim to develop single algorithm that, without any prior knowledge about the nature of the environment, achieves O(polylog reerret in stochastic settings and O(VT)--reret in adversarial settings. Such algorithms are referred to as best-of-bott worlds (BOBW) algorithms [Bubeck and Slivkins 2012). While many prior works design separate algorithms tailored to either the stochastic or adversarial model, real-world applications often involve uncertainty about the true nature of the environment, making BOBW algorithms especially valuable in practice. Although BOBW algorithms have been developed for various settings including episodic MDPs with individual loss feedback [Tin and Luo| 20200 Jín et al. [021] 2023) no such algorithm was known for episodic MDPs with aggregate bandit feedback with unknown transition, prior to this work.
1.1 Contribution
This paper presents the first BOBW algorithms for episodic tabular MDPs with aggregate bandit feedback and unknown transitions. More specifically, we consider layered MDPs with L-layers, and begin by considering the setting where the transition probability matrix P is known, designing an algorithm that achieves Ö(VT))-rege in adversarial environments and O(log - in stochastic environments. We then extend this approach to the more realistic and challenging setting where the transition matrix P is unknown, with the help of the techniques by Jin et al. [222]] for handling unknown transitions.
Our results are accomplished by combining some algorithmic frameworks including follow-the regularized-leadee (FTRL) over occupancy measures and self self-bounding techniques (Wei and Luo 2018 Zimmert and Seldin 2021] with key ideas from the recent study by Maiti et al. [2025] on the online shortest path problem with bandit feedback. More precisely, our algorithm is inspired by their loss estimation method for the shortest path problem, which plays central role in our design. By adopting their loss estimation approach, not only can we construct an estimator using only bandit feedback, but we also find that its second moment is well-controlled (see Lemma 4 and the subsequent

---

Table 2: Regret bounds for episodic MDPs with unknown transition. log -(log(())|A()))
Algorithm
Stochastic
Adversarial
TC
Efroni et al. 2021
V log
Cohen et al.
2021
([S||A))01))
V(IS|AA)OOT
Lancewicki and Mansour [2025
V S loge
VISTP|A|LTTog log
((SAIAS log"
This study
1)15 ALTTlog
Amin
Table 3: Comparison of regret bounds for online shortest path problems with bandit feedback. The quantity 0 represents the instance dependent constant characterizing the asymptotic lower JEL as shown bound for linear bandits [Lattimore and Szepesvari 2017), and it is known that c* S Amiu
in Lee et al. [2021] Here E' Unevo(s) 0+v { (o)} and E Uwev-u(s) 04 (x)),
where 0+ V C is the set of outgoing edges from v, ' is an optimal policy and V is the set of nodes reached by 'τ. Please refer to Definition 2 for further details.
Algorithm
Stochastic
Adversarial
TC
Bubeck et al. 20122
[E|T log
TTToog [P]
Lattimore and Szepesvari [2017]
Lee et al.
2021
c² log T (PT
F (PIT
Dann et al.
2023a]
Ito et al. 2024
[E log (P] log
| log PP]
Amin
This study
(Tsallis entropy)
log Enery
logh
v ET LT
Amin
This study borgbbarree))
log EeEF
E LT log
A(e)
Lower bound
c² log T 2 E.Ek
Tog
E log (P) log E
[[e]]
discussion). This property is highly beneficial for designing BOBW algorithms. Building on this insight, we propose efficient and nearly optimal BOBW algorithm for the online shortest path problem with bandit feedback, which naturally extends to the case of MDPs with known transitions.
However, extending this estimation idea to the unknown-transition setting requires substantial care. The new estimator contains negative terms, and thus, naively replacing the occupancy measure with its upper confidence bound, done in prior work [Jin and Luo 2020 Jin et al. [021], does not necessarily yield an optimistic estimator. To address this, we carefully design the estimator so that it is optimistic in expectation and its second moment remains well-controleed. This allows us not only to effectively handle aggregate bandit feedback, but also, perhaps surprisingly, to avoid the technically involved loss loss-shifting technique used in prior analyses [Jin al. 2021 2023), thereby simplifying the overall regret analysis. We refer the reader to Section for a detailed discussion of these estimator constructions.
The regret upper bounds established in this work and prior studies are summarized in Tables 2 anan [3] For detailed definitions of the symbols used in the tables, we refer the reader to Section 2 "TC" stands for computational time complexity and a checkmark (v) indicates that an efficient implementation is possible. The symbol > 0 denotes a polynomial factor in other parameters such as T, |S], and [A]. In Table 3 for the shortest path problem. P denotes the set of all directed paths, and it holds that log [P] S min[[V], L, [E]] where L is the maximum number of edges in path of the given graph. Here, S Y means X = O(Y) in this paper. Similarly, X Z Y means X = )(Y).
As shown in Tables I and we propose computationally efficient BOBW algorithms that achieve nearly tight regret bounds for known-transition MDPs and the online shortest path problem. We note here that the corresponding lower bounds for stochastic environments are also new con- tributions of this paper. The adversarial lower bounds for toown-trassitio MDPs and online
3

---

shortest paths are due to Lancewicki and Mansour 2025 and Maiti et al. 2025 respectively. For iaanoon-transition MDPs (Table 2 we propose the first BOBW algorithm that achieves an O (Eeter.afar+s)
1 [ log ++| log (L (1)))))) log Logs+Lis: P|A log" -regret bound in the Amiu
(+,a)
stochastic setting and simultaneously achieves an upper bound of Ô (V(IA) + L)I in the adversarial setting. Moreover, all of our BOBW algorithms exhibit robustness to corrupted stochastic environments, achieving regret bounds of the form O + VUC), where U is the stochastic regret and C is the corruption level. These results are established using an argument similar to the standard self-bounding technique (Zimmert and Seldin 2021 Jin et al. 2021 2023).
Due to differences in the problem settings, several caveats must be taken into account when making comparisons. First, while prior work on episodic MDPs assumes that the per-step loss or reward within each episode is O(1), our setting assumes that the aggregate loss or reward over entire episode is (1). To align the scales, we multiply the regret bounds from prior work by a factor of 1 L. As noted in Remark [ in the appendix, our setting strictly more general. In addition, some prior works [Cohen et al. [021] Lancewicki and Mansour [0225] consider non-layered settings, and we reinterpret their bounds in terms of the layered setting by replacing (S] L with |S] where appropriate. Furthermore, while we evaluate the expected regret defined in Section 2 some of the prior works
(Efroni al. 2021 Lancewicki and Mansour 2025
Lee al. 2021 establish eigh-probbbility regret
bounds.
Tables 1 and 3 include the bounds achieved by applying algorithms developed for finite-armed linear bandits Bubeck et al.] 2012 Lattimore and Szepesvari 2017 Lee et al.) [002 Dann et al.] 2023a Ito] al. 2024]. where the feature space dimension is A or E). and the number of arms is calculated as | or [P], respectively. We note that due to the exponential number of arms in this approach,
is generally unclear whether an efficient implementation is feasible. In contrast, the other algorithms listed, including our proposed methods, can be implemented efficiently using dynamic programming or convex optimization techniques. We include additional related work in Appendix A
2 Problem setup
2.1 Episodic Markov decision process
In this paper, we consider finite-horizon Markov decision processes (MDPs) with finite actions and finite states. The model is defined by a tuple (S, A, P), where S is the finite set of states, A is the set of actions, and P S A + [0, 1] is the transition function that defines the probability of moving from one state to another given an action. We assume that the state space S consists of (L+ 1) layers:
S can be expressed as disjoint union as S U Sk, where Su {so} (initial state), St { (terminal state), Sk + ( for E [L- -L-1, 11, and S& UK = for is * k. Transitions from the k-th layer allowed only to the (k: + 1)-th layer, i.e., for any A E f0. 1....... L- 1}. Eves p(s'(s,) = 1 holds for all s E S2 and a E A and P(s'|s,a) = 0 for all s E Sk. a E A and s' E E'S S Let k(s) denote the index of the layer to which the state belongs. In known-transition setting, we assume that the transition function P known to the player. On the other hand, in maknown-transition setting, the player does not know the transition function P and it is learned through interactions with the environment.
In episodic MDPs, the player interacts with the environment in a sequence of episodes. Before
each episode E [T], the player selects a policy n, E πl == {T (S {st)) ) x A - [0, EasA ([ls)) = }} and the environment selects loss function f, S x A + [0, 1]. Each episode
E [T] consists of a sequence of time steps. The initial state si is set to sp for all episodes E [T].
At each time step k E {0. I, L 1-1) the player chooses an action af E A according to the policy Te. i.e., aj follows the distribution T. (-(- and state si+11 is sampled from the transition function P(-Isf ab) given the current state si and action at. At the end of the episode, the player observes the aggregate loss feedback e E [0, 1] such that E [ce ((of. at) )x)eeLu- = Σtzd (sf, af), which corresponds to the sum of the losses incurred at each time step in the episode. We note that the player does not observe the individual losses (e(*f, af) for le E [T. 1]. All the information revealed the player in each episode is the state-action trajectory (($), )=E(LL) and the aggregate loss c. We

---

assume that the loss function & is chosen so that Σk=o ( af) E [0, 1] for any possible trajectory (($), (lf (et For notational convenience, we suppose that (5 a) is set to 0 for all a E A.
For a transition P. loss function & S x A - R. and a policy л II, let Q (s. a; f) and VP f) express the values of the and Q- functions, i.e, we set P (SL) Q (sL, = and recursively define
Q PM (s,a; a; = (().0)+
Σ P( (s: = [ S'ES
aEA
for 8 o s1, and E A. The Q-function and V-function satisfy the equality stated in the following lemma, serves as a fundamental property that underpins both the justification of our loss estimator and the derivation of the regret upper bound.
Lemma Suppose i is defined by f(s,, a) = (" (3 - (s; {) for some a E II and for all E S and E A. We then have
v (s: E) V²
(s; (=;(s) (s, Q" (s, - (s:
(1)
for any n' 11, s E S and E A. In addition, we define the occupancy measure qf S A |0, 1] by (s a) Pr [[sk; ax) (s, ((5k; is sampled according to and P]
(2) for 8 E SA and a E A. We also denote gf (s) = =cEed (f. a) = Pr [sk s] for E Sk. for notational convenience. Let QP -1 Po by the transition P. We note that ºº is a closed convex set. From the definitions of V, Q and q, we have E [ee | TT, 4a] = V. (so, Le) = (fe,g = En Exes, EeEA a((s,a)q Using these concepts, we define the regret:
fq
E II} be the set of occupation measures induced
P (s, a).
Regy(TT) E
Σ
T
(v Pitt -v (so, (i) = E
Σ
). -
l Ping
Pite - -
(3)
where E|.) denotes the expectation with respect all the randomness of the environment and the player. We also denote Regz- = ma (x*), Hereafter, when it is clear from the context, we may omit P and for simplicity. Additionally, for notational convenience, we denote
(-) P (; ()) = P. (;44).0
(( gi Pixi, and gd =
2.2 Regime of environments
We consider several different regimes as models for the environment generating the loss function l, In an adversarial regime, &, can be chosen arbitrarily by an adversary, depending on the history ((TT (E))) ())_) so far and the policy म, chosen by the player. In a stochastic regime, the loss function E, is independently and identically drawn from unknown distribution for each episode E [T]. For a stochastic environment, let
x A - [0. denote the expected loss function, which is defined as (s, E(fe(s. a)] for all E S and E A. We then have Regr = E [TT (6".9t q") = E Exe EAEa A(s, a)
a)). where q" e arg wiggmnnge (e", and A 5 A [0, 1] is defined as A(s, a) Q" (s, Vx (s; QF' (s, a; --)mmin/'e Q (s, d') for an optimal policy x² that minimizes V V"((s; (*). We note that the optimal policy n" unique and only if the set arg min (s, a; (*)] (a e A A(s. a) 0} consists of single action for all s E S. Here, generalization of stochastic regime admitting a unique optimal policy, we can define the an adversarial regime with self- hounding constraints:
Definition (self-bounding regime for MDPs). Let x= S + A be a deterministic policy. Suppose that A : S A [0, 1] satisfies A(s, a) > 0 for all S \ {st} and a E A \ (s)). Let C' 2 O. The environment is in an adversarial regime with a (T",, A, C') self-bounding constraint (or, more concisely, (TT", A, -)sselo-bounningg regime) if holds for any algorithm that
T
Regr (Tt)
2 E
Σ
Σ
Σ
A ()) - C.
(4)
SES (+)
5

---

We also denote Amin min. (7 A(s, a). As discussed by Zimmert and Seldin [2021), this general regime that includes stochastic environments with adversanal corruptin. where the parameter C' corrrsponns to the total amount of corruption. For more details, see, e.g., [Zimmert and Seldin 2021
Jin and Luo 2020 Jin et al. 2021
2.3
Online shortest path problem
In online shortest path problem, the player is given a directed acyclic graph (DAG) G = (V U {s, g...g),E. E). where and g the source and target vertices, respectively, V is the set of other vertices, and E is the set of edges. Denote m = E and n = [V Let L. denote the maximum number of edges in s-g path in G. In each round and the player chooses a path Pt from to At the end of the round, the player can only observe the aggregate loss feedback & [0, 1] such that E [ez P, Eeep. l(e),, while the player does not observe the individual losses (e) for E E. The definition of regret, the regimes of the environment, and other related concepts are defined in a similar way to in the case of episodic MDPs. More details on the model are given the appendix. We also note that the online shortest path problem can be interpreted as an "almost" special case of episodic MDPs with known transitions, but it is not necessarily an exact special case. For details, see Remark 2 in the appendix.
[T]. the environment chooses loss function & F [0, 1]
3
Core idea: construction of loss estimator with aggregate feedback
A key aspect of the proposed algorithms lies in how to estimate the loss function in setting where only the limited aggregate loss feedback is available. In this paper, inspired by the approach of Maiti itt al. (2025) to the online shortest path problem with bandit feedback, we extend the idea to the MDP setting. We begin by briefly reviewing their approach.
3.1 Review of the approach of Maiti et al. 2025 for the online shortest path problem
The online shortest path algorithm by Maiti et al. 2025
maintains an 8-g flow qe E C [0. 1] of convex hull of the set of all s-y paths. In the following. we denote (v) = Eeeay q(e) for any E [0, 1 and e E V U {s}, where 04v C E is the set of outgoing edges from t. From qt, it samples path pt E 10, F in Markovian way, i.e., we choose a path as follows: (i) We first initialize pa E {0, 1 by (e() = O for all e E and set V + s. (ii) [c)c)
capacity 1. Note that Q can be interpreted
While * g. Pick E 04 with probability q.(0) set Pr(e) +- 1, and transition to e's terminal vertex e4,, i.e., set u <- e.. We then have E [p: q:] = lt. i.e., each edge e E E is included in the path p with probability (e).
After constructing the path pt as described above and obtaining the aggregate loss feedback G. such that E [c, Pr] (t,,Pt). the loss estimator [p(p) for any s-g path p (s vo, eo, el, ................................ 1L-1,, E1, g) is defined as follows!
L(()) Σ po(ew)
I-1 Ct - pe(ea) = C. Σ p(e)pu(()
plu)pa(w) (c(w)
(5)
K=0 (+(e))
k=1 (v&))
(((e)
We then have E L((p) gr. Ee]
() for any s-g path p. In fact, the conditional expectation
given qe, la satisfies
(e()))
E
Elesppe (p(())) 1] Le(s + vk) + le(ex) + LL + 9).
(6)
(e()))
(r((k)
E
C
E((esptt (((())) = 1] L. + vx) + Le + +))
(7)
qe (1x)
where Le(v + v') represents the conditional expectation of the cost of the subpath of p. from v to v'.
given that Pt goes through and v'. By combining 55) and we obtain (T(()) qt l =
'The construction method by Maiti et al. 2025 does not exactly match the one described below, as they add a uniform shift and incorporate implicit exploration[Net (2015). These adjustments are designed to obtain high- probbbllbayility regret bounds, but they not essential in this study, which focuses expected regret bounds.

---

Eks (((ex) (fr.)) In this paper, we define the loss estimator & E R by Ea(e) = a
pile) Pele_) where e- E U {s} is the initial vertex of the edge E E. As we have (((e)
(COP) = (p) Cr for any s-g path p. we can use le as loss estimator in our FTRL framework.
3.2 Loss estimator for MDPs with known transition
Let qe E Q be the occupancy measure for the policy Te. Suppose that the trajectory ((s). of k= is generated according to the policy and is the observed aggregate loss feedback. For any } and for any 8 E Ss and a E A, denote (+))) Tia s] and T, a) =
E (0. 10.
T[( af) (s, a)}. Note that we then have E [T)()) TT. (:(s) and E (1, a) TT] = (.(8. a).
Inspired by the approach of Maiti et al. [2025]. we define the loss estimator as the following lemma:
Lemma 2. The loss estimator le S A + R defined Ee(s,a) cc- (e(a))
((ssa)
L(a) 4x(3)
satisfies
E ((, l, mt (s, a;
4r (s; =: (s)
(8)
From this and Lemma we have (TT E
ET (V= (s0: Ri) v (so: k:)
E (2:.1 [.)0
)-
Thanks this, we can use E, instead of & in our FTRL-based algorithms.
3.3 Loss estimator for MDPs with unknown transition
In the case of unknown transitions, when attempting to construct a loss estimator in the same manner as in Lemma 2 a key difficulty arises from the fact that the true value of q: not available. To address this issue, one may follow the approach Jin et al. (2020) and compute upper confidence bound ue for gt, using as a surrogate the estimator. However, naively replacing de with u, in the definition of &g in Lemma
2 introduces yet another issue. Specifically, as le in Lemma 2 contains
a negative term (i.e., Cc (s)) ) substituting with its upper bound dy may lead to an undesirable positive bias in the estimator, which creates an obstacle in the regret analysis. To derive valid regret upper bound, is essential that the estimator is optimistic, i.c., its expectation must act as lower confidence bound on &, in (8). To this end, we define the following novel loss estimator:
le())
(8 a) C. (s, a) (1 Te(a 8) c.) (e(s) s) - (1 7.(a 8))
We (s, a)
We can evaluate the expectation of EY in manner similar the proof of Lemma 2 as follows:
(s)
E [ (s) le, Te, u.
V* Ei) +1 (r(ass)) - (1 Te s)). (10)
(s)
We here have (s,
V V= = (s Ed'E Te(a' ss) 6 = (1
Te(al Tr(als)) (8, a; bx) - Ea' Te (a'
dd) 2 -(1 (r(als)) as QTa a; 4,) E [0, 1].
and thus: Q=: (s, a; Ee) (s; (1-ss - 2 0. Hence, under the condition of (s) 2 qs()..
the value of (10) is lower bound on (s) == Q= a; E,) a (s; f,), i.., (s. is an
optimistic estimator of Es(8, a). In addition, the gap between them is at most He(s)-9de) T (als)))
(x())
Lemma 3. Under the condition of uu( 2 (a). we have
E((s,a) (s) (s)
(1 (cls)) < E (s, la Ri, udl $ a))
(11)
Ur ur(s)
3.4 Second moment of loss estimators
Our proposed algorithm, like those of Jin et al. 2020 Jin and Luo 2020 Jin et al. [2021), J. is based on the Seew--the-Reullaiieee framework, the second moment of the loss estimator plays crucial role. The second moment of the loss estimator introduced in this section can be bounded as follow:
Leader (FTRL) framework over occupancy measures. In this
7

---

Lemma 4. Loss estimators Eg in Lemma
2 and EY in satisfy
1- ([ass))) (=)
E (s. la Te, mp] 2 1 T(ass) 24 (s.
q:(())
(((8,a)) C,,
+1)
(1((s)
When applying the self-bounding technique derive an Oppolylog T') regret bound, the (1 ग. (als))
factor in this lemma plays a crucial role. In prior work [Jin et al., 2021 2023], the original loss estimator did not exhibit this factor in its second moment, and hence the analysis relied on a carefully designed shifting function to apply loss-shifting trick and extract the desired (1 x{ass)) factor. However, this significantly complicated the analysis. In contrast, our regret analysis does require the loss-shifting trick, as the belldbounding technique can be applied directly. As result, we avoid the technically involved analysis necessitated by the loss-shifting trick in previous work.
4 Algorithm and regret bounds
4.1 Warmup: online shortest path problem
As warm-up, let us consider the algorithm for online shortest path problem. Following the ap- proach Maiti et al. [2025]. we update point q the 8-y unit flow polytope Q (i.e., the convex hull of all s-g paths) using the following FTRL framework: ge E arg minge { <>== Z,.9) + +v(())
where 2, is given as in Section 3.1 and (g) is a regularizer function defined as:
()( =
2
Σ
[(ee)
((n with N = Vi
1
B = 0(1,
(Tsallis entropy)
T)
eEE
EEE
()(1) Σ
Ing(e) with me(c) (4 In Σ P- (+))
log-barrier)
(e(e)
EEE
where we define pc(e) (G
g.(e) )² We then have the following regret upped bounds: se(e_))
Theorem 1. Let p¹ [0.1] be an arbitrary s-g path and 'T" UU {s} - E be such that (v) E 0pvfor all v E (s) and p" (e()) =
= xt (e-)= =e.
e. In the case of Tsallis entropy
T
Regr(p") S
Σ t=1
E
E Σ E
Var())+ +
Σ
V(((+(()) + VmnL + m log T.
VEVU(S)OEOLLM
-V
the is given by Tog-barrier regularizer, we have
Regr E
Σ Σ
EL (.p.(e)(1 qetr)
gele)
log(T)) m log(T).
DEVU(s) cE0+v
Corollary 1. We have Regg S / /L[(n + T) + n log T the Tsallis entropy case and Regr S VmL(n + T) log T in the log-looriee case. Simultaneously: under the condition of Regr(p") 2
E DE Everu(a) EeEO ((e)p((e) Cor some A E [0, 1)= and C 2 O, we have log + LogoTT Ale)
(x") S U + VUC, where U = =vevU(N)) Eneo, (x(((()))
Amin in the Tsallis
entropy case and U = Enevu()) EnEH, (x))(()))
Ion'T A(e)
for the flog-barrieree case. case..
The tightness of the gap-dependent upper bound derived here is discussed in the appendix.
4.2 MDPs with known transition
The algorithm design for episodic MDPs with known transitions almost identical to the case of the shortest path problem. Specifically, we apply the FTRL framework over the set of all occupancy measures the feasible region, replace each edge E E in the regularization functions in (Tsallis entropy) and (log-barrier) with state-action pair (s, a) E S C {SL} x A, and redefine as pr(s,a) a) ((,((s,)) (1 ae(al ?) With this setup, we obtain the following regret bound:
8

---

Corollary 2. We have Regr E V + A8] log T in the Tsallis entropy case and Regr 2 V|S||A|LT log T in the log-barrier case. Simultaneously, under the condition of (4), have Regr(T) (TT) S U + VUC, where U == DoffL Eossr(s) A(r,a)
log + LS log in the Txallis entropy
Amin
case and U = = Spta Eapar(s) TogT for the log-barrier case. M(s,a)
The gap-dependent upper bound achieved by the log-barrier regularization in this corollary is tight. In fact, the following lower bound holds:
Theorem Consider stochastic environment in which ct follows a Bernoulli distribution of parame-
ter Σk=1 E* (s at) where we assume that this value is [3/8, 5/8) for any possible trajectories. Define A S
+ [0. 1] by A a) = Q (s, a; E*) V (s; et) for an optimal policy π Let S be the set of all states E S { such that q" (s) > 0 for some optimal policy x². Then, for any consistent algorithms, we have lim i
Regr
log 2 Exes- EacA:A(r))>0 Als.a)
4.3 MDPs with unknown transition
Our proposed algorithm for MDPs with unknown transitions adopts epoch-based approach, similar to prior work (Jin et al. 2021 2020J. each epoch i, it updates both the transition probability estimates and their corresponding confidence intervals. Based these, we compute an upper confidence bound ut on the occupancy measure q.. and use it to construct the loss estimator E as defined in (9). Note that (s, a) can be efficiently computed using the COMP-UOB procedure proposed by [Jin et al.) 2020].
We then define the adjusted loss estimator as f- Br, where B; a bonus term derived from the confidence width. Unlike prior work, choice of the loss estimator f allows to avoid scaling B; by an additional factor of L. The policy for each episode is selected by applying FTRL over the estimated occupancy measure space using l.. The regularization function used here matches the Tsallis entropy regularizer from Section 4.2, except that the learning rate Ty is reset at the beginning of each epoch, and a small log-barrier term is added to stabilize updates.
A notable improvement over prior work (Jin al. 2021] is that the second-moment bound established in Lemma alllows us to bypass the loss-shifting technique. As a result, our regret bounds exhibit improved dependence on the horizon L. We refer the reader to [ the appendix for full details. Our algorithm, constructed in this way, achieves the following upper bounds:
E
Theorem 3. In the bandit feedback setting, Algorithm 1 with 8 t and l ISTAT guaran-
tees Rogr(z*) = 5 (LISIVIATT + |S I,2 | and simultaneously Regr (egr(x**=
o AU+VUCC + +V) under Condition where V = -L In² and is defined as
In [ h22
(S In + L|S) In
U= Σ Σ
+
A(s,a)
AMN
888L (e)
We defer the proof of the above theorem Appendix
Conclusion
This paper initiated the study of best-off-othh- worlds (BOBW) algorithms for knite-horizon episodic MDPs with aggregate bandit feedback. We proposed efficient algorithms that achieve low regret in both stochastic and adversarial settings, and established nearly tight upper and lower bounds under both known- and unknown-transstion settings. Our approach built upon FTRL over occupancy measures, combined with carefully designed loss estimators that optimistic in expectation and admit tight acoond-momen bounds.
Despite these contributions, many open questions remain. A central limitation of our approach is its reliance on occupancy measure updates via FTRL, which-while grounded in convex optimization and thus computationally feasible some extent-still requires solving convex problem in each

---

Algorithm BOBW algorithm for MDPs with unknown transitions and aggregate bandit feedback
Input: confidence parameter å (0, 1)
2: Initialize: epoch index i = 1 and epoch starting time t = 1;
3: V(s, a, s'), set counters mi (s, a) = ma (s, a. mg (s a) mo a, 0;
4: empirical transition Pi and confidence width B1 based on Eq. (2);
5: for = 1..... T do
6: Let de be the regularizer defined in Eq. 63 and compute
q: arg min Ei= (g. Eg) Φ((9),
(E
where E, - B, and (s, min 2 2' Bi(s, a,),
7: Compute policy Te from q such that (T(als) x (c(s, a).
8:
Execute policy We and obtain trajectory (s1, (e.)) ) for k = 0, ...., -1 1.
9:
Construct loss estimator eú as defined Eq. (9) Increment counters: for each k < L,
10:
my (s(8 Or.k; 8t,++1) ms(8t,k Ot,k, St,++1) + 1, m,(81,,, < ms( (t,,), +
11:
if ak, mz(S ar.x) 2 max(1, 2m (st, a,,)) then
& entering a new epoch
Increment epoch index i + and set new epoch starting time 4 1+1.
13:
Initialize new counters:
(ss, a, s'), m.(s, a, s') = m m=,1 as, m,(s, a) = m,,1 a).
14:
Update empirical transition P. and confidence width B, based on Eq. (57) and (58)
round. Moreover, this framework does not easily extend beyond tabular MDPs to more general representations such as linear models function approximation.
promising direction address these limitations is adopt policy optimization- meth- ods [Shani et al.) 2020 Luo et al., 2021]. In particular, a recent paper by (Lancewicki and Mansour 2025] has shown that near- optimoptima and efficient adversarial regret bounds can be achieved through policy optimization. Combining this line of work with the techniques in [Dann et al. [023a may yield BOBW algorithms that are both computationally efficient and more broadly applicable.
Another important direction for future research is to extend the present results beyond the online shortest path problem other combinatorial optimization settings, or more challenging MDP for- mulations such as stochastic shortest path problems [Chen et al. 2021]. Addressing these challenges may lead a more comprehensive understanding online learning under aggregate feedback.
Acknowledgments
Ito is supported by JSPS KAKENHI Grant Number JP25K03184 84.. Jamieson is funded in part by NSF Award CAREER 2141511 and Microsoft Grant for Customer Experience Innovation. Luo funded by NSF award IS5-1933607. Tsuchiya is supported by JSPS KAKENHI Grant Number JP24K23852.
References
Sébastien Bubeck and Aleksandrs Slivkins. The best of both worlds: Stochastic and adversarial bandits. In Proceedings of the 25th Annual Conference on Learning Theory, volume 23, pages 42. 12.123,. 2012.
Sébastien Bubeck, Nicolo Cesa-Bianchi, and Sham Kakade. Towards minimax policies for online linear optimization with bandit feedback. In Conference Learning Theory, volume 23, pages 41. 14. 2012.
Sébastien Bubeck, Michael Cohen, and Yuanzhi Li. Sparsity, variance and curvature multi-armed bandits. In Proceedings of Algorithmic Learning Theory, volume 83, pages 111-127. PMLR, 2018.
10

---

Clément L Canonne. A short note on an inequality between KL and TV. arXiv preprint arXiv:2202.07798, 2022.
Asaf Cassel, Haipeng Luo, Aviv Rosenberg, and Dmitry Sotnikov. Near-optimal regret linear MDPs with aggregate bandit feedback. In Proceedings of the s1 International Conference Machine Learning, volume 235, pages 5757-5791, PMLR, 2024.
Niladri Chatterji, Aldo Pacchiano, Peter Bartlett, and Michael Jordan. On the theory of reinforcement learning with once-per-episode feedback. In Advances in Neural Information Processing Systems, volume 34, pages 1401-3412. Curran Associates, Inc., 2021.
Liyu Chen, Haipeng Luo, and Chen- Yu Wei. Minimax regret for stochastic shortest path with adversarial costs and known transition. In Conference Learning Theory, pages 1180-1215. PMLR, 2021.
Alon Cohen, Haim Kaplan, Tomer Koren, and Yishay Mansour. Online Markov decision processes with aggregate bandit feedback. In Conference on Learning Theory, pages 1301-1329, PMLR, 2021.
Chris Dann, Chen- Yu Wei, and Julian Zimmert. A blackbox approach to best of both worlds in bandits and beyond. In The Thirty Sixth Annual Conference on Learning Theory, pages 5503-5570. PMLR, 2023a.
Christoph Dann, Chen- Yu Wei, and Julian Zimmert. Best of both worlds policy optimization. In Proceedings of the 40th International Conference on Machine Leurning, volume 202, pages 6968-7008. PMLR, 2023b.
Yonathan Efroni, Nadav Merlis, and Shie Mannor. Reinforcement learning with trajectory feedback. In Proceedings of the AAAI conference on artificial intelligence, volume 35-8, pages 7288-7295, 2021.
Liad Erez and Tomer Koren. Towards best-of-all-worlee online learning with feedback graphs. In Advances in Neural Information Processing Systems, volume 34, pages 28511 1-5221. Curran Associates, Inc., 2021.
Shinji Ito. Parameter-free free multi-armed bandit algorithms with hybrid data-dependent regret bounds. In Conference on Learning Theory, pages 2552-2583, PMLR, 2021.
Shinji Ito, Taira Tsuchiya, and Junya Honda. Nearly optimal best-of-bott-worldd algorithms for online learning with feedback graphs. In Advances Neural Information Processing Systems, volume 35, pages 28631 1-2643... Curran Associates, Inc., 2022.
Shinji Ito, Taira Tsuchiya, and Junya Honda. Adaptive learning rate for foloww-heeregglaiiee--eddd Competitive analysis and best-of-both-wont Learning Theory, pages 2522-2563. PMLR, 2024.
In The Thirty Seventh Annual Conference on
Chi Jin, Tiancheng Jin, Haipeng Luo. Suvrit Sra, and Tiancheng Yu. Learning adversarial Markov decision processes with bandit feedback and unknown transition. In International Conference on Machine Learning, pages 4860 4869. PMLR, 2020.
Tiancheng Jin and Haipeng Luo. Simultaneously learning stochastic and adversarial episodic MDPs with known transition. In Advances in Neural Information Processing Systems, volume 33, pages 16557-16566. Curran Associates, Inc., 2020.
Tiancheng Jin, Longbo Huang, and Haipeng Luo. The best of both worlds: stochastic and adversarial episodic MDPs with unknown transition. In Advances in Neural Information Processing Systems, volume 34, pages 20491-20502. Curran Associates, Inc., 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. In Advances in Neural Information Processing Systems, volume 36, pages
Curran Associates, Inc., 2023.
Tal I Lancewicki and Yishay Mansour. Near-optimal regret using policy optimization online MDPs with aggregate bandit feedback. arXiv preprint arXiv:2502.04000 2025.

---

Tor Lattimore and Csaba Szepesvari. The end of optimism? an asymptotic analysis of finite-armed linear bandits. In Artificial Intelligence and Statistics, pages 728-737. PMLR, 2017.
Tor Lattimore and Csaba Szepesvári. Bandit algorithms. Cambridge University Press, 2020.
Chung-War Lee, Haipeng Luo, Chen- Yu Wei, Mengxiao Zhang, and Xiaojin Zhang. Achieving instance-optimalityy and hinimax-optimaliis in stochastic and adversarial linear bandits simulraneously. In International Conference on Machine Learning, pages 6142-6151. PMLR, 2021.
Haipeng Luo, Chen-Yu Wei, and Chung-Wee Wei Lec. Policy optimization in adversarial MDPs: Improved exploration via dilated bonuses. Advances in Neural Information Processing Systems, 34:22931- 22942, 2021.
Arnab Maiti, Zhiyuan Fan, Kevin Jamieson, Lillian Ratliff, and Gabriele Farina. Efficient near- optimal algorithm for online shortest paths in directed acyelic graphs with bandit feedback against adaptive adversaries, 2025.
Saeed Masoudian, Julian Zimmert, and Yevgeny Seldin. A best-of-both-worle algorithm for bandits with delayed feedback with robustness excessive delays. In Advances in Neural Information Processing Systems, volume 37, pages 141071-141102. Curran Associates, Inc., 2024.
Gergely Neu. Explore no more: Improved high-probability regret bounds for non-stochastic bandits. In Advances in Neural Information Processing Systems, volume 28, pages 3168-3176. Curran Associates, Inc., 2015.
Lior Shani, Yonathan Efroni, Aviv Rosenberg, and Shie Mannor. Optimistic policy optimization with bandit feedback. In International Conference on Machine Learning, pages 2020.
PMLR,
Taira Tsuchiya, Shinji Ito, and Junya Honda. Best-of-both-world algorithms for partial monitoring. In Proceedings of The 34th International Conference on Algorithmic Learning Theory. PMLR, 2023a.
Taira Tsuchiya, Shinji Ito, and Junya Honda.
pewalty follow-the-reuularized leader: Sparsity, same-dependency, and wort-l-bbtth-woold. Advances in Neural Information Processing Systems, volume 36, 2023b.
Chen-Yu Yu Wei and Haipeng Luo. More adaptive algorithms for adversarial bandits. In Conference On Learning Theory, pages 1263-1291. PMLR, 2018.
Julian Zimmert and Yevgeny Seldin. An optimal algorithm for adversarial bandits with arbitrary delays. In Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics, volume 108, pages 3285-3294. PMLR, 2020.
Julian Zimmert and Yevgeny Seldin. Tsallis- An optimal algorithm for stochastic and adversarial bandits. Journal of Machine Learning Research, 22(28):1 2021.
12

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
Theorems match the claims made in the abstract and introduction.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results be expected to generalize other settings.
is fine include aspirational goals as motivation as long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes].
Justification: Limitations and future works are discussed in the conclusion section.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification. asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low images are taken in low lighting. Or speech-to-text system might be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach address problems of privacy and faimess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question:
For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
13

---

Justification:
Every assumption our problem setting is clearly mentioned in the introduc-
tion.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proof's can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should properly referenced.
4. Experimental result reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [NA]
Justification:
The paper does not include experiments.
Guidelines:
The answer NA means that the paper does include experiments. If the paper includes experiments, No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm. (b) If the contribution is primarily
model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome deseribe the particular way they provide for reproducibility, In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
14

---

Answer: [NA]
Justification:
The paper does not include experiments.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.cm
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https
/ ccpppi.ccppulli//uuuiu wwwiiicgguie///eeeeeeeeic CoodeSubeiiieeee ssi wswonnolli onnolicy)))) for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [NA]
Justification: The paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [NA]
Justification: The paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, at least for the experiments that support main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
should be clear whether the error bar is the standard deviation the standard error of the mean.
15

---

It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of enrors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [NA]
Justification: The paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g.. preliminary or failed experiments that didn't make into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https: httpp:::///errsss... http:/p....pppp..ttttccccccllela
Answer: [Yes]
Justification: Our paper is theoretical in nature.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is a special consid- eration due to laws or regulations their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: Our paper is theoretical in nature.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that improvement in the quality of generative models could be used to
16

---

generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
there are negative socictal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: Our paper is theoretical in nature.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
Justification: Our paper is theoretical in nature.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, wwppppswppteeeee www.reewwthhhe....c. com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's is creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
17

---

Answer: [NA]
Justification:
Our paper is theoretical in nature.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details the dataset/codd/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: Our paper is theoretical in nature.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, other labor should be paid at least the minimum wage in the country of the data collector.
Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: Our paper is theoretical in nature.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, originality of the research, declaration is not required.
Answer: [NA]
18

---

The core method development in this research does not involve LLMs as any important, original, or non-standard components.
Justification:
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, or non standad components.
Please refer to our LLM policy hattps://neurips.. 200ps//ee//o0oeeeeeee/////////// for what should or should not be described.
19

---

Contents
Introduction
Contribution
2
Problem setup
2.1
Episodic Markov decision process
2.2
Regime of environments
2.3
Online shortest path problem
3
Core idea: construction of loss estimator with aggregate feedback
3.1
Review of the approach of Maiti al. [025 for the online shortest path problem
Loss estimator for MDPs with known transition
3,3
Loss estimator for MDPs with unknown transition
3.4
Second moment of loss estimators)
Algorithm and regret bounds
Warmup: online shortest path problem
MDPs with known transition
MDPs with unknown transition
5
Conclusion
Appendix
20
Additional related work
21
Auxiliary lemmas
22
B. Lemmas for FTRL
22
B.I.I Stability terms for one- dinenssennii functions
22
Online shortest path problem with bandit feedback
24
C.I Notation and problem setup
24
Algorithm
................................
25
Regret analysis
26
................................
C33.1
Analysis for entroyy case
28
Analysis for log- nagrbarrierae case
31
C.4 Lower bound for stochastic environments
33
D MDP' with known transition
35
D.I
Algorithm
35
D.2 Regret analysis
37
D.2.1 Analysis for Tsallpyynntrppy case
37
20

---

D.2.2 Analysis for log- bog-barrier case
38
D.3 Lower bound for stochastic MDPS
38
Algorithm for MDPs with unknown transition
41
Confidence set of the true transition
42
Loss estimator and Regularizer
42
Main Result
43
Analysis of BOBW with unknown transitions
44
Auxiliary lemmas
45
F22
Technical lemmas to analyze ESTREG
49
Adversarial regret guarantee
52
Stochastic regret guarantee
F44.1
Self-bounding terms and related lemma
53
Proof for the stochastic world
A Additional related work
FTRL and www.oofooohworldeee algorithms In episodic tabular MDPs with adversarial losses, Jin and Luo 2020) is the first to propose BOBW algorithm under known transitions. Jin et al.) [002] extended this to the mnknown-transition setting, which is further improved and extend to the setting where the transition can vary over episodes (Jin et al. 2023 Subsequently, policy optimization algorithms was shown to achieve BOBW guarantees with improved computational efficiency (Dann) al.) 2023b]. In spite of these developments, under aggregate feedback. We build on the analysis of Jin et al.) [202T]. While we may improve our bounds by using the optimistic transition technique from the recent work by Jin al. [2023]. remains unclear whether this technique can be effectively combined with our loss estimator, which can be negative.
work the first consider BOBW algorithms
A key challenge in achieving BOBW is the design and analysis of the regularizer in FTRL. In this work, consider two types of regularizers (see Section 4.1). The first one is hybrid regularizer (Bubeck jt al. 2018) that combines the Tsallis entropy with a small-coefficent log barrier. The first BOBW algorithm based on the Tsallis entropy was initially explored by Zimmert and Seldin [2021]. and
the hybrid regularizers to ensure the stability of FTRL have been shown to be powerful in obtaining
BOBW guarantees for complex online learning problems
for obtaining adaptive bounds Zimment
and Scldin 2020 Erez and Koren, 2021 Ito et al., 2022, 2024 Tsuchiya al., 2023a b Masoudian al. 2024 The second regularizer we consider the log-barrier regularizer with adaptive learning
rates, developed in Wei and Luo (0188) Ito [202]]. As we show in this paper, although the strong regularization of the fog-barrier can introduce an additional OVylog T) multiplicative factor in adversarial settings, it ensures strong stability of FTRL.
Episodic MDPs with aggregate feedback. Recently, MDPs with aggregate feedback have received growing attention. For example, in tabular MDPs, aggregate feedback has been studied in both the
stochastic and adversarial settings (see [Efroni et al. 2021 Cohen et al. 2021 Chatterji et al.) 2021 ). as well in the context of policy optimization [aaccwicci and Mansour] 2025 Similar interest has emerged for linear MDPs as well (see [Cassel el al.) (024)). However, to the best of our knowledge, our work is the first study best-of- best-of-both-woofe both-woordds guarantees the setting of aggregate feedback.
Remarks in comparing results
Remark (On the scale of loss). In existing studies on online learning for MDPs with adversarial losses, it's common to assume that (((s,) E [0, 1] for all and Such setting is reduced to
21

---

setting by scaling the losses by factor of L/L, which therefore can be regarded as a special case of our setting. If the loss is given by this reduction, values of losses have the same scale of O(1/L) for all layers. In contrast, in our setting, the losses may have different scales (possibly > L/L. for each layer, which can be interpreted to be more general.
Remark 2 (On online shortest path problems and episodic MDPs). The online shortest path problem can be interpreted as an "almost" special case of episodic MDPs with known transitions, but it is not necessarily an exact special case. Intuitively, the vertices v E V in the shortest path problem correspond to the states 8 E S in an MDP, and selecting one outgoing edge e E 04.0 from vertex corresponds to choosing an action a E A in the MDP. The shortest path problem however differs in several aspects: the set of vertices V does not necessarily have a hierarchical structure, the number of edges in path from the source to the sink is not necessarily fixed, and the set ô_ of outgoing the vertex Therefore, the shortest path problem
edges available for selection can vary depending cannot always be directly interpreted as an MDP. Consequently, regret bounds for MDPs do not immediately translate to results for the shortest path problem. We therefore provide a separate discussion on the online shortest path problem. However, the overall framework for algorithm design and analysis is similar to that for episodic MDPs with known transitions.
B
Auxiliary lemmas
B.1 Lemmas for FTRL
B.1.1 Stability terms for one-dimensional functions
Lemma 5. Let o: R2o -> R be defined as ((x) -2v/ and Dz(U.x) be the Bregman divergence associated with Φ, i.e.
Vx (Vz v5)² Do(y. -2/1+ + 2/z + Tz -x)
1
1
Then, for any x E (0, 1). E R and n > 0 such that n > -1, we have
{ {e. (x y) 17
1 -o(cu.00)
12312 It nevi
sup vE
Proof. We have
e. (x
y)
-D((,,)=
=
")
1
((2/7- 2/ +
22V
Vx
1
+ +ml
(x - v)
-1
1
1
2
7
y/
Vx
+ +n8
V
+ ml
V1/
Jo + nex
1
-1
1
)
2
1
+ mp -1
y
V
+ nne)
+ n/
+
- vx + ner
7
1
-1
+ me)
- V + ner
7
V
Vā
1
- 1 + +VvV)
711 (1+np(5)) (12Px)
VI
" (1
1+ n
Lemma 6. Let > 0 and B > Suppose that Φ= : Ryo + I. is defined as o(x) -2 -22Vo-$lnn (-Vr-Bll(>) (z().
Let Doly, x) be the Bregman divergence associated with 6o Then, for any x E (0, 1), l E Th and such that xē 2 2. we have
2
sup {e- (x- (0.1)
-) y) - Do(u, S 3/2
(12)
22

---

Proof. If & 2 O. it immediately follows from Lemma 5 that the left- hand side of (12) is bounded by
nf= from above. We next consider the case of < 0. The derivative of e (x y) (v, x) in y is given as
1
B
8 y
glv) -
T
This is monotone decreasing function and hence the maximum of l. (x - y) - Dølu, x)) attained at y" E Ry such that g(y") = 0. As we have
B
B
+
tx
B
S-++
B+ Ex
3x
I
and
+ +ne)
-
-2
l
+ tne
1
0,
V
we have
B
( 1/
+ +(²
)3}
-2)
3º S min
J.
S min
2x, Vx
+ rpf
B +
Px.
Vx
{ 2, (1 npe V 21
= x min
where the last incquality follows from the assumption of lx 2 - We hence have
sup
EE (x y) Do(u, S -((y" x) - -Doly" , 5 -ly" xx)
vE(0,1]
- min { 1, 7l(1)) -2
-11 -1.
(13)
I < -IVI S 1/2, we then have (1 + npl
15 -6yt which implies that the value of 13) at most -lx (-6nk = 67 3/2 II -nEVI > 1/2. we then have the value of 13) is at
most - 21 x)) = 2/22 This completes the proof.
Lemma 7. Let Φ : R>0 - TR be defined as ((x) = - -lo((>) and Do(y, be the Bregman divengence associated with i.e.,
Doly. x)) = - llog y + log + - (y (y- x) = log
y/ + y
1.
Then, for any (0, 1), E R and n7 O such that mrl > -1, have
sup { l. (x y) Do(3,x) vE[0,1
1 x))
1 (-log -xz()= + mxl).
"
11
Consequently, if nex 2 -, we have
e. (x v) Do(u. } $ nx²6 (1
+ Ije < 0) -elle s 22222
sup v
Proof. We have
L (x y) 1 Do(
1 17
y + x
--++ - + ne) (o v1)
=
log
For fixed x, l and n, this value is maximized when
1 + nL. We then have
8 (x y) 1 Do(u, = 17 1
1 (-
log x +
(-log (1 + rp() nzl).
17
y
17
23

---

As we have log(1 +a) + 2/²² + I[a <
0]
|a| for a 2 -1/2, we have
e. (x y) - - D x)
1
(- log (1 + +mxrt + +nrlf)
7
"
1
$
2
(nxr)) - -I[e < 0] inxel(3)
"1
nu²
_
+ +I[e < <0) mprlefe)
n
Proof of Lemmal 7 We can show this by backward induction in layers. For 8 8T., is clear as both sides equal to O. For E Ss with k < L,
Q" (8, a(s,a) +
Σ
u) (8:
8'ES++1
QQ - (x; +
Σ (())(s,0) (vd())
S'ESt+1
={(s,a) + Σ (6)) (x(xt))+++++++ E P( (v)
S'ES+1
6'ES441
=(ss,)) - -V" +
Σ P(s'ls,a)v** (8':)
RESt#1
=Q (s, VT (s;
where the second equality follows from the induction hypothesis and the definition We hence have
V (s: = Σ 2'(als) (s,0; >'als)) (Q- (s, a; - = va (s; - ("(
aEA
aEA
C Online shortest path problem with bandit feedback
In this section, we analyze our algorithm for online shortest path problem. Specifically, we prove Theorems 4 and 5 which together directly imply Corollary T in the main body. In addition, prove our lower bound result Theorem G
C.1 Notation and problem setup
G (VU 9s, E): directed acyelic graph.
Source node.
gi Sink node.
V: Set of vertices that are neither sources nor sinks.
E' C (VU {s}) x (V U (g))): set of directed edges.
e_,e+ E V U {s,gh g) initial and terminal vertices of an edge E E, i... = (e_,e+).
0+r C E: sets of incoming and outgoing edges of a vertex v E V U (8,g), i.e.
=_v= EeE E e+ v). 0.v {e E E e_ = v).
= V..
EE.
P S (0, F: set of (vector representations of) s-g paths.
24

---

= conv(P) S
[0, 1]:: set of s-g flows of value 1, equivalently convex hull of
Note Q {
[0, Exca, {(e) Eeeo_g q(e) 1, EeEeo q(e)
Eneo, v (Ve E V)}.
L m S + 1: maximum length of s-g paths.
Without loss of generality, assume that every vertex V admits path from passing through v.
In each round t E [T], environment chooses & R and then the player chooses Pt P, after which the player observes feedback E [0, 1] such that Efc pt] = (ft, pt). We here assume that satisfies p4, for all p E P. The performance of the player evaluated in terms of regret defined as:
T (l.Pr - 13)
(p")((")) =
Σ
Regr =
max Regr (p"), prE
where the expectation is taken over all randomness arising from the environment and the algorithm.
C.2 Algorithm
The algorithm updates qe Q by an FTRL approach and picks pe P so that Elpr 1u] qc. following the technique of (Maiti et al. 2025].
In the following, for q E Q and E V. we denote
a(v) Σ g(e)= Σ a(e)
(14)
eE04v
for the notational simplicity. Let Pv P an s-g path that passes through v, i.e., Po(u) 1. Define qu E Q by
1
qo
Σ
Pv.
(15)
M
VEV
We then have (v) 2 1/[V| 1/n for any V.
Define qe by
Σ e + v
lt E arg min
(16)
QEQ
where 2, is an estimator for e, defined later. The regularizer dh is given by
v)(9))
2
Σ
Vale)- Σ
Iig(e) with T = Vt ==
or
(17)
1tt
CEE
CEF
()(1)
1 (e(e)
In Ing(e) with me(e) (4+ In Σ (c))
(18)
EEE
where E [0, 1] will be defined later.
Based qi Q, we pick p. P in the same way in (Maiti et al. 2025
Initialize p E E by p(e) 0 for all E E and set v
8.
While A g:
Pick e E 0.v with probability qe (c))/(()))
Set p(e) 1 and transition to the next node e4, i.c., e+.
25

---

We then have Elpalqi = ge. After outputting pt. we get feedback ea [0, 1] such that Elcalpe, (c) (lt, Pt). Based this, define l, _ by
(p(le) pr(e-)) q((e) (g(e)) qi(e_)
(((e)= = a.
(19)
Note that the notation of (14) applies to p E P S Q as well, and that pc(u) if and only the path passes through the node n. Then, it holds for any q E Q that
(r(e)
pr(e_)
(2..9) =
{(e)
(c(e) ge(e_)
cEE
(t(e)
prle-)
((e) Σ
rEVUfa) qe(e_ 9(()
Σ
(E = U 0+r)
ct
(((e)
BEE
eEVufst
Pt(e)
Pe(u)
FEE (((e) ((e)
vEVU(S} 9c(w) g(v))
E
(e E 24v = n, 14)
Pa(e) l((e) g(e)
Σ pc(v)
((v) -
(P+(s) = =4((8) =g(s) 1)
-EV (((
NEE
(20)
We note that, an alternative definition of &, given as
Pr(e) (c(())
(e()+)
(e())
(21)
go (e())
also satisfies 20 similarly, and hence we have
(2,.9) (2..9)
for any q E Q. Therefore, using 2 in (T) instead of Eo in (19) does not change the behavior of the algorithm.
We now state the following that can be proved in similar way in Maiti et al. 2025
Lemma 8. For any q, g' E Q, we huve
E K df) (e, ea] (6e, - -
where the expectation is taken w.r.f. Pt-
Note that the effect of the path-length does not appear here. That is, we do not need to assume that the path lengths are the same.
C.3 Regret analysis
Definition 2 (consistent policy). Define II = { ( + E T(V) E 0,v (Ve V {s)).
Let E P be an arbitrary 8-g path. Let E* C E and V C V denote the sets of edges and nodes included in p", i.e., Ex (e E (e( 1] and V {u E V p²(v) 1}. We say n" E II is
consistent with p² E P if and only (v) E E" for all u V*U(s). We denotes E' = E' Im(=").
Definition 3 (self- bolff-buunding regime for online shortest path). Let p* E P be an arbitrary s-g path and suppose that n' II is consistent with p². Suppose that A [0, 1 satisfies A(e) > 0 for all e E F. Im(=*). The environment is in (p". n=,, A, -.)-)seff-ouuddiii regime if it holds that
T
Reg (p*) 2 E
Σ Σ
Σ
A(e)p((e) -C.
(22)
1=1
vEVufs) aea, ((
26

---

Remark 3. An example of A E [0.1] can be constructed as follows: Assume that & follows an identical distribution independently for all E [T] and denote &" E. For each u, v VU {s,g), let dist(u, r) denote the length of u-v shortest path w.r.t the weight e*. (Set dist (u, (u, v) = +00 if there is no u-v path.) For each e E E,, define A E [0, 1) by
A = ( (e) + dist(e+, g) dist(e-.g).
(23)
Then, if p- E P is shortest s-g path, then (2) holds. In fact, for any s-g path p E P expressed as sequence of (s = Uu, 61, 01, C2 22,
Uh Cha = Un), we have
h
(A,
Σ
(()) = Σ (e + dist(u). cist((1g1199)
j=1
h
Σ
E² (ez) + dist(vn. 9) dist(vo. = (E: (8" ,p"),
which implics Regr (p*) = E E (A. Suppose H² is chosen so that at (1() e arg cea (e()) Then, A(e) for all E' E Im([t) if and only if the shortest u-g path is unique for all v V (s}.
Remark 4. An issue of the definition of A in 23 is the requirement for strong assumption that the v-g shortest path is unique for all u E EVU {s) to ensure that A(e) > 0 for all e E E'. We can relax this assumption by some alternative definitions of A. When using the following definition, it suffices to assume that the s-g shortest path is unique: Define L' = maxper (E p(c)) S L. For e E E'
and & [L']. define P(e, k) E P and Á(e) by
p(e,k) = PEPl p(e) = Eplc') p(c')= = =k]
e'EE'
{1 inf pEP(e))
p²)) p>))
1 inf I
((e) min kE(L) k
((CD--'))
min kE(L)
(24)
pEP(),))
We then have En Á(e)p(e) S EEERy A(e)p(e) for all P. which implies that the environment in (p", x"" x;; Á) as well. Further, as we have p² & P(e,, k) for any e E E' and k. we have
1 min [(e" p - p0)} : Amio (m")
((e) 2 L
for any E E'. Hence, this value is positive as long as the s-g shortest path is unique. We also have (e)) minegg A(e) for any E E'.
Let go e Q be such that (o(e) 2 1/m. For any p' E Q and s E [0, 1]. set q" by
g" = e1 + EQU-
(25)
Using Lemma and standard analysis for FTRL (see, e.g., Exercise 28.12 of [Lattimore and
Szepesvári 2020 ). we obtain:
Regr (p") = Σ (tsPt - 2²)
E
Σ
T
Ceespe
v²) -p-)
E
Σ (G -
-pi) ri)
T
(le. qi - -3>
T
(l,, qu pr)
T
El,, q: - s²) + ET
+ +&E Σ
$ E
T
< ET +
(te. ---(444))
Delget1, 9)) + (vi(q") v)rr((9)) (9)) + (
1=1
=istab.
=ipena,
(26)
where D+(..)) represents the Bregman divergence associated with v defined by 17 or 18 and we set (g) = 0 for t = 0 as exception.
27

---

C.3.1 Analysis for Tsallis-entropy case
Theorem 4 (First part of Theorem D. Letp' E P be an arbitrary 8-g path and suppose that x² E II is consistent with p". Then the proposed algorithm with the Tsallis-entropy regularizer 17 achieves:
(egr(p")
E
Σ
E
Vale)+ E
Va((=(u)) "EViV"
+ m molog (27)
Vt
1=1
(EVV((s)
cE vE
E
Σ
E
Vq(e)+
Σ
Σ
q((e)
+ m log T
(EVVU(s) (=)(")(T(()))
NEV*U(s) (Tr
(28)
Corollary (First part of Corollary I. In the adversarial regime, the proposed algorithm with the Tsallis-ent entropy regularizer (17 achieves Regr O(vmLT + m logoT) Further, if the environment is in a (p", n², A, -e-slff- boffdfiguniigg regime given in Definition 3 VUC + m log T, where we define
we then have Reg, (p') S U
== Σ Σ
log
+
n² log T
(29)
A(e)
A
vEVU(s) eEd (())(())
A min (A(e) Be E
(v)))
(30)
In the following, provide proof of Theorem
Lemma 9, When we use the Tsallis-ent entrrpy regularizer
stability terms are bounded as
Elstab,] S E Tt Σ
Σ cE0++
Vai(e) Va(u)
SE E
T Σ
Σ
Vg((e)
rEVUfs)
rEVU(s) cEd (m)
(31)
Proof. To bound the stability term, we can apply Lemma 6 with 8= [ee,, (e)., n= 7h and (((e)
2. fact, we can verify that -Ee(e)qi(e) S
qu 2. Hence, from Lemma we have
(2e, - -9-1)
1 D(g(41.9)) 9r) 9:) Σ (21 (Eo(e))
Th
cEE
Pr(e) pr(e_))
S Σ (21
(e(e)
(e(e_)
eEB
(p((e) (e(e-) 2
Σ
Σ
(gele))3/2
3/2
(E = Ubevuss) 040)
(((e) (((c))
vEVU(s)
(r((e) pe(v)) 2
= 1/ Σ
Σ
(/1l)))312
(e 04r = 6- =)
(e(e)
-1 (e(v)
cEVU(s)EEa
(v(
(r(e) 3/2
(p((e)a(()) (i(e)
2
T Σ
(((l)
(v)
vEVUfs)
e
28

---

where we used the fact that Pe(v) = implies pi(e) 0 for E d4v. Taking the conditional expectation w.r.t. Pt given Gt, we obtain:
-11 ( 27
(v)
(x(e)
pr(e)ax(u)
E
Σ
(v)
(c(v))
(c(e)
e
qi(e)
-110-11) pc(e))i(U) -1) (p+(v) =1
(((())
Qe(w))
2:(e)
cE
(r(e)
3/2 ge(e)
(((1)
-1) + (1- ge(e)
V
(1(T))
(((T)
(c(e)
qe(v)
e
Vv(u Σ
qc(e) 1/2
9:(c)
Σ Veole) (1-
ge(e)
(t(v))
(((w)
gc(m)
"
"E
Further, as we have (1 - x) - 2(1 - vi) for I E [0, we have
Σ Vq((e) (1 1 4((c)
1 (c(c)
E g((e)
2 Σ Va((e)
Σ Va(le)
qc(v)
qc(v))
e (r)
e v
cE
=2 Σ (e) (v(v)
Σ V(((e) va(c)
(v)(
cEd+v
rE0+7
By combining the above inequalities,
E ( ((+1) -
1
-D S Σ
Σ Va(e)- (000)Vaa()) Va(o))
7/e
vEVU(E}
cE0+0
The second inequality in (31) follows from the fact that (e) S (e(v) for any e E d4v.
Lemma 10. Let p" be path consisting V E EV and E C F. Suppose that q" is given by
25
For t 2 2, o² is path consisting of V* E V and E" C E, penalty terms are bounded as
pena, S 1/.
Σ eEE
Vgle)
EE|
me
11 T Σ
Va(l) me
BEFAR
Σ
Σ
((ee+
Σ
Ve((x<(())
+ me
(32)
vEVU(>)
VVVIV-
In the case oft = 1, the bound includes an O'm log(m/s)) term in addition to the above.
Proof. Suppose that 2 2. We note it follows from T) 1/v2 that have
O(e)). We hence
mr
pena, =
1 1
Σ
Vaile) (e S 1Jt
V Va((e) (c(())
M1-1
cEE
e
$ 1/1
(a((e) - (pr(e)+e) -8 =
Σ
Va((e) - FE* | + ms
3EE
LEE
<
Σ
Vq(le) + ms.
BEEVE-
The equality in 332 follows from E E" ='= (Unev((s) (04v ( (V) V*). In the case of I 1, the penalty term includes an additional term of
3 Σ (In(a((e)) In(g" (e))
<
Σ
In (e) S m
log )m)
cEF
e
which completes the proof.
29

---

Lemmas 9 and I0 combined with 26 immediately lead to 27
Given this, the next step to
28
follows from the following lemma:
Lemma 11. For any e E V V and any q E Q. we have
((v)
Σ Σ (()).
(33)
(EV-
Proof. As Q is a convex hull of P and both sides of 33 are linear in q. it suffices to show (33 for E P. Then, for any E P, if RHS of 33 is positive, then it is at least 1, and hence (33 holds. Therefore, suffices corresponds to the sequence of (s vu, 61, ....... Cb2 In fact, we can show this in induction
show that RHS
= LHS 0 for E P. Suppose
g). If RHS 0, then consists of
V fui...., 2/-- g) and E* (T²( (=)
j, under the condition that E (o') ((e) 0 for all v' E V U ((03) =
Erea oj g(e) = - q(T (vz)) = 1 ((0)t1)= =.
Proof of Theorem 4 We choose E [0, 1] in the definition of q" in (25). Then, Lemmas 9 and 10 combined with (26) lead to 27 The other inequality (88 follows from
Σ
vg((T((v))
Σ Vq((t) Sn -V
Σ
E
qe(e),
VEVVV*
VEV- (f
where we used Lemma in the second inequality.
Proof of Corollary 3 As have EeEr (()) L and Evev ((v) s L for any Q, from the Cauchy-Schward inequality, we have
Σ Σ
Vale) S Σ ((ee) &
E Σ (e(e) S VmL.
vEVU(a) eE8+
eEE
eEE
and
Σ Va(u) S Va(u)s
I Σ ge(o)= S VnL.
VV
NEV
NEV
Combining Theorem with this and Σt= 3 S VT, we obtain Regr S VmLT + m log T. By using the Sauchy-Schwar inequality, we obtain the following:
Σ Σ Σ
Va(e)
Vi
vEVu(s) eeo, v)(
Σ
Σ
A(e)q((e)
t vEVU(s) cEa, ((Tr((())))) VA(e)
Vi
Σ
Σ
Σ
E
((c)g(())
Vt
A(e) V rEVu(s) eE (o))
vEVuist ol
Σ
Σ
Σ
Σ Σ
A(e)
A(e)
rEVU(s) rEd (((T*(()) (m)
vEVU(s) cEd (((((()))
30

---

Similarly, we have have
T
Σ
E
q((e)
Vi
(eVu cEd_ el (x)((()) (o)}
T
12
Σ
Σ
ge(e) log
vEVU(s) (E0+ri(T(())
n
Σ
Σ
le)
eEVu =E
Hence, from Theorem Jensen's 's inequality, and the assumption of self-bounding regime Defini- have
tion g
T Σ
Regr(p")
U
Σ
E
A(e)a(())
m log T
[=l vEVU(s) eEA, (v))
< U (Regr(p") + C) + m log??
$ VU (egr(x") VUC + log T
which implies Regr(p)) (p") $ U + VUC + m
C.3.2 Analysis for log-barrier case
In the case the log-barrier regularizer, we have the following regret bounds:
Theorem 5 (Second part of Theorem The proposed algorithm with the log- regularizer
18
achieves:
(r(e) qi qi(t)
Regr S
E
Σ
Σ
Σ Ccp((o) (plee)
log(T)
+ m log(
(EV cca..
Corollary 4 (Second part of Corollary log-barrier regularizer (88) achieves
D. In the adversarial regime, the proposed algorithm with the
Regr E
mL
Σ
log T
mL log T
min E
Σ (le
S <vm.T.
(34)
PePP
(egr("")SS + VUC + m log T, where we define
U= Σ Σ
log T A(e)
(35)
vEVU(s) eEd, (x)
To show these, we use the following lemmas: Lemma 12. When we use the log- fog-barrier regularizer (18), we have
Σ ne(e)p((e) (pe(e)= (:(E)
stab, 5e Σ
(((
vEV
31

---

Proof. As we have (1)2(c)&((c))
I
qı(e) qcle_
S t - 1/2, we can use Lemma to bound the
stability terms:
stab, x Σ El(
(r(e)) pr(v)
= Σ
Σ
n(e)(a(e)))
q((e) 4e (e
VEVu(s) e60+0
gr(e)p((w) (e(v)
= c E
Σ
ne(e) Pr(e))
revu(s] 260+v
gc(e)
Σ
Σ
ne(e)p(())
(p((e)
qt (c(
nEVU(s) c702v
where we used the fact that q(v) = 0 implies q(e) = 0 for E O+ (v) and for any E Q.
Define (e(e) by
(((e)
pile) = cpp(c-)
(pi(e) -(p(e)
ge(e_)
Define q² by 25 with e = m/T. Then, from 266 and Lemma 12 we have
T
(p") S m (4") E
Σ ne(e)p(e)+ +
Σ log
+ m
(T(e)
(e(
1=1eEE
eEE
(()) + Log(T)
) mr(e)
E
3EE
1=1
T
S
E
(e(e))og(MT))
+ +m log(')),
EEE
where the last inequality follows from the setting of me (e):
t-1
-1/2
(e(c)= +
Σ pr(e)
log(T)
This completes the proof of Theorem 5
32

---

Proof of Corollary 4 We can show (4 by using the Cauchy-Schward inequality, Jensen's 's inequality. and the fact that Le Pe(e) I L. The other one can be shown via the following:
go(e) qe(v)
E Σ Σ
Σ (pp((v) p((e)
NEVU c
Σ Pa(u) pr(e) (((e)
Σ
E
(v)
vEVU(s) cE
9:(e) (1
1 q((e)
Σ vEVU(s) c
Σ
E
Σ
(o(u)
T
[ (((e)
T
q (v)) (1 (e( (w))
E
Σ (((e)
(c(v)
ge(v)
eEVU(s}
T Σ [=1
Σ
E
(e)
+
E
(g:(v) 2: (x= (w)))
vEVU(s)
1EE 1e68 (v)
2 Σ E
Σ
(e
(EV rEO,pl
Hence, by using the condition of the self-bounding constraint Definition
we obtain
T
Regr(p')
Σ
E
E
(e
log
+ m log T
wEVU(s) eEO, (v)
Σ
Σ
V
log T Ale)
E
((e)
T
(e(e)
+ m mogg' T
eEVUfs} CE0+e)T (v)
Σ Σ
log T A(e)
E
Σ Σ
A(e)
Σ
vi(e)
+ m log T
CEO (()
[EVUU) cE0 v(rT(()
1=1
log
Σ Σ
Regr (w*)+ +C mmm+logg mog
Ale)
DEVU(N) eE (\(= (1)
VURgg (p")
VUC + log T.
This implies that Regr (p") $
VUC mlog
C.4 Lower bound for stochastic environments
As our problem is special case of the linear bandit problem, we can apply the lower bound given by [Lattimrre and Szepesvari 2017 Corollary 2], which is characterized by the following optimization
problem:
A(p)
inf aE|
Σ app) subject PEP-
where p- =P arg min pEp (E", p) A(p) = (e* min (e*, "r,,p"), and
H(a) Σ a(p)pp T.
PEP
33

---

However, deriving an explicit expression for the optimal value of this optimization problem is not straightforward. fact, we have not yet identified such an expression. Instead, in what follows, we present lower bound by exploiting the specific structure inherent to this problem.
Consider stochastic environments specified by L" such that (f",)) E [3/8, 5/8) for all p P. We suppose that Cr E {0. 1 follows a Bermoulli distribution of parameter (t), Suppose that A is defined as 23 We then have (L",p) .p) min (E", .p'pp) (A. Denote
A(e)
min pEPay(e)
(().
(36)
Theorem 6. Consider an arbitrary consistent algorithm, i.e., assume that there exists & (0, 1) such that Regr I MT holds for any instances, where M > 0 is a parameter independent of We then have
Regr Z log T
A
lim inf T-00
Σ
(37)
A(e)²
cEE:(())>0
Remark 5. If A given by (3) we have A(e) A(e) for E 04v where E V = {0 E V
dist(s, v) + dist(e, g) = dist(s, s, 9)}. In fact, for such an edge e, we have
(e) = dist(s, e-) + ((e) + dist(e+.g)) dist(s,g) = (e) + dist(e+. - dist(e-,g) = A(e).
We hence have
Σ
E
E
A
Σ
E
A(e)
A(e)
(C):
(EVU(S) cEO,, (()))
VEV=U(s) e()))0)
Proof of Theorem
pe E (1* p)}. As have
Regr E
.t p²)
Σ (e", , pz)
A())
Σ prle)
we have
lim inf
Regr log T
Σ
A(e)
lim T-
Σ Pc(e)
(38)
T
log
T
cE
In the following, we evaluate the value of lim inf log E
Et= [r(e)] for any fixed E
such that d == ((E) > O. Consider a modified enviromment given by É such that ((ē) (²) 26 and é(e) E (e) for + ē. Then, we have p" (é) = 0, it holds for any P that
(i.p-p")
(E" .p p²) 25(p(e) (²))
(A,p) 28(p(e) (e))
2 8p(2) - 20(((e) pp" (2)) = -ōp(E).
(39)
where the inequality follows from the definition of 8 A(ē) given in (36). Further, as there exists E P such that p(e) = 1 and (A, p) = 6, we have
min PEP
(p - pr) < 6 25 5.
(40)
Hence, from
39 and 40 the regret for the environment given by i satisfies
Σ (i. P) 2.. E
T
T Σ -a-piis m(())
Regr
max É pEP
(41)
where E[-] represents the expected value when feedback is generated by an environment associated
with ?. On the other hand, the regret for the environment given by 8* satisfies
T
Regr = E
Σ A. pe) t=/
2- E
Σ
(e)
(42)
34

---

Let TV denote the total variation distance between trajectories c)) for environments with f" and é. Then, have
T
Σ
Pc(E) E [0. 1], we have
T
1
E
(2)
E
Pr
(E)
STV.
T
T tm1
1=1
We hence have
T
T
TV
1 - E
Σ P+(e)
+ E
Σ pr(e)
T 1=1
T
1=1
1 T
E
(e)
+ E
(e(e)
T
T
t=1
Regr + Regr)
8T
where the last incquality follows from (11 and 42). Here, from the Bretagnolle-Hube inequality
(c.g.. [Canonne
[2022], Corollary 4]) and the chain rule of the KL divergence, have
E DKL (1e like, (10..))l(...)))
TV 2 exp
2
E (pe(é) DEL ((e pp) l1(e" .P)) 26)]
exp
1=1
T -502. E
Σ Emtel)
exp
Combining the above inequalities, obtain
T
1
8T
(e)
log
2
log
8
2(1 - TV)
82
2(RegT Regr)
8T
8
0
log
4MT1-6
=
gz
Elog T + log
4M
Consequently, we have
lim inf log T
E
Σ
(t)
8
((2)2
for any ē e E such that (@)) By combining this with (38) we obtain 37
D MDPs with known transition
In this section, analyze our algorithm for episodic MDPs with known transitions. Specifically, prove Theorems and g which together directly imply Corollary 2 in the main body. In addition, we provide our lower bound result in Theorem
D.I Algorithm
The algorithm's construction is almost identical that of the shortest path case. The unbiased loss estimator is defined in Lemma
35

---

For notational simplicity, we omit the conditioning in expectations throughout this proof. Fix an arbitrary E Sy and a. We then have
Proof of Lemma 2
(ss, a) 91 (3,00)
T- (ss a o)
E
Ct
E
- E
Σ
{(s), at)
(sh, a (s, a)
E
[(s a
E
Σ i=
( at)
11 s
EEB
Σ
A(s)
af)
8/ =
(s,
Similarly, for any fixed & Ss, we have
I((s)
L-1
E C: (1(s)
= E
Σ
((s) a
$ =
= E
e a s/ = + (s:
=0
By combining the above two equalities, we obtain
1,(8, a) q((s,a)
[s()) (())
E [2(6,,a) = E
E
Q (s)a);;)))))) (s;
In the following, we denote
&
E
Ee Te, Es]
(=* (s; []
By combining Lemmas
1 and
2 obtain the following expression of the regret:
Regr(#*)
E
v (80: Ee) V (o0(00;;))) (x)
VT (su: Ee) V (ou: Ei)
E
E
(Ee, g¹)
(2r ot)
E
(43)
where we denote 9² = q"t To upper bound the value of Σt (
--"
we choose E by
using the following FTRL approach similarly to the case of online shortest path problem:
Gt E arg min SEQ
Σ
Er.9 E
+ v0l0)
where
()(g) Th.
Σ Vq(s,a) -
Σ Blng(s,a) with 1) = Vi' 3 =2 2, or (44)
sFst,GEA
(g) Σ
In ()) with ne(s,a) (4+ In Σ ()()a))
- (45)
()((sa))
where p. [0, 1] will be defined later.
36

---

D.2 Regret analysis
In our regret analysis, we use the following lemma:
Lemma 13 (First part of Lemma 4). If fe is given by as in Lemmal the expectation of ((s, a)2 taken
w.E.t the randomness of satisfies
1 (e(as)
Ge (s(s, a)
Proof. For notational simplicity, we omit the subscript throughout this proof. From the definition of l, we have
E [ss s s(()) i(als) (1 1 ) + (1
T(als)) (1--T(lss))
(((3a)) {(s)
g(5)2
q(s)
ass,a)² (T(a)s)(L- =(als))
((=ss)))) + (1-xx(ls))) (alls))
q(s, - -1 1 1-
((s)
(s,
We also use qo and q", which are defined as follows in the analysis: For all s E and a E A, let
(s.a E arg ye d' (s) Define do E Q by go = S| En, taa For q² = q² and & E 1). define q² by
q = (1 - 2)4² + EqO-
(46)
Then, holds for any q Q, 2, S and that
((s,a) a)
q(s a) go a)
|I||A g(s, a)
I |S||
(47)
(5,
E (,,a(s,
From 43 by a similar way to (26 we can show that
Regr( (T) S ET +
E
(le. 9441) De(gc+1, (vi(g") -/--1(0)) (b( =istab,
1/2
(9)))
=:pena,
(48)
D.2.1
Analysis for Tsallis-entropy case
Theorem 7. For any deterministic policy nt I1, the proposed algorithm with the Tsallis-entropy
regularizer (44) achieves:
Regr(T")
E
E Vg) +
LIS|IA| Σ
Σ
+ +||||A| log T
eoEL (*)*(()
efol (f)
In the proof of this theorem, we can bound the stability term by using the following lemma: Lemma 14. When we use the Tsallis-entropy regularizer 17h. stability terms are bounded as
E(stab:] S
E 1Jt Σ
Σ (*))(()
Va((s,)) v(((s)
Tr Σ
Σ
Vae(s, a)
efoL
(
(49)
This can be shown in similar way Lemma 9. by using Lemmas and 13 Furthermore, the penalty term can be bounded the same manner done by Jin and Luo 22200] using their Lemma 6 with 0. By combining these results, Theorem 7 can be established in the same way as Theorem
37

---

D.2.2 Analysis for log-barrier case
In the case of the log-barrier regularizer, we have the following regret bounds:
Theorem 8. For any deterministic policy x², the proposed algorithm with the log-ban log-barrier regularizer
achieves:
Regr I
E
Σ ST8L (s)
Σ (L(ss) - =e(als))² log(T) log(T)
+ |og)))
(50)
To show these, the following lemmas:
Lemma 15. When the log-barrier regularizer 445 we have
stab, Se >EEEEE
a (T((s =e(als))²
8581, aEA
Proof. We have
stab; (le. 9: -9(1191111 De(gc+1.99)
Σ (((s,a)()((ss))) -2+1(s,0)) m)(s,a) D (
where D3 is the Bregman divergence associated with ø(x) = - -In(x). As we have
(ss.a) ((ss)) g((s)
S a) 2
we can apply Lemma to obtain the following:
stab, Σ a) (s, Σ ()() =r(als))²
Define (r(s, a) by
(+(s. 2
p)(s,a)= = ccl((s) ((((())))((())
[1(ss,))
(8)
Then, Thcorem 8 can be established in the same way Theorem 5
Lastly, results in Corollary 2 follows from Theorems andd g by an argument similar that used for Corollaries B and 4
D.3 Lower bound for stochastic MDPs
Consider stochastic environment in which follows Bernoulli distribution of parameter (e", pt)) where we assume that E" S -> [0, satisfies (E", .p) e (3/8, 5/8] for any possible trajectories p and (SL. a) 0 for all E A. Define A : S x A + [o, 1] by optimal Q function values:
(a A),
(s, = (s, + Σ P(s)ls,a).V'
(s S { A),
V*(s) = min Q* d'EA
E
A(s,a) = Q" a)
min Q (s, a') = (s, (s)
(s S, A).
a'EA
38

---

We then have mAn ((s,a) 0 for all E S and |Al S 1/4. Also, we have
1-1
(f: = Σ
((),)))(s.a)
0= aEA
L-1
EE
Q'(s.a)- E (ills,))VV(())
g(s,a)
sE aEA
5'ESNI1
ΣΣ ('ss
E ((5)) (16)).1(66)
RES REA
2'ESKI1
Σ
Σ
(Q' (()6sa)- + (s0) (SL)
SE REA
= A g) + min (E", .9")
as (sL) = ( (st, 0 for all E A. Denote
Q- = arg min {(e", .9) = arg min {(A,)) g)}
TEΩ
{ O (A,g) 0} {q E Q A(s,a) > 0 = g(8,a) = =0}-
We also define
8 = E {1L) 39 E O* 2''(()) > 0}.
Then, for any consistent algorithms, we have
Regr logT
Σ Σ EE
lim inf
T
SES' dEA:A(s,a)20 A(s,a)
Theorem Consider an arbitrary consistent algorithm, i.e., assume that there exists e E (0, 1) such
that Reg, S -T holds for all instances, where M > 0 is a parameter independent T. Then for any MDP with 6 S x A + [0, 1] satisfying (e*, E [3/8, 5/8) for any possible trajectories and 8* (SL, a) = for all E A, we have
inf
Regr
Σ
Σ
(51)
T-
log T
A(s,a)
SES aEA:)())))20
Proof. Let o² E Q², As we have
T
T
T Ass
Regr E
(e", Pt. - 9²)
= E
(e", 4t 9²)
= Σ
Σ
(
3,a
we have
Reg. log T
li T-000
Σ a) liminf
E Σ vc ())
(52)
T-x log T
8,0
In the following, we evaluate the value of lim inf log T
ge(3, a) for any fixed 5 e
S* and à E A such that 0 A(5,a) 0. Let q" E arg argmaxxeee {s(5)} and denote q
max,e2: (n()) = q (8) > 0. Then, from Lemma 16 below, there exists c E (0,8) 8] such that
(A.g) 2 emax(0, g(5) / + Ōq(,aa).
Consider a modified environment given by i such that ((5, ā) (5, - c/2 and E(s,a)
(*, for (8,a) a) * (3, a). Then, as we have 4 (3, a) = 0. it holds for any a E Q that
(1.q - q²) = (f" 9*) (6 + : (g(5,a) - a5)
= (A, (8+
c -) q(3, a) 2 cm (0) - [] - c
2 (3, ā)
2 cmaxf0, 1oaxx(0.q(3,00 a) - (9(3,)) = C
c
(19(3, q - 4)
(53)
2
2
39

---

Further, as there exists q Q such that
(2,9-9') gr)
or
we have
min
(..)) (i, gE@
07 2
(54)
In fact, such an occupancy measure 9 can be constructed from corresponding policy म S A, by modifying a policy x¹ S - A corresponding to q" Q" such that (s) q. We set F(s) = (s) for all s * and set 7 ($) à. An occupancy measure q corresponding to satisfies q 0)
and (e", .4) gö, which implies that (i.q) S Hence, the regret for the environment given by 8 satisfies
Regr max E
Σ
[L.q0 -9)
rEQ
E
Σ
(1,9t - q-)
(from 54
T
(8, ā)
(from 53
IV
Σ max {0. (r a)}
(55)
where E[-] represents the expected value when feedback is generated by an environment associated with E. On the other hand, the regret for the environment given by l satisfies
T
Regr 2 2
Σ
(5 ā)
2 28-8 E Σ min (g. (c.
(56)
Let TV denote the total variation distance between trajectories ((ye, Pt, o)) for environments with l and l. Then, we have 1 DT min {q. (c(ā,ā) [0, 1]. we have
qT
E
min (3.
E
min (a. (3)
TV.
qT
qT
We hence have
1-
TV
<
1
E
min {ū. (8)
+ E
min (q. (3,
qT
qT
t=1
E
max {0, 20(5,a)
E
min (5,4(),))
qT
qT
1
Regr + RegT
qT
where the last inequality follows from (5) and (56). Here, from the Bretagnolle-Hube Huber inequality
(e.g., [Canonne [2022], Corollary 4]) and the chain rule of the KL divergence, we have
TV 2 exp
Σ
DKL. ((E.Pi) (IE.NNIle..))) mi))
T'
(x, ū) DKa. (1e, ,p)) (1EE", pc) - 9)
Σ
= 2
exp
1=1
Σ (3, a) 1)
exp
-5
+
C 2
E
a)
40

---

Combining the above inequalities and c E (0, 60, we obtain
1
1
qcT
E
Ce 55 a)
2 82
log
log
2(1 TV)
82
Regr + Regr)
qcT
qc
log
loo T + log
82
8MTL-E
82
8.M
Consequently, we have
lim inf 7-000 log? T
Σ qe à)
2
6
82
A a)²
for any & E St and E such that ((, a) > 0. By combining this with (52). we obtain (11)
Lemma 16. Suppose that E S and denote q max {q(s)). Then, there exists e > such that the following holds for all E Q:
(A, 2 cmax(0.g(s) q) +
Σ
(s8,a)((s,0)
aEA
Proof. Suppose that E S* i Sg. Decompose A as A Ack Agk. where
(A(s,a).0) if E Urek Sk (Acu(s, A2x(s (0,A(s,a) if E Uv2t Sk
We define q-k and q> in the same way. Define f(x) (xyls)= (A, g). We then have
f(z) inf (E(:1(s)=>
(A.9) (E):
inf (Ack + A Azk: qe (EQ:0(s)=a
inf (Ack.
The last equality follows from the fact that, for any q Q (corresponding to x E II) such that
((s) = x, there exists o' E Q such that g(s) = x, (A ck. g') = (Ack, g), and (Azk) g¹) = Such (Ack, an occupancy measure can be constructed by policy n' E II given as n 7'8 a) = (s, a) for
s E Ukee Se. and 7',8,)) = n" (s, a) for 8 U>>2 Ser.
max (q())) We note that I S 9 and f(x) +oo and only if 2 < I S E. As Q is polytope, f(z) is piecewise linear function in x, i.e., there exists finite sequence of real numbers Hg = I 21 < x2 <.... < In
Define x ({))) and
E R such that f(x) is an affine function in each interval [ri, 1. I. From the definition of Q* and we have f(x) > 0 for
any x > q. Indeed, if (s)) > q then a & º*, which means that (A, ④) 0. Hence, e defined as
{ f(x)) | [n]. 24 >
c=inf inf { Iz
positive. (When F,, i.e., when there is no x; q. we let e be an arbitrary positive number.)
Further, as f(x) 2 0 for all x and f() is affine in each interval [ri, 1i1)) we have f(x) 2 emax x g for all F. From this, we have
(A, g) = (Ack. g) + (Azk.g) g) 2 f(g(s)) + (Azn.g) 2 c,))
-
Σ A(s,a)q(ss, aEA
E Algorithm for MDPs with unknown transition
In this section, we present the details for our www.ooft---ootttteooo algorithm for MDPs with unknown transitions. Similar Jij et al. [202)) our algorithm proceeds in epochs. In each epoch, we execute FTRL using our novel loss estimator and the current empirical estimates of the transitions. At the end of the epoch, we update these empirical estimates. We refer the reader to Algorithm T for full details. In this section, we use E.[:] to denote the conditional expectation E[-[Fr,1)), where Ft-1 1 the past filtration.
41

---

E.1 Confidence set of the true transition
In this section, we use the same confidence sets used by prior works Jin al. 2020 For each epoch i, we define the empirical transition P. as:
2021
P,(5'ss,a) mi(s, a,))) V(s,a,s') E Sy Ax S = 0, ...... L 1. (s)
(57)
For each epoch i. define the confidence width B, as follows:
Pi(s'|s, a) In TISIIA 14 In rIS|Ia
B, a, s') = min 2
+ ms, 1
(58)
ms,5,a)
where 5 is some confidence parameter.
For each epoch i. the confidence set P. of the true transition defined as follows:
P. P P: ((slss,a) Pi(5'ls, a) Bi(s, a, 8'), V(s,a, E Ss x A x Sk+1, k v.). (59)
As shown Lemma 2 Jf al. 2020). the true transition P lies in the confidence P, for epoch i with probability at least
40.
E.2 Loss estimator and Regularizer
We begin by presenting our novel loss estimator:
(s a) C. (s. + (1 - aa(a s) - c.) II()) [s)
-=((a [)),
(60)
we (s, a)
where uz(s, a) denotes upper occupancy measure of (s, a) under policy m., and is defined as
as,,a)
.ax of Pise (s.
(61)
PEPRO
where i(t) denotes the epoch to which round belongs. Note that u4 (s, a) can be efficiently computed using the COMP-UOB procedure proposed in (Jin et al., 2020].
To build intuition for why this estimator enables the corresponding loss estimator in the setting with known transitions.
guarantees, we now consider
E (s, a) = a as) (1 (a(s) - cx) (e()) (1-s((a(s))
(62)
(s,saa)
In the unknown transition case under semi-bandit feedback, Jin et al. 2021 considered the loss ((...))) which ensures that (, a) E, Ie(
estimator Me(s.a)
whenever ur(s,a) a) Z
Me (s..a))
(s, a). This inequality plays key role establishing their bott- worldss result.
In our setting, the role (s a) is played by the pseudo-loss (, a) = Eg a)]. When
u,(s,a) 2 ge (s, a), we show analogous inequality: (,(s, E, a)] 0, which is similarly crucial for our analysis.
We begin by analyzing the pseudo-loss Es(8, a) as follows:
(( E,
[2)(ss a))
[ Le(ss a) c. (()
[1 (s) (s)
E,
+E,
(1 <a(sss))
qe(8,a a)
Q* (s ( + (a(as))
(al(s)s)
Q (T
By Lemma 1 we have (L,, a: the role of ee in our setting.
)²) = (le, 4i 4²), implying that the pseudo-loss can indeed play
42

---

Next, we compute the expectation of (s, a) as follows:
(s(s)
E, as, To analyze this expression, observe that:
(*) (s, (* + - (al(s)))
QT V Q (s, a) Σ Tr(a' (s)(*((s,a))
a'EA
(1 mT(als))
Σ a'ya
Te(a' (s)
2 (11 - {r(ds)))
(as (= E [0, 1)
and thus:
(s (s) + +1 (a|s) 0.
Now, under the condition that uz(s) 2 (s), we have
m m1($)
< 1, and therefore:
(s(s)
E, (8) a)]
(s(s) 1Q' (s, a) - V (s) 1 (a(ss)) (1 (a(ss))
S (Q"((s (* + 1 (a(as))) (x((sss))
(s, V*(
= ={{ssa).
That is, (s, is optimistic estimator of the pscudo-loss fe(s, which plays crucial role in our regret analysis.
In addition to bounding the expectation, we also analyze the second moment of the loss estimator. This analysis is facilitated by the careful introduction of the term (1 Te(a s)) into our loss estimator, which yields the following bound:
1
E, (1) 2) S E.
(c (Lr(s, (()) ss)) (1 #e(a s)) (s) s)))
uu(8, a)²
+ (1 (a(a| ss)
(r(s)
1
+ - re(a 1))
$ (1 - m s))
u4(s) ue (1 a)
Using this bound, we obtain a control on the stability term the regret analysis:
Eg as 3/2 ( a)² as) S (s, a) xz(a s)).
This upper bound plays a crucial role in enabling a regret analysis based on self-bounding terms. In particular, it allows to bypass the loss-shifting technique employed in Jin al. (202T). while still controlling the stability term.
To leverage this upper bound, use the following regularizer in epoch é:
dc(g) = ΣΣ> Σ
Va(s,a)-8 3
>E> ΣΣwn ln)(s,a),
(63)
Tkt a
where 7)+ - and /3 1024T. The log-barrier term is included stabilize the updates, following the approach of Jin and Luo (2020
E.3 Main Result
Theorem 10. In the bandit feedback setting, Algorithm with = 75 and
IT guaran-
tees (x*) = Ô [AAT) + |S|[A\IT + T and simultaneously Regr(("))
o ( + VUC + v) under Condition 4 where V = |A and U is defined as
L In + | In L
+ (I 1 In L|S In? AMIN
U= Σ
A(s,a)
SLAL (8)
43

---

We defer the proof of the above theorem to Appendix
Analysis of BOBW with unknown transitions
For any time-step let i(t) denote the epoch the time-step is part of. Let E,I. --11 be the conditional expectation, where Fz-1 is the past filtration. Recall the definition of E and E from Eq. (60) and Eq. 62 respectively. Also recall that le E7 Buee Let & be pseudo-loss such that (((5, E, (s. QT (s, a) (s).
Now define the conditional expectation of &g follows:
gr(ss) (s(s) (Q (s, a) - + =e(als)) (ells)))))))) (s, a).
()) E, Ea a)]
(64)
Definition 4. For any policy æ. the estimated state-action and state value functions associated with Pite and loss function l, are defined as:
(s, ()) + E (1)
e (s x A.
S'ESKOH
(s) = Σ (s..),, VsES,
aEA
(st, 0, Va E A.
On the other hand, the true state action and value functions are defined as:
(8, ((),,))+
Σ
(V)
x A,
S'ESx(H41
(T) = Σ r(a]s)Q](ssa) As
a
(st, = 00 Va E A.
where denotes the true transition function.
Moreover, we define pseudo state-action and value functions as follows:
(s, = a) +
Σ (( V(s,a) E (S (+Lt) AA
S'ESCCH
VT(() Σ [( VsES,
(8), =0 Va E A.
Let AA be the event that P E P. for all epochs i 1. Moreover, also define A; to be the event P E Ptt.Note that the value of 1 {AAi) gets determined based on observations prior to epoch i only. Let TISsIA and let f (0, 1).
We decompose the regret against policy æ as follows:
T
Reg(T)
E
Vi (so) VFT (8o)
E
V. (80) (T
(due to Lemma
E
(so)
(s0)
E
T (so) (so)
E
V (so) (70
ERR1
ESTREG
ERRa
(65)
44

---

Note that, the second term (restated below) is controlled by the FTRL process.
P -apnti-Poooo ( 2i)
E|ESTREG] E
g Puns - - g ..00..)))
E.)
E
(66)
F.1 Auxiliary lemmas
We often use the following lemma to handle the small-probability event A while taking the expecta- tion.
Lemma 17 Jii al. 2021
Suppose that random variable X satisfies the following conditions:
Conditioning on event &, X < Y where Y >> 0 is another random variable;
.X < C holds where C' is another random variable which ensures E [CCE99 S D for some
fixed D R4.
Then, we have
E [ S D Pr(7
We next restate the performance difference lemma.
Lemma 18 (Performance difference lemma). Suppose is defined by E(8, = -) for some II and for all and A. We then have
vz (s; = V" (s: (*)))
(s,a; (s, =
(s:
(67)
for any a' 11, s E S and a E
We immediately get following corollary.
Corollary 5. a) S x A. we have -1 (s) < and
and -1 -13 (s) S
We next state the following lemma.
Lemma 19. If event holds, then Es (Pa()(8'ss, P()(ssa)) (F -P(((s)).))(((((ss.))))) B)
0.
Proof. When (s,)) = 2, we have
Σ
(Pan)o'(ss ()) P(s'ls, VT((s)) (s
S'E
Σ
01) 1+
Σ
Pio a) 1 =0,
S'ESuOg+
8'E
where the inequality follows from the fact -1 -1 V7')
On the other hand, when EveSuon (s, (s, a), we have
Σ (Pio(511s,0) P(s a)) (5) (s
d'E
Bs, 1- Bic a) = 0.
3'ESe
where the second line follows from the definition of event A.
We next state the following proposition
Proposition 1. For all (s, S x A. we have 0 S (s, V**(s) +1 T<(als) 2
45

---

Proof. As we have
(") = = Σ [ (s,a')
(68)
= (1- - x.(a
Σ [m(d)))00( -(1 -=)=())))), (69)
a' Ra
get ( a) V* + 1- - 20.
As S Q (5,0) S 1, we also have QT (s, - (s) =e(a|s) (0)
We next state the following proposition.
Proposition 2. If event A holds, (e(s,)) a) S (((ssa) - ()) all (s, a) E A.
Proof. The following holds by Proposition
given that the event A occurs:
(() 9c(s)
(s(s) (Q (8, a) - (8) + =x(a(s) (1 - =T(als)) - BB
< (Q a) (s) (0+11-((aa))) (1- - =e(als)) - (o
= a)) - (i(t)
We next state the following proposition.
Proposition 3. If event A holds, -3 S (8, & for all (8, ESS A.
Proof. Due to Proposition 2 and the total loss of any trajectory is between 0 and 1. we have (() s a)) - ( a) S Q" (s. a) < 1. On the otherhand, due to Proposition
(s) (s(s)
V= (sa) 1 me(as)) (1 =r(als)) Bun)(s,a)
(s)
2 -1 (a(ss) (i(r) (s)
2 3.
We next state the following lemma.
Lemma 20. If event A holds, the following holds:
S E A,te [T].
Specifically, we have:
(uo,, V.5 (so) s V) = (.)
Proof. We prove this result via backward induction from layer L to layer O.
Base case: for sL Q7 (s, a) Q7 (s, a) 0 holds always.
46

---

Induction step: Assume that (F - (s, a) holds for all states e with k(s) > h. Then, for any state with k(s) h, we have
(=) ()) +
=
Σ
Bice)
(due to Proposition 2
{((ssa)+ +
Σ
(10 (s
(induction hypothesis)
3'E
{b(8,a)+
Σ
P(5')s,aVVT(5))
8'E
Σ
(Pit)(5'(s;a) - P(s'(s,a) a)) (T" (s,))
d'ESE
S {((,sa)+
Σ
P(
(due Lemma 19
s'ESe(a)+1
$b(8,a)+
Σ
P(5ls, = (8)
This concludes the induction.
The following lemma follows directly from Lemma C.1.2 in Jin et al. 2021
Lemma 21 (Jin and Luo )020 ). Algorithm ensures (s(s) 2 [s for all t and s.
Lemma 22. Algorithm ensures the following:
o)) 3 Te(s,a) + (()))r(())s)
|S]t.
(((s,a) a)
We also have:
L, a) + (,())T((al))
1. a) + (()
E
Asce)
E
Alco) 2.
(((8,0) a)
(((80) 0)
Proof. Due to Lemma
21,
we have the following:
< 3++ + Less, a) + (())T((as))
a()
(s()) (e(s))TT(as)) (als)
S 33+ + T,(s, a) + (a())
St]t
(s) (a(s))
[, a) + (()) Stt
= 3 +
(s)
Next, we have:
L (s, a) + ((s)TT
L.ss, a) + ((ss)
E
Ar(e)
= E E,
Ar(s) = E [2 =
ge (s a)
(8)
Similarly, we can show that E
Ai(e) = 2.
(c(3,))
Lemma 23. Algorithm 7 ensures the following:
Ee(s,a) < 6|Stt ESx A
Proof. Due Eq.
664)
we have the following:
(s)
L,(s, a)
(QT (s, V (s) + +1-mm(ass)))
(als)) - (1 (a(ss) - (s a)
(x(s)
(s)
(+(s) +3
(due to Proposition
< 2|S[| +
(due to Lemma 21
< S|.t.
47

---

We immediately get the following corollary.
Corollary 6. Algorithm 7 ensures the following:
(7 a) - 6L/S|t, V(s,a) E e
Let (9(() Eoj., EoEa Vq(s, a) and (6(9) = -3 Eoes (s, a). Recall that 6e(9) = ΦH (q) + ΦL(9) and 1024L. Now we prove the following proposition.
Proposition 4. If event A holds, then [( $ A/4
Proof. We have the following:
[| & $16:1(
(as V'h( 1 (p)(T)))
1
2(L(s, + (s())
$
((-(1~(aals)) (i a))² a))
3
ux(8,a)2
8781,
(as ()² - 2a + 263)
1
4(Te(8, + (1)))(((8))) +8) ())
B
a)
# aEA
(as (s))) [0, and -(1 te(als)) + (s, E (-1,))
$ 8
Σ Σ
(s (I((s + (8)(s))) (as (s s (().,))
878L aEA
1
Σ
(8I(s) & (s))
1
(16L)
3
64
We now state the following lemma, which follows from arguments identical to those in Lemma C.1.8
T
of Jin et al. [021]. J and provides an upper bound for E
Σ Σ Σ a) Bun)(s
t= 1s,,, aEA
Lemma 24. Algorithm Tensrres the following:
E
a) (8) -0 (1' L |S||ATT 1 6)
(70)
Finally, we state the following lemma on the learning rates and the number of epochs.
Lemma 25 (Jin al. (2021).. According the design of the learning rate 1}. following inequalities hold:
Vt-two++1 the
T m <0((S| log2 T).
(71)
1)
S 0 (VIs) | T log
(72)
1
< T 2
(73)
T1t -1-
Moreover, Algorithm 1 ensures that N < S (log T + 1) where N is the number of epochs.
48

---

F.2 Technical lemmas to analyze ESTREG
We defined the estimated regret in each epoch i as follows:
1441
(TTREG((T) = E
Pi PP Ee)
E
a q Pin. Ri)
Lemma 26. With B 1024T, for any epoch i, Algorithm ensures
ESTREG,(T) So E L
Σ t=
+ L|S|[A|| log T + E EIIISTT (ti+1 ti]l
(74)
for any policy and simultaneously
f41-1
E [ESTREG;(T))
< O
E
V
S
Σ T
Σ ##OL aft(())
Σ
((8,a))
t=
1411-1
+0
E
Σ
v (c(s,a)
(75)
t=
StsL az
h+-1-1
+0
Σ
T Σ
Σ
Te ()) Biee as)
t=
s5 aEA
+ +0 (L]ST|| log
7 E [LIS|T (1++1 - 4)))
for any deterministic policy S
Proof. If the event Ai does not hold, we have the following:
441-1
at q, 21
(#o(s, + (ss a)) [((s,a)
888,
Σ ()) + (() 3+ +(s,,))+T(())a
Σ
|Sit
uc(s,a) a)
t=
(due to Lemma 22
f+111
ΣΣ ()(s ((8,a)) I(ss a) + (e)s))
< ST
Σ
(s,
sp82
+ 6L (t41 -4).
Due to the second part of Lemma
22
we have the following:
Σ q q, 2o A$
s [6L + 4L|S(T) (t++1 - tx) (A
s E (ti+1 - t.)
Recall that (2((g) - Eufer EAEA / g() Also recall that (s (s. Ey [V((')] and Vi(s) = Eawa (-18) [e(s, a)] (with Vz(s)) 0). Due to Proposition 4
49

---

we get the following by using the same argument as (Jin and Luo 2020
Lemma 5];
f
④t - 9.6)
1441-1
1
1
o (L|S]|A|10g
+
(0H(1) - on oz
7/:
T/-11
11,+1
h+1-1
+8
Th Σ
(s, a)
(76)
t=
Now, we condition on the event A; Recall the definition of Ex from Eq. (60). Now we have the following:
as (s),))))))))))
u(ss,) a)2 (G (Tr(s, ((())))())))) + + (1- (
27, a) (1-m7(als))
(as (a + 6)2 - 2a² + 2b²)
< 47.(s, a) 12
(1(3, ((L((s,0) - ((s) ([-m((as))(ss)(((((
(s, a) 8/2 (a(as)))?
(77)
where we get the last inequality as (s) S (s) and (s. s a))
As E, (L, a) (a(s)) = g(s (als)) + {(()) -<((aaaa)) and
E,
(s) = (s), we have the following:
E.
((I(ss,)) - (((s){(a)(s)) + [<(d + a7) - Te (a)s)))
as)
12 0) (s) (1 - (alss) (als) 27 (8, (s. 2 (als)))
(=(
(s, a) 1/2 (als))
(78)
We now proceed to prove Eq. 74) and Eq. (75).
Proving Eq. 74 In this case, we consider the second term inside the minimum in Eq. 76)). and derive straightforward upper bound (H(4) - Φu (ğ:) using the Sauchy-Schward inequality, yielding (g) - (H) S Eofor. EnEA (e, a) S /L.S|AA] This gives
q, E.
1=4
h 1
h+1-1
$ O (L]S||A||og]]) + / ||S|AA|
Σ
T +8 8
T) Σ Σ qe a) 2), a)²
1=1,
t=,
SfeL aEA
1/t since
- 4++
M 1
Tt
h+1-1
+ + /
Σ at + 16
"t Σ Σ
1=4,
8532 acA
111-1
+1 Σ T Σ Σ (8, 1/2 (s
$5888 aed
4+1-1
1441-1
0
L|S||A||og T + DSS
Tp.
+
ΣV
Ee t2 a)²
t=4
t=
8f81, a
(as Bi( (2, 54)
50

---

Therefore, by Lemma 17 Eq. 77p. Eq.
788
and tower rule, we have for any policy x that,
441-1
(e(s,a))/2 (1 = ))
E [ESTREG;(TT] 0o
E V L|S|IA
Σ
1/t
Σ Th
t=
t=
8881,
O (L|S||A] log T + 8.
E
[| (1++1 4)])
44111
oo
V ||S||A|
Σ Tp
|||
[|S)T (t +X)
where the second step follows from Exper EAEA V & VLSSIA This completes the proof of Eq. (74.
Proving Eq. 75)
In this case, note that since ı is a deterministic policy, it follows that
vi(aa))) - -1) + Σ [.(s)) -
Φ -
E (s)
aEE
By applying Jin and Luo 2020 Lemma 16] with 0 to upper bound the first term, and using [Jin and Luo 2020 Lemma 19] to upper bound the second term, we arrive at
0x(2) - (2) = Σ E Vā(s,a)+
L Σ Σ @()
SYOL afn((s)
s782 a+
Therefore, considering the Eq. (76 and using the inequalities (a + 6)2 < 2a² + 212, we have
1 1 S 17c from Lemma 25 and
l4+1 -1
q, 21
S
S
Σ
Σ #FOL ast
Σ
a(
t=
4+1-1
T
(s
El
S af)(s)
441-1
(79)
+ 16
Σ
1 Σ
Σ
a) 2) (s,
t=
441-1
+ 16
Σ
T
Σ
Σ a) (s a)²
t=
| log
Next, observe that for a deterministic policy म. we have:
Σ Σ (((8,)) (1 (a(ss))
< Σ Σ 8F8L as)((s)
V Σ Vi((s) (T(((())))))
#5 A
of811
Σ Σ
Va((,a)+ + Σ (s) Σ (r(ass)
8481, as)((s)
8881..
(apt
2 Σ Σ (((s)))
(80)
81 as
51

---

Therefore, by Eq. 79 Lemma 17 Eq. 77
Eq.
78
Eq.
80
and tower rule, we have for any
deterministic policy π A that,
4+111
E [[STTREC;TT]]
S O
E
V
L
Σ
T
((s
t=
efol asf((s)
h+1111
+0
Th E
V)((s,))
878 apf((()
h41-1
+0
Σ T Σ Σ
(
(s,
1=t1
#f8r, acA
+ O (T|SS]|A| log T + 8. E [T|S) (4++1 - 4))
F.3 Adversarial regret guarantee
Recall from Eq. 665) that the regret decomposes as:
Reg( (T))
E
(5o)
E
Vi (so) (su)
(su)
E
V.. (so) (so)
ERR
ESTReo
ERR
We now analyse each term separately. First, we have the following:
ERR
Σ (ge, Es)
[
(QT (s) +1 (x(als))7(ssa))
(u,(8, a) -0(5. a))
a(
8888 aEA
(a- (1,
2
+
(e. Bun)
where the second equality follows from Eq.
64 and ==s V (s).
Due to the above equality, proposition Lemma 17 the fact that Tr (s, a) S (s, a) under event A
and analysis of ERR; from Appendix C,2 Jin (021]. we get the following:
E Ô [ | L3|S|$
Next, we have the following due to Lemma 20
Lemma 17
Corollary 5 and Corollary 6
E|ERR2] δ (L|STT2.0)
According to Eq. (74) of Lemma 26 have
N
ESTREG(T) E
T q PrcO R2)
E
Σ
ESTREG (T)
N
4++1-1
00 E
nt
+
||S)?|
A/2 log T + 8. L|S]72)
:=
(due to Eq. 774 and Lemma 25
2ō <0(1S1AAIVT. (1SIAIIVTT++11$$11
(due to Eq. 72
52

---

Finally, by combining the bounds for ERR1, ERR2, and ESTREG, we obtain:
Reg(T) = (LSWIAATTSSSAVVII
F.4
Stochastic regret guarantee
F.4.1
Self-bounding terms and related lemma
In this section, we adopt the definition of self- seff-boundin terms and the related lemmas from Jin et al.
202T]
Definition 5 (Self-bounding Terms), For some mapping n² S - A, define the following:
T
() = Σ Σ
Σ
qe(s, a
V max {m)ro)(s,a))
t=l
sf81, (s)
(2) = Σ
Σ
- (9((s,))99((6 ())))))) V max {mico (s, 1)
(=1 SY88 O= (8)
M
P(wlu, u, v) J max (miro) (u, v), 13
(J()) Σ Σ
Σ
aluu,)y
9: (c(s,alw),
8886 OFFT
(a())
Σ
a(s,a),
1=1 8888 (s)
(o(J) = E
ae a),
sta (s)
M
(o(J) = -
ge(s, a) % as, (((s,a) a)
Σ
Σ
qd(u,v)
max (u, v), 13 a ((s.
P(wlu, v) J
81 a= (8)
kmo
(u.
Lemma 27, Suppose Condition holds. Then we have for any O E R
E (Q)
a a (Regy (T' C)+
Σ Σ
8.
(ss.a)
8#81. (s)
Lemma 28. Suppose Condition holds. Then we have for any R.,
8.
E [Q)) < B (Regz (T + + 3 AMIN
Lemma 29, Suppose Condition
4 holds. Then we have for any a, B E R.,
E [Qa()) < (a + 3) (Regy (T + CC+ Σ Σ
Σ
8L
8L31S
+
(ss,a)
3
AMIN
85 (s)
Lemma 30. Suppose Condition holds. Then we have for any 3 E R+,
J
E (J)) < 8- (Regr + C) + 4AMIN
Lemma 31. Suppose Condition holds. Then we have for any a R
E [Q(J)) a (Reg, (T*) + Σ Σ
4aA(s,a)
8F81 (+)
Lemma 32. Suppose Condition 4 holds. Then we have for any R+,
1 8L3 8
E [Q([)) < 3 (Regg + +C+
A
53

---

F.4.2 Proof for the stochastic world
Similarly to the proof in Appendix C.3 of of et al. [202]], we decompose the sum of ERR; and ERRg into four terms ERRSUB, ERROPT, OCCDIFF and BIAS:
T
ERR1
ERR
Σ
Σ
Σ
ae(s, (s,a)
(ERRSUB)
1=1
sts2 (s)
( (s, Ey (s,a)
(ERROPT)
8FLL (x)
T
(9)(s,a) (((s,a)) @o (s, - V.- (s)
(OccDIFF)
spaa aEA
Σ
E Σ
(s) V7 (s) V. VTr(s) (s)
(BIAS)
FELL (*)
where ET is defined as
= (((,,)=(((s,d))
(( (s)
We now begin by upper bounding E [OCCDIFF]. First observe that we have the following:
OcCDiFF
ΣΣ
Σ
Σ
(m((s,)) (s) (Ør (s. V. (s)
[=1 SFLL AEA
(Q (s, V (s)
8880 Oxft* (8)
Σ Σ Σ
(n(s,a)@((ssaa))) a)l O (s, vi (s)
8888 af** (8)
Under event A,
we further have Eto Eafrr(s) (e(ssa) - a))
QF (s V,= (s) I 5L ΣT Enpar Eapr(ss - as -3 < ((ss,) S 1
under event A. If event A doesn't hold, we have Σt= Eoper Eafr( (qi(s, a) - a))
QT (s) - V. (s) < 12L |/A due to Corollary 6 Hence due to Lemma 17 we have the
following
E[OccDIFF] < 0
L E Σ Σ
(s)(s (c)) + L|S| A|T2
(s)
S O (L"1
QZ
where the last line follows from the definition of C3 and Lemma D.3.10 of Jin et al. [222
54

---

Next, due to Lemma 17 Lemma 20 and Corollary 6 we have E [BAS]] S 8 ( The first terms ERRSUB and ERROPT are bounded differently. First, under event A, we have
ET (8,a) a) = (e(s, - a)( +
Σ
(P(s'(s,a) - (sce)("((s,)) V (6)
d'ESkO)
= (80' - m -1- +1-x((alss) (1 (0 a)
4z(s,a)
+ +Bun)8,,)+ Σ
(P(8's, - (s V. (s')
d'ESk
2(uu(s, a) ()) ALL (s
(05,a))
where the last line uses the definition of the event A along with the fact that qi (s, a) S uu(s, a) and -3 < (s, a) under this event. Next, observe that the range of E, is O(L]S)t),
established by Proposition and Corollary 66, which implies that the range of both ERRSUB and ERROPT is ( Thus, it suffices to add term of order O 12255(T2) to account for the event A
By the exact same analysis as in Appendix C.3 and Appendix B.2 of et [021] and the fact that [v(s)] = O(L) under event A, we have the following:
[ERRSU]] = O E (aa(n))) + Q (L?) In ) + | 1) E [RROOP]] = O E (Q((In)) (2 +
We are now left with bounding ESTREG using self-bounding terms.
Term ESTREG Based on Eq. 75 from Lemma 26 summing over epochs gives the following upper bound for E [ESTREG]:
N 141-11
t41-1
O
E
S
Σ
Σ
+ E
Tk
Σ
Σ
v a
sfor, (s)
im
t=
N
+0
Σ
Σ
a)) Buto(s,a)
+ +0 (L log" T + L|S
i=1
t=
syla REA
(due to Lemma 25
T V S
T
o
E
Σ nt
Σ Σ (+)
+0
E
1
Σ
(g)
1=1
t=1
8888 aff*(()
O
(L'ISTIAAP'>?>
(due to Lemma 24
By the exact same analysis in Appendix C.3 of Jin al.
2021
we bound the first follows:
T L
E
as
syfa aptio (s)
o (I(SS) T) Qu (In+)) [2(8)"14)>1>)))
Again by using the exact same analysis as in Appendix C.3 of al. 2021]. we bound the second term follows:
T
E
Σ
a))
(s)
o
[Q((())AA log Q3 (Inz)] + 1191)11441111))
55

---

Thus, we obtain the final bound on E |ETTRE]]:
E [ESTREa] = 0 Q4
1og T) + Qs [[8] 7) + Q3 (In))] + 1115)191//111)
Recall that 1/T and have
| Finally, by combining the bounds of each term, we finally
(egy((")) (T
S 0 E [Q] (L2)S) + Qa (In))]
(from ERRSUB)
+
Q2 (I Ind) + Q6 (In<)]
(from ERROPT)
+ E
Q2 (I
(from OcCDIFF)
+ E [Qu (L]S|)A4|nn)) 1) + Qs (IS]IA Q (In))
(from ESTREG)
+ L In²
Using the self-bounding lemmas 27 32 and the exact same analysis as in Appendix C.3 of et al.
2021 we get Regr (T*) is bounded by O (U VUC v) where V L3 |A In? i and U dehied as
L L In | In2 L
[L S + 131SPAAD In L|S In²
U= Σ Σ SffL (+)
+
A(s,a)
A MIN
This completes the entire proof.
56


Reviews:
[{"review_id": "clTyV0tL4h", "reviewer": "Reviewer_irfz", "summary": "The paper proposes the first best-of-both-worlds (BOBW) algorithms for episodic MDPs with aggregate bandit feedback, where only trajectory-level losses are observed. The algorithms achieve $O(\\log T)$ regret in stochastic settings and $O(\\sqrt{T})$ in adversarial ones, both for known and unknown transitions. The algorithm works under the assumption that the state space is partitioned on a set of $L$ layers, and transitions from a layer $k$ are only allowed to layer $k+1$.", "questions": "Why is it necessary to assume that the MDP is layered?", "limitations": "Assumption of layered MDPs and lack of experimental evidence/sanity checks.", "rating": 4, "confidence": 1, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "## Strengths\n\n- Although the paper is not in my area of expertise, I believe the paper is overall clearly written and the contribution seems significant.\n\n## Weaknesses\n\n- Lack of experiments. Even for a theoretical paper, I believe sanity-check experiments that test the main algorithmic novelties are important. \n\n- Clarity could be improved by moving the algorithm definition to the main text. In the current version, the main text focuses on explaining the ideas behind building the algorithm, but without clearly presenting the algorithm itself.", "was_revised": true, "final_justification": "As I said in my review, although the paper is not in my area of expertise, I believe the paper is overall clearly written and the contribution seems significant.", "rebuttal": "We thank the reviewer for their review. We address their concerns below.\n\n**Reviewer’s question:**\nWhy is it necessary to assume that the MDP is layered?\n\n**Author’s response:**\nNote that this assumption introduces no loss of generality: any finite-horizon MDP can be transformed into a layered one by replicating the state space across $H$ layers. We assume a layered MDP primarily to simplify notation and analysis. This is standard in the literature, for instance, in works like (Jin et al., 2020, Jin et al., 2021), and is often referred to as a loop-free stochastic shortest path problem.\n\nJin et al. 2020. *Learning Adversarial Markov Decision Processes with Bandit Feedback and Unknown Transition*\n\nJin et al. 2021. *The best of both worlds: stochastic and adversarial episodic MDPs with unknown transition*\n\n**Reviewer’s comment:**\nClarity could be improved by moving the algorithm definition to the main text. In the current version, the main text focuses on explaining the ideas behind building the algorithm, but without clearly presenting the algorithm itself.\n\n**Author’s response:**\nWe thank the reviewer for this helpful suggestion. We agree that presenting the full algorithm in the main text would improve clarity. In the revised version, we will prioritize including the algorithm in the main body, space permitting, and adjust the surrounding discussion accordingly."}, {"review_id": "Pcc8BGQPyI", "reviewer": "Reviewer_Utfj", "summary": "The paper studies online learning in finite-horizon episodic MDPs under aggregate bandit feedback, which means that on each episode, the agent only observes the aggregate loss across the entire episode. Prior work has provided regret bounds for the worst-case version of this setting, where the loss function each episode is chosen adversarially. In the stochastic version of this setting the loss function of each episode is chosen iid. This paper proposes a “best of both worlds” (BOBW) algorithm which yields $\\tilde{O}(\\sqrt{T})$ regret in the worst-case setting and $O(polylog(T))$ regret in the stochastic setting. They also provide nearly matching lower bounds. Lastly, they provide some regret bounds for online shortest path as a byproduct of the primary analysis.", "questions": "If the authors believe that there is a reason I am underestimating the potential impact of their work, I am open to changing my mind. However, since this is ultimately a very subjective assessment, I think this is unlikely.\n\nMinor comments:\n1. “TC” is not defined in Tables 1-3. I understand that it is defined later, but I think everything that is used in the table should be defined in the table\n2.  Is there no way to simplify the expression on line 92?\n3. Lines 98-107: Why not instead assume that the aggregate losses are in [0,L]? That seems simpler\n4. Line 136: What is this expectation over? Isn’t $c_t$ a constant conditioned on $((s_t^k, a_t^k))_{k}$?", "limitations": "The “limitations discussion” is essentially just a normal conclusion section where the authors discuss technical open questions. I suppose this technically fits the requirements for a limitations discussion, but to me it misses the spirit of the requirement: if the expectation was simply to write a normal conclusion section, there would be no need to explicitly include the requirement for a limitations discussion in the submission guidelines.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "**Strengths**\n\nThe paper does a reasonable job of motivating the problem. The authors' work fills a gap in the existing literature and they provide a clear comparison (I especially appreciated Tables 1-3). The results all appear sound and well-justified.\n\n**Weaknesses**\n\nI did not find any significant issues with the paper. I think the presentation could be improved somewhat: the paper dives into pretty heavy math on page 5 without a lot of intuition. A proof roadmap or a definitions roadmap might be helpful here.\n\nThe primary reason I am not awarding a higher score is simply that nothing in particular stands out to me about this paper. The results are fine but not exceptional, the techniques are fine but not exceptional. The paper fills a very specific niche that I think has limited impact. To the extent possible, I would encourage the authors to justify why their paper is not “just another MDP online learning paper”.\n\nI realize this may be frustrating to the authors since this is a very subjective assessment, but I cannot justify giving a higher score because I do not think the paper has “high impact on at least one sub-area of AI or moderate-to-high impact on more than one area of AI”. Overall, I still lean towards acceptance though.", "was_revised": true, "final_justification": "My assessment remains the same: the paper has no major issues but I do not think it is has “high impact on at least one sub-area of AI or moderate-to-high impact on more than one area of AI” to justify an Accept rating.", "rebuttal": "We thank the reviewer for their review. We address their concerns below.\n\n**Reviewer’s comment:**\nIf the authors believe that there is a reason I am underestimating the potential impact of their work, I am open to changing my mind. However, since this is ultimately a very subjective assessment, I think this is unlikely.\n\n**Author’s response:**\nWe thank the reviewer for their thoughtful assessment and constructive feedback. We acknowledge that parts of the presentation, particularly the transition into the technical sections, could benefit from more intuition and a high-level roadmap. We will address this in the final version.\n\nRegarding the impact of our work, we address a fundamental gap in online learning for MDPs with aggregate bandit feedback, where the learner observes only the total reward over a trajectory. This setting is strictly more challenging than the standard one, where feedback is observed at each step, and it also arises naturally in many practical applications where intermediate rewards are inaccessible or costly to obtain. Existing methods either rely on policy-optimization approaches or linear bandit reductions, neither of which achieve best-of-both-worlds (BOBW) guarantees.\n\nOur technical contribution is twofold:\n\n* **Novel estimator and first FTRL algorithm**: We build on the recent estimator of Maiti et al. (2025) for shortest paths in DAGs and generalize it in a non-trivial way to design the first FTRL algorithm for aggregate feedback MDPs. This directly leads to the first BOBW guarantees in this setting.\n\n* **Simplified analysis and improved bounds**: Unlike prior BOBW work in standard MDPs, which required complex loss-shifting techniques, our estimator avoids these techniques and yields a cleaner, more general analysis while improving the regret bounds.\n\nWe believe that introducing FTRL to the aggregate-feedback setting, achieving BOBW where prior methods failed, and simplifying the analysis via a more general estimator together lay the groundwork for future advances in online learning with partial feedback.\n\n**Reviewer’s comment:**\n“TC” is not defined in Tables 1-3. I understand that it is defined later, but I think everything that is used in the table should be defined in the table.\n\n**Author’s response:**\nWe apologize for the confusion. “TC” refers to time complexity, and a checkmark indicates that an efficient implementation is possible. We will clarify this in the table for better readability.\n\n**Reviewer’s comment:**\nIs there no way to simplify the expression on line 92?\n\n**Author’s response:**\nCurrently, we are not aware of any way to simplify the expression. Improving upon this remains an important open question.\n\n**Reviewer’s comment:**\nLines 98–107: Why not instead assume that the aggregate losses are in $[0, L]$? That seems simpler.\n\n**Author’s response:**\nWe assumed that the aggregate losses lie in $[0,1]$ purely for simplicity of presentation. To compare with the $[0,L]$ case, one can simply scale the regret bounds by $L$. Moreover, as explained in Remark 1 of the supplementary material, choosing aggregate losses in $[0,1]$ (or $[0, L]$ when scaled) corresponds to a more general setting than assuming per-layer losses are $O(1)$.\n\n**Reviewer’s comment:**\nLine 136: What is this expectation over? Isn’t $c_t$ a constant conditioned on $((s_k, a_k))_k$?\n\n**Author’s response:**\nIn the stochastic setting, $c_t$ is a noisy reward, and the expectation is taken over the randomness in the noise."}, {"review_id": "jCEGcKTKsX", "reviewer": "Reviewer_URxr", "summary": "This paper propose the first study of best-of-both-worlds algorithms for episodic tabular MDPs with aggregate bandit feedback, i.e., where the learner only observes the cumulative loss incurred in each episode instead of the individual loss over each state-action pair of the trajectory. They define a loss estimator inspired by online shortest path problems, and use it on FTRL algorithms over occupancy measures. They treat both the cases of known and unknown transitions.", "questions": "I have a question regarding the final result:\n\n* What specific aspect of the loss estimator allows to avoid scaling the bonus term by an additional factor of $L$? I ask because, in episodic MDPs, methods that incorporate bonus terms are typically known to incur an extra $L$ factor in the regret bound compared to approaches based on confidence bounds over occupancy measures because of this scaling factor in the bonus definition. Does this suggest that in the standard episodic MDP setting a similar loss estimator could be used to eliminate this additional term in the regret bound while keeping the same dependencies on the other MDP parameters?", "limitations": "yes.", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "This is an interesting paper for the following reasons:\n* The paper is well-written and clearly structured.\n* Adapting the loss estimator from online shortest path problems to episodic MDPs with aggregate feedback is novel and enables the development of BOBW algorithms, and potentially other algorithmic approaches as well.\n* Rather than simply combining two existing results (the loss estimator from Maiti et al. and the FTRL BOBW approaches from Jin et al.) the authors also have to address the additional challenge of unknown transition probabilities. Ensuring the optimism of the loss estimator in this setting seems non-trivial and the approach they use in section 3.3 could have broader applications.\n\nAside from the limitations already outlined in the conclusion as directions for future work (generalizing to policy optimization algorithms to avoid computational complexity), I don't see any major weaknesses to highlight.", "was_revised": true, "final_justification": "After reading the other reviews and responses I will keep my original positive score. The authors have addressed all of my questions, and given the strengths highlighted above, I believe this is a interesting work.", "rebuttal": "We thank the reviewer for their review. We address their concerns below.\n\n**Reviewer’s question:**\nWhat specific aspect of the loss estimator allows to avoid scaling the bonus term by an additional factor of $L$? \\[...] Does this suggest that in the standard episodic MDP setting a similar loss estimator could be used to eliminate this additional term in the regret bound while keeping the same dependencies on the other MDP parameters?\n\n**Author’s response:**\nIn Eq. (9) on page 7, the presence of the terms $(1 - \\pi_t(a \\mid s))$ in the numerator of the fraction and $-(1 - \\pi_t(a \\mid s))$ after the fraction eliminates the need for loss-shifting techniques used in prior work, thereby avoiding the additional scaling of the bonus term by a factor of $L$. Our bounds also improve upon the instance dependent regret guarantees by Jin et al. (2021), who considered the standard episodic MDP setting.\n\nJin et al. 2021. *The best of both worlds: stochastic and adversarial episodic MDPs with unknown transition*"}, {"review_id": "yPukShQqBs", "reviewer": "Reviewer_CGzt", "summary": "The paper studies best-of-both-worlds algorithms for layered finite-horizon MDPs with aggregated bandit feedback. The proposed algorithm is efficient and obtains the following regret bounds, where $T$ is the number of rounds:  \nFor known dynamics:  \nAdversarial losses - $O(\\sqrt{ T})$ ; Stochastic losses - $O(\\log T)$ regret.  \nFor unknown dynamics:   \nAdversarial losses - $O(\\sqrt{ T})$ ; Stochastic losses - $O(\\log T)$ regret.  \nAll rates are near optimal also in $S,A, L$, i.e., states, actions, and horizon length.  \nIt also presents regret bound for the Stochastic Shortest Path setup.", "questions": "1. Can you explain the general algorithm framework and provide pseudo-code?", "limitations": "N/A", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 3, "significance": 4, "originality": 3, "strengths_and_weaknesses": "**Strengths:** \n\n1. Well motivated setting.\n2. Near optimal regret bounds in the first BOBW algorithm that considers MDP with aggregated bandit feedback.\n3. Well-written paper.\n4. Novel optimistic approximation technique (although inspired by previous work on SSP).\n5. High potential to impact the community by extention of the approch to other related setups with aggregated bandit feedback.\n\n**Weaknesses:**\n\n1. The dependency in $S,A$ is  not optimal in some of the studied cases.\n2. The algorithm is not properly stated in the main paper.", "was_revised": true, "final_justification": "After reading the authors rebuttal, all my concerns are satisfied and I am supporting the paper's acceptance.", "rebuttal": "We thank the reviewer for their review. We address their concerns below.\n\n**Reviewer’s comment:**\nThe dependency in $S, A$ is not optimal in some of the studied cases.\n\n**Author’s response:**\nWhile we agree that the dependence on $S$ and $A$ is not optimal, the same holds for prior works in the standard feedback setting. Improving these bounds in both the standard and aggregate feedback settings remains an important open question.\n\n**Reviewer’s question:**\nCan you explain the general algorithm framework and provide pseudo-code?\n\n**Author’s response:**\nOur algorithmic framework has the following main components:\n\n1. Building the confidence set of the true state transitions.\n2. Building an optimistic loss estimator.\n3. Determine a policy using an FTRL with a suitable regularizer which contains both Tsallis-INF and log-barrier.\n4. Generate a trajectory using the policy computed and update the estimates.\n\nThe main novel aspect of our algorithmic framework is the loss estimator, which eliminates the need for the loss-shifting techniques used in prior work and avoids the additional scaling of the bonus term by a factor of $L$. In addition, our approach generalizes the estimator of Maiti et al. (2025), originally developed for shortest paths in DAGs, to the more general setting of MDPs with aggregate feedback. For the detailed pseudo-code of our algorithm, we refer the reviewer to Algorithm 1 on Page 41 of the supplementary material.\n\nMaiti et al. (2025). *Efficient near-optimal algorithm for online shortest paths in directed acyclic graphs with bandit feedback against adaptive adversaries.*\n\n**Reviewer’s comment:**\nThe algorithm is not properly stated in the main paper.\n\n**Author’s response:**\nIn the revised version, we will prioritize including the algorithm in the main body, space permitting, and adjust the surrounding discussion accordingly."}]

Author rebuttal:

Meta-review: All reviewers gave the paper positive evaluations. It is mostly well written and its theoretical results are strong enough for this venue. Given these strengths, I recommend that it be accepted.
Decision: Accept (poster)