Near-optimal Regret Using Policy Optimization in Online MDPs with Aggregate Bandit Feedback
Authors: Tal Lancewicki
Yishay Mansour
Venue: ICML 2025 poster (2025)
Keywords: Online MDPs
Policy Optimization
Aggregate Bandit Feedback
Full-bandit feedback
Reinforcement Learning
Regret Minimization
Adversarial MDPs
Primary area: theory->reinforcement_learning_and_planning
TL;DR: First Policy Optimization algorithms and improved bounds for online MDPs with aggregate bandit feedback

Abstract: We study online finite-horizon Markov Decision Processes with adversarially changing loss and aggregate bandit feedback (a.k.a full-bandit). Under this type of feedback, the agent observes only the total loss incurred over the entire trajectory, rather than the individual losses at each intermediate step within the trajectory. We introduce the first Policy Optimization algorithms for this setting. In the known-dynamics case, we achieve the first *optimal* regret bound of $\tilde \Theta(H^2\sqrt{SAK})$, where $K$ is the number of episodes, $H$ is the episode horizon, $S$ is the number of states, and $A$ is the number of actions. In the unknown dynamics case we establish regret bound of $\tilde O(H^3 S \sqrt{AK})$, significantly improving the best known result by a factor of $H^2 S^5 A^2$.

Near-optimal Regret Using Policy Optimization in Online MDPs with Aggregate Bandit Feedback
Tal Lancewicki
Yishay Mansour' 12
Abstract
(2021b), who considered the setting study here, where the losses are non-stochastic and may be chosen by an adver- sary. They introduce a variant of bandit linear optimization which they call Distorted Linear Bandits and provide a solu- tion for Through the framework of occupancy measures, they reduce the problem of adversarial MDPs with aggregate bandit feedback to Distorted Linear Bandits. This approach allows them to obtain regret of ( 5 A /K), where K is the number of episodes, H is the horizon, S is the number of states and A is the number of actions. While the dependency on K is optimal, the dependency on other parameters is far from optimal.
We study online finite-horizon Markov Decision Processes with adversarially changing loss and ag- gregate bandit feedback (a.k.a full-bandit). Under this type of feedback, the agent observes only the total loss incurred over the entire trajectory, rather than the individual losses at each intermediate step within the trajectory. We introduce the first Policy Optimization algorithms for this setting. In the known-dynamnn optimal regret bound of é( /SK),, where K is the number of episodes, H is the episode horizon, S is the number of states, and is the number of actions. In the unknown dynamics case we establish regret bound of Ó S AK), sig- nificantly improving the best known result by a factor of 2 A?.
case, we achieve the first
In this paper, we revise the setting considered in Cohen et al. (2021b), both in the known and unknown dynamics cases. We present algorithms based on the Policy Optimization framework (Cai et al., 2020; Shani et al., 2020; Luo et al., 2021; Chen et al., 2022a), which has strong connections to many practical algorithms such as NGP (Kakade, 2001), TRPO (Schulman et al., 2015), and PPO (Schulman et al., 2017). Our algorithms have a closed-form update and are more efficient than that of Cohen et al. (2021b), which requires solving convex optimization problem in each iteration. We obtain the first optimal bound under known dynamics and significantly improve the regret bound of Cohen et al. (2021b) in the unknown dynamics case.
1. Introduction
The standard model of reinforcement learning (RL) assumes a rich feedback loop, where for each step within the episode the agent observes the loss in that state as feedback. While ideal, this often not the case in real-world applications. For example, in multi-turn dialogues with LLM, feedback is typically available only at the end of the entire dialogue, not for each intermediate response. Similarly, in robotic manipulation, feedback is often only available for the entire trajectory, indicating whether the robot successfully com- pleted its task, rather than providing feedback at every step of the robot's 's movement.
Summary of Contributions. The main contributions of the paper are as follows:
We present the first Policy Optimization algorithms for Online MDPs with aggregate bandit feedback.
Under known dynamics we the first to establish the near-optimal regret bound of é /SAK).
To address this challenge, Efroni et al. (2021) have initiated the study of aggregate bandit feedback in stochastic set- ting where losses are generated in an i.i.d. manner. More recently, Cassel et al. (2024) have extended this to linear MDPs. Most related to our work is that of Cohen et al.
In the unknown dynamics case, we achieve a regret of ((HS)) Surprisingly, this regret bound matches the best known regret for Policy Optimiza- tion with semi-bandit feedback (Luo al., 2021).
BBaavatnik School of Computer Science, Tel Aviv University, Israel "Google Research, Tel Aviv, Isracl. Correspondence to: Tal Lancewicki <lancewicki @ mai..tau.a..il...
We establish a new lower bound 2(H for online MDPs with aggregate bandit feedback. To the
'Luo et al. (2021) presents slightly different dependence on the horizon H. This is due to their assumption of a loop-free MDP, which effectively enlarges their state space by a factor of H compared to our model - see Remark 1.1.
Proceedings of the ndnd International Conference Machine Learning, Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Near-optimal Regret Using Policy Optimization in Online MDPs with Aggregate Bandit Feedback
best of our knowledge, this is the first lower bound for this setting that is not directly implied from the semi-bandit case.
where B is a bound on the losses (Bubeck et al., 2012). Using a discretization argument, this bound can be extended to ((Bv/K) for any compact convex set. However, the EXP2 algorithm is not efficient in general. The latter bound for general convex set is attainable with efficient algorithms (polynomial in d) under mild assumptions (Hazan & Karnin, 2016). When using occupancy measures to reduce online MDPs with aggregate bandit feedback to Linear bandits, the decision set is of dimension d = HSA, the bound of the loss in each round is B H. and the number of de- terministic policies is N = ASH Thii results in regret of Ó(HSVAK) and Ó(11SAvK)) with inefficient and efficient algorithms, respectively. For the known dynamics case, we improve these bounds to optimal é / regret with an efficient and more natural algorithm.
comparison of our results to previous works is summa- rized in Table 1.
Overview of techniques. Much of our algorithms' de- sign and analysis follows the seminal work of Luo et al. (2021). As most of the regret minimization literature. they built upon the fundamental value difference lemma (Kakade & Langford, 2002; Even-Dee Dar et al., 2009) that breaks the total regret as a weighted sum of local regrets in each state separately with respect to the Q-function. Our central ob- servation is that the regret can be decomposed in similar manner but with respect to different quantities, which we call the U-values. These quantities are particularly natural in the context of aggregate bandit feedback. The U-function at a given state and action is the expected cost on the entire trajectory given that we visit this state-action pair. Our decomposition with respect to the U-functton is especially useful in the setting of aggregate bandit feedback since the U-function can be easily estimated using only the accu- mulated trajectory loss. This is in contrast to Q-function estimation that typically uses individual losses or the cost- to-go from a state-action pair.
As mentioned before, Cohen al. (2021b) have extended the linear bandit model to Distoried Bandit Online Linear Optimization (DBOLO). They show that online MDPs with aggregate bandit feedback and unknown dynamics can be reduced to DBOLO efficiently. Their algorithm is built upon the SCRIBLE algorithm (Abernethy et al., 2008) and guar- antees regret of 0 5 A$/2 On the same setting, we improve their regret bound to ((HSSVAK).
Regret minimization in MDPs with semi-bandit feedback is extensively studied in the literature, initiated with the seminal UCRL algorithm (Jaksch et al., 2010) for stochastic losses. Their model was later extended to the more general Online (adversarial) MDPs where the loss functions are ar- bitrarily chosen by an adversary. Most algorithms for this model are based either the framework of occupancy mea- sures (Zimin & Neu, 2013; Rosenberg & Mansour, 2019a;b; Jin et al., 2020) or the Policy Optimization framework (Even- Dar et al., 2009; Shani et al., 2020; Luo et al., 2021). In the adversarial model with bani-b feedback and known dynamics, the optimal regret bound is Õ(H V5AK) case and is attained by an occupancy- measure based algorithm (Zimin & Neu, 2013). With PO, the state-of-the-aa thette- re- gret under known dynamics is Ö(H² (SAK), We achieve the same bound with aggregate bandit feedback which in this case is optimal. Under unknown dynamics, the best known bound is O(H2SVAR, and is also attained by an occupancy- measure based algorithm (Jin et al., 2020), while the best known lower bound is 12/13322/SA// 2018). With policy optimization algorithm, the best known bound is Ö(H SV (AK) (Luo et al., 2021). Although we are in a setting with less informative feedback, we match the latter bound.
1.1. Related work
Aggregate bandit feedback with stochastic i.i.d losses was first studied by Efroni et al. (2021) who obtained regret of 0 A3/2 with an efficient algorithm. Their transition and loss functions are not porizon-dependee Adapting their bound for horizon-dependent losses and tran- sitions we consider here would effectively inflate the number of states by factor of H, resulting in regret bound of Õ( 223/ /3). Cassel et al. (2024) intro- duced the first algorithm for Linear MDPs with stochastic losses and aggregate bandit feedback. Their algorithm at- tains regret of D(vd5 d H" K) where d is the dimension of the feature map. In the special case of tabular MDPs, they show a regret of 52 A3/2
Adversarial Linear bandits (see for example Lattimore & Szepesvári (2020)) is a variant of the classical Multi- armed Bandit problem where each action is associated with a vector in Rd. The loss in each round is the inner product of the action with an unknown parameter vector chosen by an adversary. Through the concept of occupancy mea- sures, online MDPs with aggregate bandit feedback and known dynamics can be seen as a special case of Adver- sarial Linear bandits. In terms of regret bounds, EXP2 (Dani et al., 2007: Rasa-Bianchi & Lugosi, 2012) with a specific exploration distribution achieves the optimal bound of O B / log N) for any finite set of N actions in Rdd
(Jin et al.,
Remark 1.1. We note that some of the literature on semi- bandit feedback, such as Jin et al. (2020); Luo et al. (2021), assumes loop-free MDPs. Under this assumption the state space consists of H disjoint sets S = S, US U U SH such that in step h the agent can only be found in states from the set Sp. Effectively, this means that their state space
2

---

Near-optimal Regret Using Policy Optimization in Online MDPs with Aggregate Bandit Feedback
at time h. The value Vi;;; f) is the expected cost of a with respect cost function e starting from 8 in time h, i.e. (s; E) = E E|> h (ar(s,, aa:) I 8h = s]. where the expectation is with respect to policy π and tran- sition function p. that is, an ~ Tn (-<(-18))) and 8/41 ~ Ph (- an.). The Q-function is defined by (s, = E[ (1 ane |FT, 8h = 8, On = a] The occupancy measure (5, a) = Pr[s,, = a, = a T $1 = Simit] is the distribution that policy т induces over state-action pairs in step h, and we denote (s) = EnEA (s..a).
Table 1. Comparison of regret hounds for online MDPs with ag- gregate bandit feedback. In the 'Loss' column, 'adv.' denotes adversarial (non-stochastic) losses, while 'stoc. denotes stochas- tic i.id losses. The regret bounds presented in this table ignore logarithmic and low-order terms.
Algorithm
Dynamics Loss
Regret
Reduction to Efficient
known
adv.
v HH
Linear Bandits algorithm
Algorithm I (ours)
known
adv.
v VH'SAK
Lower bound
known
adv.
v /HSAKK
UCBVI-TS
Learning protocol and Feedback The learner interacts with the environment for K episodes. At the beginning of episode k. it picks a policy x², and starts in an initial state of Sinit In each time h E [f it observes the current state si draws an action from the policy of ~ T (+1s%) and transitions to the next state shi11 ~ pa((1s% af) There are three types of loss feedback that are common in the literature:
unknown
stoc.
v HH8
(Efroni et al., 2021)
REPO for tabular MDPs
unknown
stoc.
v AH'S
(Cassel et al., 2024)
Reduction to DBOLO
unknown adv.
Hi0g1aAKK
(Cohen et al., 2021b)
Algorithm 2 (ours)
unknown adv.
V HH8SAKK
In full-informatiin feedback, at the end of episode & the agent observes the full cost function 8 E [0, 1] 1AAA
is larger than ours by a factor of H. So for example the regret bound Ó(H2 (/SSVAA) in Luo et al. (2021) implies bound of O(H"SVAK) in the transition model presented in this paper. We emphasize that these differences are rather artificial and not due to an actual difference in the regret.
Under bandit feedback (a.k.a semi bandit, the agent observes the loss function over the agent's 's trajectory, {e% (s 1
Under aggregate bandit feedback (a.k.a full-bandit), the agent observes only the entire episode loss, L Eie (s), )
Stochastic binary trajectory feedback was studied in Chat- terji et al. (2021). In their model, the rewards are drawn from a logistic model that depends on features of the trajectory.
In all three settings, the trajectory {s at H is assumed to be fully observed. In this work, we assume aggregate bandit feedback, which is the least informative among the three above.
Preference-based based RL (PhRL. is a model where the feed- back is given in terms of preferences over a trajectory pair instead of rewards. This is partially related to our model in motivation. A partial list of works on PbRL includes (Saha et al., 2023; Chen et al., 2022b; Wu & Sun, 2023). For addi- tional related work on the topic, see the above references.
The goal of the learner is to minimize the regret. defined as the difference between the learner's 's cumulative expected cost and the best fixed policy in hindsight:
K
2. Preliminaries
RK =
Σ VT (Simit e*) k=1
Σ Vi (Sinses e*), k=
A Umite-horizon episodic adversarial MDP is defined by a tuple MM- = (S. H, Simit, P. { {==)) ). where and A are state and action spaces of sizes [S] S and |A| = A, respectively. H is the horizon, Sinat is the initial state and K is the number of episodes. p: S x A [H]] + As is the transition function such that P%. (s' [s, is the probability to move to s' when taking action a in state at time h. {E= S x A x [H] - [0, 1) are cost functions chosen by an oblivious adversary, where f)) (/,s a) is the cost for taking action a at (s,h) in episode k.
where nT = arg min, Σ k= VIT (Sensss (*) is the best fixed policy in hindsight.
Value difference lemma. The analysis of policy optimiza- tion algorithms often built upon a fundamental regret decomposition that follows the following lemma:
Lemma 2.1 (Value Difference Lemma (Kakade & Langford, 2002; Even-Dat et al., 2009)). For any loss function E and any policies n and x²'
A policy S x [H] + A is function that gives the probability TA (als) to take action when visiting state
VT (Simits E) - VT' (Simits E)
= Σ u (s) (TT (1)) - - 5), (1)
'This regret bound is adapted to horizon-dependent transition and losses- see the related work section for more details.
h
3

---

Near-optimal Regret Using Policy Optimization in Online MDPs with Aggregate Bandit Feedback
where (1)) is the inner product.
where (s; = B A-1 (sw, an ) x., 8n = 8).
As direct consequence we can break the regret as,
Proef. Due to the Markov property and the fact that π is Markovian policy, the trajectory up to time h - 1 does not depend on the action taken at time h. Thus,
Rg= Σn
1h (s) 2 (
(..
h
U a; (%,
where, for each h and 8, the internal sum over & can be seen as regret of a Multi-armed bandit problem with respect to the loss vectors (%,
h-1
=
E
Pas (sh', and)
rt, 8T 8h = 8, an = a
Additional notations. Episode indices appear as super- seripts and in-episode steps as subscripts. The notations O() and & hide poly-logarithiic factors including log( K/6) for confidence parameter 8. [n] = (1.
E
e (sw, on) ) = (s;
The indica-
tor of event E is I{E) and we denote ()) I(s
(4 when the policy and cost are x² and gh respectively. The
8, af = =). We use the notations (s),
As a corollary of Lemma 3.1 we obtain the Value Difference Lemma with respect to the U-function.
expectation conditioned on the policy T² is denoted by Ex.
Corollary 3.2. For any loss function i and any policies and n',
3. The U-function
VT (Simit; 8) - VT (sinit; E)
Policy Optimization algorithms build upon the Value differ- ence lemma, but since the Q-function is unknown (due to the bandit feedback), one would need to estimate it. The state- of-the-art PO algorithm for semi-bandit case (Luo et al., 2021) estimates the Q-function via importance sampling:
- (1) (TT 8) - - 8), (T,,
h,s
Proof. For each h and 8, Eo Tn(a 8) = E. (a 8) 1. Thus,
(7, a; 118h- 00 = 8) LhcH
(T (8) - (3) (7(,,;))) (mT(aa [s) - ss) =0
1T a)
where Lh:H En- le (shr, axe ) the realized loss-to- go from time h. To be more precise, (Luo al., 2021) add small bias the denominator to better control its variance and use an upper confidence bound of 2o7 (s, a) whenever the dynamics is unknown. Indeed (7, a; E) is an unbiased estimate of Q7 (s, a; f). Note that with aggregate bandit feedback LR.H cannot be computed and it becomes unclear how to directly estimate the Q-function. For this reason we introduce a new quantity which we call the U-function. While the Q7 a; E) is the expected cost-to-go from time given that we visit state s perform action a at that time; the U fffnctiion is the expected cost on the entire trajectory given that we visit and perform time h. That is,
Adding the above for each h and & in the sum on the right- hand side of Equation (1) completes the proof.
As in the Q-function case, a direct consequence is that we can break the regret as,
RK = Σ UT (s)
Σ ( 8) x (s), U
where similarly to other notations, we slightly abuse nota- tion and write Uf(ss, a) = UR (s, a; e*).
In the context of aggregate bandit feedback, the U-function is much more useful as can be estimated using the loss of the entire trajectory. In particular, the following is an unbiased estimator of UK (s. a; E):
H
Ug a: = E
Σ
(sr, an)) 87 0,00 = a
The following lemma shows that the difference (R(s, a)- (5(s,aa a) does not depend on a. Lemma 3.1. For any Markovian policy n. loss function and (h, 8, a) E (H] x A x S,
(K az f) 1[sh s. Op LS.
11 (8,a)
= HM (s on) is the aggregated feedback of the trajectory. Later in the algorithms, we will use an optimistic variant of this estimator.
where -
(s =)
4

---

Near-optimal Regret Using Policy Optimization in Online MDPs with Aggregate Bandit Feedback
4. Known Dynamics
Algorithm 1 Policy Optimization with Aggregated Bandit
Feedback and Known Transition Function
Our algorithm is based on the regret decomposition in Equa- tion (2). Each internal sum can be seen as regret of bandit problem with loss vectors ( (s,-). Thus, we run Multi- plicative Weight Update with respect to estimate of the U-function that uses only the aggregated trajectory loss:
Input: state space S, action space A. horizon H, learning
rate 1) > 0, exploration parameter Y > O, confidence
parameter >> 0.
Initialization: Set n (a s) 1/A for every (h, [H] x x x A.
(. Th (- s) x exp(n(U, - (s. Here is a learning rate, ÜK is the estimate of the U-function and B* is some bonus function that we'll define later. The estimate of the U-function is defined by,
for k: k= 1,2,.... K do
Play episode k with policy nhth and observe aggregated bandit feedback LĀ.H
2hm e (s%, dt)).
(s) = 11(sa)) Li.1
a (2(0)))+7
# Bonus Computation
Set B #++ (s, a) 0 for every (s, E ES A.
(s,a) a) (5(s, +
(s)
1
(3)
for h = H, H ...... do
for (s. E ES x A do
(s) = EnEA 3yHnilala] (G
where 7 ((/VKK used to reduce the variance of the estimator. We note that in the known dynamics case μ (s, a) can be easily computed using dynamic programming.
B (8, 0) = (1))
+2 L' Ph (s' s, s,a) (a' (
end for end for # Policy Improvement
Note that the regret decomposition in Equation (2) is av- eraged with respect to the state occupancy of π*, while the second moment of the estimator is roughly scaled in- versely with the state occupancy of オ². In order con- trol this distribution mismatch, we reduce from our U- estimate bonus term B (+s a) similar to Luo et al. (2021). B (s, a) is essentially a Q-function with respect to a known loss function 1²*_ In the known dynamics case we set (all) (s) = EaEd ([)))))))())))>> where the reason for this particular choice will become clearer later in the amalysis. B (s, a) is computed using standard Bellman equations (e.g., as in Lancewicki et al. (2023)), which is simpler and more intuitive than the dilated version of Luo et al. (2021).
For every (8, h)) E 8 X Ax [M]:
at s)e ( Ex (00 (x
Th + ()
end for
Lemma 4.2. Under Algorithm for any h, s, a and k.
()),)) (k(s,)) +7 (k(s,a)
E& (t(),aa
Theorem 4.1. Under known dynamics, running Algorishum with nj (HVSAK- + /²)K)- and y Hn, guaran- tees with probability 1- 8.
Proof. By definition Pr(TT)(s, a) = | -( Us- ing the law of total expectation and the fact that (s) = O whenever I1 (s. a) = 0 we get.
(1,
Rx S Ō(H + HiVK).
Es [ a))
Es [ū) ()) = 1] (
If SA> H² (which is typically the case since for any prac- tical application S > H), the first term dominates and our bound is optimal up to logarithmic terms. A straightfor- ward reduction of our problem to linear bandits that uses the efficient algorithm of Hazan& & Karnin (2016) guarantees expected regret of Ō AVK). Our algorithm improves that by a factor of VSA and guarantees regret with high probability rather than only in expectation. In addition, our algorithm is more computationally efficient since it has closed form update opposed to the reduction that requires solving convex optimization problem in each iteration.
+ Rx (U)(s,)) a) 1 a)) 0] (1 - -
Σ# Σ#= of (ste, a
[1((,)))= =1 | ( a)
Ex
[
1 u)(s,a)+ +Y
a)( E2
H
Σ
e C atte 1/ 8, a =
a)) +
Lin=h
_
()(
(1) + U Uf((ss,))
Before we outline the proof of Theorem 1. let us first show that (s, a) is a nearly unbiased estimator of U/A (s, a).
Given our novel regret decomposition in Equation (2) and
5

---

Near-optimal Regret Using Policy Optimization in Online MDPs with Aggregate Bandit Feedback
the lemma above, the of the analysis follows similar steps as those in (Luo al., 2021).
(Lemma E.5), REG can be bounded by,
H In A
+ 2n
Σ
(a)) s) - Bx(,
Proof sketch of Theorem 4.1. Using Equation (2), we can break the regret of the algorithm follows:
k,h,
Ö H 17
H K
+ 2n
Σ (4(5) ()) k,,,,,a
E (s) ( 18) -
In the inequality we ve used the fact that (s) S 3H, and thus, (x, S 3H² since it is a Q-function with respect to (s). Once again, the second sum here may not be bounded due to the mismatch between (1) and (*) in the denominator of U (s, a). However, note that Ex [ (s, a)² S /²/ + 7) and using standard concentration inequalities we can bound the the last term in the last display by.
BIAS1
+ Σ (1(()) ( 6), 6), (b.,)) -(,o,,))
k.h.o
BIAS2
+ Σ (s)
(Th(( () Th(- s), (s:-) Bk(,,))
8,8
REG
(((s)
H3 +0 11 72
+ Σ (1(ss (T+(() - 8), k.h.a
(s,
(4)
27H
Σ h.h...o
a) +7
H²
BONUS
Σ hrh,s
M
(
+0
From Lemma 4.2 we immediately get that E& [BIAsy] I O. Since ||Ù] 10x0 < H/7 we can also bound with high prob- ability BIAS2 I Ô(H²/m/ /n) using standard concentration bounds (see Lemma B.4), Again, using Lemma 4.2 the expectation of BIAS, equals the following,
?
(66)
where we' ve set 17 (2H) as in the statement of the theo- rem. Finally, recall that B) is the Q-function with respect to I as losses. Applying the standard value difference lemma (Lemma 2.1) we have,
K
E E
(((s) I () (UR(s,a) - Ex [OR(s,a)))
BONUS = Eve (Sinits Bb) V (Simit; by))
1= hisaa
Σ Σ (((s)=((a ()) (1-
Σ (1))))))))))))))))))))))))))))) k.h.s
Σ (s)
14, (s)
k=1 1,,sa
k.h.a
ΣΣ (s()) (mt(al 1,,8a
The negative term exactly cancels out (i) and (ii) from BIAS; and REG. The positive term is bounded by,
an( +7
Bounding as) by H get that Eg BIAST] EKk En, 17, (s) Using a form of Freedman's 's inequality that takes into account the second moment of the estimator, can also bound BIAS; E& [BIAS]] & >K En,s 17, +
K ΣΣ (( (s) k=1k,sa 14 (s) +)+ S &3H1SAK.
3yH
Summing all the terms and setting n and y as in the state- ment of the theorem completes the proof.
+
total we get that,
K ΣΣ (s()))
Computational complexity of Algorithm 1. The state occupancy measure can be computed using the following recursive formula:
BIAS] <
k=1 h.8
(5') Σ [MA(s)ma(a s)P(s ss,a),
Term (i) is challenging due to the distribution mismatch be- tween 11 (s) and n (s) in the denominator of U/ (s). How- ever, we will later see that the BONUS term will cancel it
S.a.
so that the full occupancy measure can be computed in O(HS²A). The bonus 8* is calculated via backward dy- namic programming also in (HS2A)), and the policy com- putation is done in O(SA)). Thus, the total complexity per iteration S2 A).
out, essentially allowing us to replace (s) with μ (s).
Before we turn to the BONUS term, let's consider REG. Using the standard regropy-re OMD guarantee
6

---

Near-optimal Regret Using Policy Optimization in Online MDPs with Aggregate Bandit Feedback
5. Unknown Dynamics
Algorithm 2 Policy Optimization with Aggregated Bandit
Feedback and Unknown Transition Function
The adaptation of our algorithm to the unknown dynamics case is relatively straightforward. Since we do not know the transition function, we cannot compute い² and can't perform the Bellman backup in the computation of B* As standard in the literature, we employ Bernstein-style confidence sets for the transition function (e.g. Shani et al. (2020); Luo et al. (2021); Jin et al. (2020)). Specifically, let pk = {Pk (s, a))a such that (- s, s, E (s, a) if and only pl. (- 8, a) E As and for every s' E
Input: state space S, action space A, horizon H, learning rate 1) > 0, exploration parameter 7 > 0, confidence
parameter >>
Initialization: Set TT (a s) = 1/A for every (h, s, o) for k = 1, 1.2..... ...... K do
Play episode k with policy T. and observe aggregated bandit feedback LÍ. > e
(sh,, of)
F (s) = maxp'ps Hh (s)
(s) (s)
x (s)
= EPp Ph
(s' s, s,a)
(5' s.a)l
(s, (=(00)++7
Li. 1 (s,a)
S 41 (s' s, a) log 10HSAK
10 10HSAK
# Bonus Computation
(3 V1
(
Set B #+ (8, a) = 0 every (8, (
for h = H, H - -l..... do
where n (s. a, s') is the number of times we visited s, a at time h and transitioned to s', n1, a) = E.. n as,)),)) and (5 s,a) = (s, a, s') s))/n/( (s, a) is the empirical transition probability. Based on Pt, we replace p in the definition of (s, with an upper confidence bound T (s) == pa p. 'p' (s) (see Algorithm 3). Here, the notation 1%
for (s, a) E ES x do
by (s) = EnEd HyHal(als)
(s)) = EnEA H g((aa))
(
(s) = (7(s) + (s)ss)
x* x (s) represents the occupancy measure with respect to the transition p' (instead of p). The local bonus (s) is adapted correspondingly and is exactly as in Luo et al. (2021)- see definition in Algorithm 2. Finally, the bonus 3* is estimated optimistically based on the transi- tion p' E Ph that maximizes it, described in the update computation of 3 in Algorithm 2.
(s, a) = (s)
Σ
ph(l') 8, a)) (d') (s))
+ max
p' p'EPt(H,)) S'S,e'
end for end for # Policy Improvement For every (s,a, 6 5 Ax [1]] by:
The regret guarantee of our algorithm is established in the following theorem.
Theorem 5.1. Under unknown dynamics, rumning Algo- rithm 2 with r = (HKSAK + H²VK)-1 and y = H,, guarantees with probability 1-
Ta ()e= Ew |s) (00
* l 8)
RK S Ō(HHSVAK + A)) A
end for
The second term of the regret is typically of low order for sufficiently large K. The above regret improves upon Cohen et al. (2021b) by factor of H A and provides high- probability regret bound instead of an expected one. Cohen et al. (2021b) uses a reduction to distorted linear bandits and requires solving a convex optimization problem in each iteration. In contrast, our algorithm benefits from a more computationally efficient, closed-form update. Our bound also improves upon Efroni et al. (2021) and Cassel et al. (2024) for the case of tabular MDPs by factor of SAVH even though they consider stochastic i.i.d losses opposed to adversarial losses in our setting. The gap from the lower bound is factor H SS, but it is worth noting that even in the remi-bandit case, the best-known regret is S/SS (Jin et al., 2020) which is achieved by a less efficient occupancy- measure-based based algorithm. In fact, even though we consider
less informative feedback, we match the state-of-the-ar regret for PO with semi-bandit feedback (Luo et al., 2021).
The proof of Theorem 5.1 follows similar steps in the known dynamics case, but includes additional steps to con- trol the transition estimation error. These utilize standard techniques that we highlight in the following proof sketch.
Proof sketch. We utilize the same regret decomposition as in Equation (4) but replace B& with L* in the Reg and Bonus terms. The estimator & remains optimistic (i.e., in expectation it is smaller than U² since with high probability (s(ss) Z (s)s for any s, and k. Thus, BIAS₁ S O(H²/7) with high probability in a similar way to the known dynamies case. In Bias 1, on the other hand,
7

---

Due to space limitations, the proof is deferred to Ap- pendix D. At a high level, the proof is constructed as follows: Consider an MDP where in the first step of each episode, the agent transitions each state with an equal probability of regardless of the chosen action. From the second step onward, the agent remains in the same state for the remain- der of the episode, wherein a hard multi-task bandit problem is encoded in each state. Roughly speaking, each state is visited approximately K/S times. Using Lemma 6. the re- gret from visits to each state is approximately H² H2 VAK/S. Summing the regret across all states gives lower bound of Near-optimal Regret Using Policy Optimization in Online MDPs with Aggregate Bandit Feedback
using (6) instead of (5) introduces additional bias of order of,
Computational complexity of Algorithm 2. The up- per/lower confidence occupancy measure computation can be done using (Jin et al., 2020, Algorithm 3), with com- plexity of OHS A) per state. The same can be done for the computation of the bonus B*. The policy update is done in (H)))). Thus, the total complexity per iteration is O(HS*A) A).
Σ (T))aa((a s)H H) (s, (s) k,,,
ph(s,a) a) +
Σ ([ s) (s 12 (s.0) k,h,a,a
()) +7
6. Lower Bound
where the inequality follows from the fact that L (s,a) $ (s,))) w.h.p. Note that this is exactly Exhhs, 1 (8)0 (+). This term is in addition to the terms we already had in Biası in the known dynamics case. In total we have,
Our lower bound uses a lower bound for the multi-task bandit problem (see for example Lattimore & Szepesvári (2020)). In the multitask bandit problem, the learner faces simultaneously H instances of the A-armed bandit prob- lem. At each round k E [K], the learner selects ac- tions, one for each bandit problem, and observes the sum of the losses associated with these H actions. This scenario can be seen as analogous to MDPs with a single state (i.e., S = 1) and aggregate bandit feedback. This is due to the fact that whenever we have only single state no informa- tion is gained within the episode. (Recall that the losses are horizon- dependent,, so we have (Su, a). for each action o, time h E [H] and using the single state su-)
H1²
BIASI S 3
E (+)++ k,b,
E (6) k.b,
Reg is bounded in a similar way to the known dynamics case. Given that the estimator is optimistic and exhibits lower variance when using the upper confidence bound on the occupancy measure, we get that Reg is bounded by,
Lemma 6.1 (Theorem I in Cohen et al. (2017)). Assume that A 2 2. Any learning algorithm for the multi-task bandit problem must incur at least 91 H2 (AK) expected regret in the worst case.
Hnn + 16 K + 3
E (s) + k,h.s
H 7
7
Finally, note B* is not an exact Q-function since we don't it know the actual transition function. Thus, can not directly use the value difference lemma to show that Bonus = Ex,,, 1 (s)bf (s) - Ek,h, M7, (s). How- ever, using the fact that we update B with a transition func- tion the confidence set that maximizes it, we are able to show that w.h.p.
With that in hand, we obtain the following for online MDPs with aggregate bandit feedback.
Theorem 6.2. Assume that H, H,S, S, 2 and K 2 2S. Any learning algorithum for the online MDPs with known dynam- ics and aggregate bandit feedback problem must incur at least Q(112 expected regret in the worst case.
The above lower bound shows that our regret upper bound for the known dynamics case is tight up to poly-logarithmic factors whenever VSA 2 H. For unknown dynamics, clearly the same lower bound holds, and we have a multi- plicative gap of H /S. We note that determining the exact optimal bound for the unknown dynamics case remains an open problem, both with aggregate bandit feedback as well as with the well-studied semi-bandit feedback.
BONUS < Σ (T( k,
Σ ( k.h,
Once again, the negative term above cancels the terms that depend on by in Biasi and Reg. Recall that (s) = (f (s) + (s). Exactly as the known dynam- ics case, ERA,, a T (s) s ((HH?SAK). The term En,,, (8) (s) equals to,
a) 1 ()) Thi a) +
H Σ (s)
h,h.
H
(n)(s, 1 (x, a)l-
k,h.8
The last is a standard transition estimation error and is bounded by Ö(H AK + H² A) (Jin et al., 2020). Summing all the terms and setting and y as in the state- LI
ment of the theorem completes the proof.
8

---

Near-optimal Regret Using Policy Optimization in Online MDPs with Aggregate Bandit Feedback
HAVSAK.
References
Abernethy, J. D., Hazan, E., and Rakhlin, A. Competing in the dark: An efficient algorithm for bandit linear opti- mization. In COLT, pp. 263-274. Citeseer, 2008.
7. Discussion and Future Work
In this paper, we introduced the concept of U-functions, which allows us to establish the first regret bounds for online MDPs with aggregate bandit feedback using PO algorithms. One of the advantages of the PO framework is its natu- ral extension function approximation (Luo et al., 2021; Sherman et al., 2023; Dai et al., 2023; Liu al., 2024).
Beygelzimer, A., LLngford, J., Li, L., Reyzin, L., and Schapire, R. Contextual bandit algorithms with super- vised learning guarantees. In Proceedings of the Four- teenth International Conference on Artificial Intelligence and Statistics, pp. 19-26. JMLR Workshop and Confer- ence Proceedings, 2011.
It would be interesting to see whether the U-function con- cept could be useful in achieving regret bounds with aggre- gate bandit feedback for environments with infinitely many states under a function approximation assumption. We note that the main challenge in extending our results linear MDPs, for example, is that the U-function is not linear der this assumption. Still, it is possible that in such settings, the U-function would have certain properties that would allow achieving sub-linear regret.
Bubeck, S., Cesa-Bianchi, N., and Kakade, S. M. Towards minimax policies for online linear optimization with ban- dit feedback. In Conference on Learning Theory, pp- 41- 1. JMLR Workshop and Conference Proceedings, 2012.
Cai, Q. Yang, Z., Jin, C., and Wang, Z. Provably efficient exploration policy optimization. In International Con- ference on Machine Learning. pp. 1283-1294. PMLR, 2020.
Moreover, it would be interesting to study the incorporation of the U-function deep reinforcement learning algorithms and explore whether can provide practical benefits or im- proved performance in large-scale, real-world RI. problems with aggregate bandit feedback.
Cassel, A., Luo, H., Rosenberg, A., and Sotnikov, D. Near- optimal regret in linear MDPs with aggregate bandit feed- back. In International Conference on Machine Learning, pp. 5757-5791. PMLR, 2024.
Acknowledgments
Cesa-Biance N. and Lugosi, G. Combinatorial bandits. Journal of Computer and System Sciences, 78(5): 1404- 1422, 2012.
This project has received funding from the European Re- search Council (ERC) under the European Union's 's Horizon 2020 research and innovation program (grant agreement No. 882396), by the Israel Science Foundation, the Yandex Initiative for Machine Learning at Tel Aviv University and grant from the Tel Aviv University Center for Al and Data Science (TAD).
Chatterji, N., Pacchiano, A., Bartlett, P., and Jordan, M. On the theory of reinforcement learning with once-per- episode feedback. Advances in Neural Information Pro- cessing Systems, 00::340133411 2021.
Chen, L.., Luo, H., and Rosenberg, A. Policy optimization for stochastic shortest path. In Loh, P. and Raginsky, M. (eds.), Conference on Learning Theory, 2-5 July 2022, London, UK, volume 178 of Proceedings of Machine Learning Research, pp. 982-1046. PMLR, 2022a
Impact Statement
This paper presents work whose goal is advance the field of Machine Learning. There are many potential societal consequences of our work, none which we feel must be specifically highlighted here.
Chen, X., Zhong, H., Yang, 7.,, Wang. 7., and Wang, L. Provably efficient preference-basee reinforcement learning with general function approxima- tion. International Conference on Muchine Learning, pp. 3773-3793. PMLR, 2022b.
Cohen, A., Hazan, T., and Koren, T. Tight bounds for bandit combinatorial optimization. Conference on Learning Theory, pp. 629-642. PMLR, 2017.
Cohen, A., Efroni, Y., Mansour, Y., and Rosenberg, A. Min- imax regret for stochastic shortest path. Advances in Neural Information Processing Systems, 34, 2021a.

---

Near-optimal Regret Using Policy Optimization in Online MDPs with Aggregate Bandit Feedback
Cohen, A., Kaplan, H., Koren, T., and Mansour, Y. Online Markov decision processes with aggregate bandit feed- back. In Conference on Learning Theory, pp. 1301-1329. PMLR. 2021b.
Lattimore, T. and Szepesvári, C. Bandit algorithms. Cam- bridge University Press, 2020.
Liu, H., Wei, C.-Y., and Zimmert, J. Towards optimal regret in adversarial linear mdps with bandit feedback. In The Twelfth International Conference on Learning Representations, 2024.
Dai, Y., Luo, H., Wei, C.-Y., and Zimmert, J. Refined regret for adversarial MDPs with linear function approximation. In International Conference on Machine Learning, pp. PMLR, 2023.
Luo, H., Wei, C.-Y., and Lee, C.-W. Policy optimization in adversarial MDPs: Improved exploration via dilated bonuses, Advances in Neural Information Processing Systems, 34, 2021.
Dani, V., Kakade, S. M., and Hayes, T. The price of bandit information for online optimization. Advances in Neural Information Processing Systems, 20, 2007.
Rosenberg, A. and Mansour, Y. Online stochastic short- est path with bandit feedback and unknown transition function. In Advances in Neural Information Processing Systems, pp. 2209-2218, 2019a.
Efroni, Y., Merlis, N., and Mannor, S. Reinforcement learn- ing with trajectory feedback. In Proceedings of the AAAI conference on artificial intelligence, volume 35, pp. 7288- 7295, 2021.
Rosenberg, A. and Mansour, Y. Online convex optimization adversarial Markov decision processes. In Interna- tional Conference on Machine Learning, pp. 5478-5486. PMLR, 2019b.
Even-Dar, E., Kakade, S. M., and Mansour, Y. Online Markov decision processes. Mathematics of Operations Research, 34(3):726-736, 2009.
Saha, A., Pacchiano, A., and Lee, J. Dueling rl: Reinforce- ment learning with trajectory preferences. In Interna- tional Conference on Artificial Intelligence and Statistics, pp. 6263-6289, PMLR, 2023.
Hazan, E. and Karnin, Z. Volumetric spanners: an effi- cient exploration basis for learning. Journal of Machine Learning Research, 2016.
Hazan, et al. Introduction to online convex optimization. Foundations and Trends@ in Optimization, 2(3-4):157- 325, 2016.
Schulman, J., Levine, S., Abbeel, P., Jordan, M., and Moritz, P. Trust region policy optimization. In International conference on machine learning, pp. 1889- 1897, 2015.
Jaksch, T., Ortner, R., and Auer, P. Near-optimal regret bounds for reinforcement learning. Journal of Machine Learning Research, 11(4), 2010.
Schulman, J., Wolski, F., Dhariwal, P., Radford, A., and
Klimov, O. Proximal policy optimization algorithms.
arXiv preprint arXiv:1707.063477 2017.
Jin, C., Allen-Zhu, Z., Bubeck, S., and Jordan, M. I. Is Q-learning provably efficient? In Advances in Neural Information Processing Systems, pp. 4863 4873, 2018.
Shani, L.,, Efroni, Y., Rosenberg. A., and Mannor, S. Op- timistic policy optimization with bandit feedback. In International Conference on Machine Learning, pp. 8604 8613. PMLR, 2020.
Jin, C., Jin, T., Luo, H., Sra. S., and Yu, T. Learning ad- versarial markov decision processes with bandit feedback and unknown transition. In International Conference Machine Learning, pp. 4860 4869-4869, PMLR, 2020.
Sherman, U., Koren, T., and Mansour, Y. Improved regret for efficient online reinforcement learning with linear function approximation. In International Conference on Machine Learning. pp. 31117-31150 31150. PMLR, 2023.
Kakade, S. and Langford, J. Approximately optimal ap- proximate reinforcement learning. In In Proc. 19th In- ternational Conference on Machine Learning. Citeseer, 2002.
Wu, R. and Sun, W. Making rl with preference-based feed- back efficient via randomization. In The Twelfth Internu- tional Conference on Learning Representations, 2023.
Kakade, M. A natural policy gradient. Advances in neural information processing systems, 14:1531-1538, 2001.
Zimin, A. and Neu, G. Online learning in episodic Marko- vian decision processes by relative entropy policy search. In Advances in Neural Information Processing Systems 26, pp. 1583-1591, 2013.
Lancewicki, T., Rosenberg, A., and Sotnikov, D. Delay- adapted policy optimization and improved regret for ad- versarial mdp with delayed bandit feedback. In Inter- national Conference on Machine Learning, pp. 18482- 18534. PMLR, 2023.
10

---

Near-optimal Regret Using Policy Optimization in Online MDPs with Aggregate Bandit Feedback
A. Summery of notations
For convenience, the table below summarizes most of the notation used throughout the paper.
H
Horizon length of each episode
K
Total number of episodes Number states in the MDP Number of actions in the MDP Transition function of the MDP Loss function in episode k Cumulative regret over K episodes
S
A
p
dk
Rg
(s;
Value function at state and time under policy и and loss function
(5)
Value under policy n* and loss function t Le.. Vit (s) V/," (s; e*) Q-function at state 8, action a, and time h under policy and loss function e
(s,a)
Q-function under policy n/ and loss function e Le., (s, a) = Q (s, a; (*) Expected total loss of the episode, conditioned on taking action a in state at time under policy m
(),0))
as,
Conditional expected total loss with respect to x² and e Le.. U,, (s.
U (s, a; (=)
(x;
Expected cumulative loss up to time h - 1, conditioned on reaching state at time under policy m
(s)
Conditional expected loss with respect x² and t Lee, (s) W (s;
(s,
Occupancy measure: probability of being in state and taking action at time h under policy x Occupancy measure under n²: (s. a) = M (s,a)
(s)
Ph (s)
Occupancy measure with respect to a transition function p'
E.Hl
Expectation condition on the policy  E&1-] E[- .²1
as)
The indicator for visiting and taking a at time episode k: (8, a) = 11 8, a = a}
(s,a)
Estimator of U// (s, a) See Algorithms and 2 Intermediate bonus function See Algorithms and 2
(s)
(s,a)
Bonus function, defined as the Q-function with respect to b See Algorithm Estimator of B (8, a) See Algorithm 2
(s,aa
pk
Confidence set of transition functions at episode k
(s)
Upper confidence bound on the occupancy measure See Algorithm 2
E (3,0)
Lower confidence bound on the occupancy measure See Algorithm 2
A logarithmic factor of log HSAK

---

Near-optimal Regret Using Policy Optimization in Online MDPs with Aggregate Bandit Feedback
B. Known Dynamics
Theorem B.1 (Restatement of Theorem 4.1). Under known dynamics, running Algorithm I with 1j
VI HVSAR HAVR H
and
7 2nH for i log # guarantees with probability 1 8. 8.
Rx S HAVSAKL+ H
Proof. Using Equation (2), we can break the regret of the algorithm as,
K
Rx=
(8)
( 5) - (6, (6),
k=1 h.8
K
Σ
Σ (s) (- s), (h,,)) - (s (s.-))
Σ
u (1(s) ( (1.(11)..00 (/,, U
1=1 h,8
km h
BIAS1
BLAS2
P ( T 8) - m s), (s. (s.
(i() ( m 8), (s, )))
b,5
BONUS
Due to the optimism of the estimator BIAS² S Ö(H²/7) under the good event G3 which holds with high probability (see Lemma B.4). In Lemmas B.6 B.8 we bound BIASI, REG and BONUS. Overall we get that,
Hln
H
Rk 2
+ n K + SAK +
7
Plugging 1) and 7 completes the proof.
B.1. Good event
We define the following good event G = Ni G. which holds with high probability (Lemma B.5):
22 log
G
Σ (M(s)T((a) s) (Ex (UM(s,a) a)] (5(s,a)
(s)
h.s,a
(s) () [1 8, a =a
H In 6H
G2
-1
a) () +
272
h.8.a
2²
6H
G3
Σ (i((s) (- 5), - b,s
ln
27
8
Under the good event the regret will be deterministically bounded. Lemma B.2 (Event G1). With probability -, 5,
K
Ü (s) - (s) a)) < (s)) + H2 Es
K
Σ
(a)))
3
Amm haa.a
km
h,
Proof. Let Yv= = En.Ht(s) ( ( | s), (s, .).. Note that [x([X]] Yx a martingale difference sequence. To bound
Σe E. [Vk) -E Ye we'll use a form of Freedman's Inequality (Lemma E.2). For that, we need to bound the absolute value
12

---

Near-optimal Regret Using Policy Optimization in Online MDPs with Aggregate Bandit Feedback
of the difference and its variance. For the absolute value of the difference we have [E [Yx] Y&l S Ma) #²
For the variance, note that it is bounded by the second moment of Y;: B& (V&] Yx ) < E (2). We further bound Es [2) as follows:
)
Ex [Y2] Es
Σ (M(s) s) R,s,a
(Emterntaa 1s) hera
Σ (
s) (U
$ E
(Cauchy-Schwwer SuhhhySSchwarz inequality)
h,8,a
(s) s) (UN(s.a))
H HB
h,s,a
(2
HR
1 (s) 8) (x) + 7)2 The (s)
A,8,a
as)
< e
M (a)
(L S H)
a)
(s,
H Σ (s) 8)
(Esl1 = (s)
(s, +7)
h,8,0
Σ (s) (a|
( +
h,5.0
Using Lemma E.2 with probability 1-
log
Σ Ex - Σ Yu S a
En [Y
+
k
where a E 10) for R such that [E] Yıl < R for any k. our case, [
Y/ S H²
And so,
K
H log 1
[Y
Σ
Yv <
(s)
+
3
7
k= h,5
Lemma B.3 (Event G2). With probability 1 1-5, 5,
(A(s)T 8)
[155 (1s = = =a - 1)
H
<
k.b,a,a ()) +7 ()(s,a) +7
2n2
Proof. Follows directly from Lemma E.4 with (s, =f((s,)) = ((())a((ale) #f(x,))+
< 7
1 and (s. a))
Lemma B.4 (Event G3). With probability 5,
K
H² H
Σ M (()ss) (1))..)))) (),,)) (H. (s.s.))
2n
1= h.o
13

---

Near-optimal Regret Using Policy Optimization in Online MDPs with Aggregate Bandit Feedback
Proof. By invoking Lemma E.4 with (x, (a) (s, + - [ (s, B& (s, a)] (o and (s, = (s, a), get,
s
K
Σ
(i((s)
(s, T (s), -
k=1 4
4 (a s) (s, a) as) +Y
H² H s
Σ (1
27 8
k,s,a
k= h,
Lemma B.5. Under Algorithm 1, the good event G = Ni=1 G3 holds with probability of at least 8.
Proof. The proof directly follows from invoking Lemmas B.2 to B.4 with 8/3 and taking the union bound.
B.2. Bound on BIASI Lemma B.6. Under the good event G1,
2 K
H² log
BIASI
ΣΣ
Σ
(s)
7
4,8
Let V5 = En (h) (1k((-1).
18), (s.))))))))
K BIASI Σ
(s) ( 8), U.,
Σ R& [VR] + ΣEE [V Σ Ya
k= N.8
Under the good event G1, Ex [xN) - Ex Yu s 3 Exm En. (3) + H² log 9 Using Lemma 4.2,
K
Σ (T) ss, - E& [Va] =
(s)) 8) (U%(s,a) - E& (U)(s.))))
h.8
1= h.s,a
K
(s)T s)U?(s,a) (1- a)
a)
k=1 h,s.a
K
Σ (s) 8) -1(1- uk(o,a)
(s) s H)
()(s,a)+7/
k= h.8.0
Σ (s)ss) (H 1s)
()( +7
M,8,0
(s)
B.3. Bound on REG
Lemma B.7. For 1) < 2 2H. under the good G2,
H A
Σ (s)) +0 +0(1) (22,)
REG < n
+ *9HH K
k,h
14

---

Near-optimal Regret Using Policy Optimization in Online MDPs with Aggregate Bandit Feedback
Proof. Using standard entropy regularized OMD guarantee (Lemma E.5),
H
An
(s) s) (U)(s,a) - o)))
REG -
2n
k=1 h,8,0
H A
21
Σ
( a)) +
h,2,a
where the second inequality is since (s) s 3H and thus (s, S 3H For the middle term,
H*I($ s, a a}
20 Σ (T(()) (s) s 2n E (M())= 8)
( S H)
(s, +7)² H..
k,A,s,a
k,h,a,a
(( 18)
2n
(Under event G2)
as) +Y
0 20 H Σ (*)
Ha
11
37
k.h,s
1
Σ (s) +0
H2
$ 3
k,h,s
The last inequality is since < 27 as in the statement of the lemma.
B.4. Bound on BONUS Lemma B.8. It holds that,
BONUS S 3yH2SAK-
> (1(())))()).
k,h,
Proof. Recall that B is the Q-function of policy n² with respect to the cost function 8t, Hence, by the value difference difference lemma (Lemma 2.1),
K BONUS= Σ
Σ p (T)) 8) m, 8), (s, 1)
EVT (Niniti bb) V= (Sinit; b+)
VT
1=1 h.8
Σ (+))))))() E (s))))))(s))
k. k.h,a
For last,
K
(s) S3.
(s)) = 3
(s) 5) +7
1=1 A.
1= h.s.a
15

---

Near-optimal Regret Using Policy Optimization in Online MDPs with Aggregate Bandit Feedback
C. Unknown Dynamics
Algorithm 3 Policy Optimization with Aggregated Bandit Feedback and Unknown Transition Function
(detailed version of Algorithm 2)
Input: state space S, action space A, horizon H, learning rate 7) > exploration parameter 7 > 0, confidence parameter
O.
Initialization: Set (a s) = and visit counters (s, s') 0, (s, 0 for every (h, (h, [H] x S x
A x S.
for 1 = 1.2..... K do
Play episode & with policy n and observe aggregated bandit feedback Lt = Σ (sh, a/)
Update visit counters for every (h, s, a, s') E [H] x S A:S:
(s, a, 8 = n - ( 8') + n/ (s, a'),; ( a) = n
k- (s, a) + - (s,
Compute empirical transition function (s' s.
(x.o.) and confidence set pk (Pl a) baah such
(a.add)
that (- s,a) (s, if and only if >. (s' s,a) = 1 and for every s' E'E S:
( s, s,a) 10HSAK
10 10HSAK
(8' (s,a) - (s' 8, [8,a)] < 4V
(x V1
(s a) V1
Compute occupancy measures (7) (s) maxpep 14 x (8) and (s) min " x" (s).
Policy Evaluation
(f,ssa) a) 7 (..a)+ (s,a)
Lis
Bonus computation
Set B (s, a) = 0 for every (s ESXA.
for H,
1, 1,
for (s,a) a) E S A do
ig (s) = EaEA (alls ((()))((a))))7
[+s)==ock = EoEs
(1.))) (s.a)))
(s) (})) + bk(s).
(s, a) (s) + max. EvesweAth (,,)) (s) a').
end for end for
# Policy Improvement
Define the policy k+1 for every (s, E A H by:
aa s)exp (-m(O) (s)
(s, a))
k+1 (a T
s)
Evee ahla (a' 8) exp (-n(U)((, (s)))
end for
Theorem C.1 (Restatement of Theorem 5.1). Under unknown dynamics, running Algorithm 3 with 1) and 7 = H, guarantees with probability 6,
Vi
HU
Rk S H 3
16

---

Near-optimal Regret Using Policy Optimization in Online MDPs with Aggregate Bandit Feedback
Proof. Using Equation (2), we can break the regret of the algorithm as,
K Rx=
Σ
(s)
( 5) 17)
k=1 h.o
K
(s) ( s), Ux(,, U% (s.
(s) (s)
1=1 A,o
A,o
BIAS1
B1A52
K
K
(s) x 8) m (8), - (s.-))
(1(0) m/6 18), (x 1),
A=11 h,
R=1
b
REG
BONUS
Due to optimism of the estimator BIAS₃ S Õ(H²/2)) /n) under the good event G3. In Lemmas C.7, C.8 and C. we bound BIASI, REG and BONUS. Overall we get that,
K
K
H22
122
RK 5
Pi (8) +
m ()) +0
+
3
7
k=1 b,e
k=1 h.e
BA15
BAIS1
HIn A
1 Σ
(M()) +0 (1TTSK+ + H²
(
7
3
ki,
REG
+ O (7 + H ( A1²)
Σ Σ (s)
k=1 h.s
Hln A
H² + +HH&SA + k
0
q it TTSVAK. H'
1
Plugging y) and 7 completes the proof.
C.1. Good event
We define the following good event G Ni G; which holds with high probability (Lemma C.5):
17

---

Near-optimal Regret Using Policy Optimization in Online MDPs with Aggregate Bandit Feedback
V(h, s,,, h). lph(s' (s,a) - (s s, V ph s, s, log GHSAK
log GHSAK 5 max a); 11
G1
8 ax) 13
+ 10
Σ as, (s) 5o 5o | log
6KHSA
6KHSA
G2
+ SH
h,8,a,k
2 log
G3 =
(s) 8) Ex [Ut(s.a) - (s))s) -
Mr (s) +
1= h,e.0
R=1 h,
(T(s) 8) = =, =o]
(a( 13)
H In 27 2
G4
(0) a) +7)
(s) +7
k= h,8,a
K
H²
6H
Gs =
(s) Th( 1s,
s),0k, (s,,)) U 1 27
In
1=1 h,s
Under the good event the regret will be deterministically bounded.
Event G1 holds with high probability by standard Bernstein inequality (see, e.g., Lemma 2 in Jin et al. (2020)). As consequence of event G1, p E pk for all k. particular, /4h a) 2 (s a) for all k h, s and a. G2 Holds with high probability by a standard techniques by Jin et al. (2020) of summing the confidence radius on the trajectory. G3, G4 and Gs follow similar techniques as Luo et al. (2021), adapted to our case.
Lemma C.2 (Event G3). With probability 1 8.
K
K
H [olog
Σ Σ (t ()) (Ex Ü (ss(ss) a)) - 0 (s, a))
5 Σ
p
(s) +
3
1= h.a.a
k=1 h,
Proof. Similarly to Lemma B.2, let Y2 = Ens ( ( s), (R(,,))) :). To bound
Στ Ex (Yg) Ex Yr we'll use
18

---

Near-optimal Regret Using Policy Optimization in Online MDPs with Aggregate Bandit Feedback
form of Freedman's 's Inequality (Lemma E.2). For that need to bound B& (Y [+
E& (Y² E& (Y+))) - E
Σ (1((s) I o)08(660))
E
4,8,0
Σ (((o)m((al))) 1s))
Σ ()(() a) (o)()))))
< Ex
(Cauchy-Schwarz)
A,8,a
(a) s) (Dt(s.a))
HEa
h,3,a
(2
H
Σ (h)))
(p) + t) (3)
h,s,a
as)
< H S
(a
(L S H)
(x))s))+ 7)2
H Σ (1
(Ex = as)
(1, +
h,8,0
T s)
S H
(s)
(p a) s (h a) under G1)
The (s, +7
h,8.0
By Lemma E.2 with probability 1-
log
Ex|Yd| - Σ Yv a Σ [Y, - E&(x))) Σ
k
where a E (0,1/R) for R such that Y - [Yx]] < R for any k. In our case, IY - E& [YA] & H2/y And so,
H log
Σ Ex(Y Σ Yv
(s) +
7
k
k=1 8.6
Lemma C.3 (Event G4). With probability
14 (3) () 8, at a)
1 (s) (a 1))
H H
3
(1 (8, a) 7)²
(s, a) +
2-
R99,a
Proof. Follows directly from Lemma E.4 with with a))
= (s) = (a(e) p((a)))
S and (s, = (s,
Lemma C.4 (Event G5). With probability - 6,
K
H²
(1)ss) ( (s). (f(ss) -()(s))) <
1n
27
1=1 h.s
19

---

Near-optimal Regret Using Policy Optimization in Online MDPs with Aggregate Bandit Feedback
Proof. Similar to Lemma C.4, we invoke Lemma E.4 with (8, (a(s)) (s, (1 (s)s o)] < H, (s, a) Ex (x, a)] (a) (s, a) and (s, = [s a), get,
K
Σ Σ
mi(s) Th 1,) U}(,,))
1=1 4,8
(4(5)) ()) (3,
H² H
Σ> (4(ss) (s,) (s) S
( +7
27
h,s,a
A,8,0
Lemma C.5. Under Algorithm 3, the good event G Di. G3 holds with probability of at least 6.
Proof. The proof directly follows from invoking Lemmas C.2 to C.4, E.6 and E.7 with 6/5 and taking the union bound.
C.2. Bound on BIASI Lemma C.6. For any h, s, and k
E (s, n*] (s,a))) Uk ( a) +7
Proof. By definition (s, = n*) (s, Using the law of total expectation and the fact that (s, 0 whenever (s,a) a) 0 we get,
En ())()a)) Ex (s,(s)) ()) =1] ()) + +EN (s) (s, a) -0] 0 ()))))
Σ# (sh,
11 a) = =1] (s)
Ex
as) +7
()) ER
Σ
ot = s, ox a
a)) +7
o) ( (s)
(1(8,))+7 +7
Lemma C.7. Under the good event,
2 K
K
H2
+ E E EE'.OO (s)8%) + O
BIASI I
7
k= A
R=1 A.
Proof. Let Yg = En. (5) (mt(() 1 s), (s., ))) It holds that,
K
K
K
BIAS = ΣΣ
u (s) (T 1.) ().
Σ
E.
Vil +
Yk-
1=1 h.s
1=
k=1
k=1
Under the good event, G3. it holds that
K
K
K ΣΣ
H² 10
1 (s)
7
k= h.s
20

---

Near-optimal Regret Using Policy Optimization in Online MDPs with Aggregate Bandit Feedback
Using Lemma C.6, and the fact that under the good event (s) S (s, a).
K
(1-
()(s,a)
(1((s) 1807(,1),, (s,
(s,
Y =
(M(s) (
Th (s) +7
R,s,a
(a) (s) 7 (s, a) (5,))
Th a) +7
k= k,s,a
Σ ()()) (
7 Th (s, +7
h,s,a
(hi a) -4 (s.0)
Σ
E p s)U (s)
(5, a) +7
1=
(under the good event /1 (8, a) S (8)
The first term above is bounded by,
Σ
ph(s)ma(aa (s,
7
K pM(s)
3)
Hy
(1,)8 +7
( +7
1= h,
k=1 h,s,a
K
Σ
(s))
k=1h,8,
The second term is bounded by,
Σ (00))((ss))((s.... ph(s,a) a) - L (s,
Σ (M(s) 8)l1 ( a) _ (s,
(8) +7
1h a) +
h,aaa
Σ Σ (S
R=
C.3. Bound REG
Lemma C.8. For n S 24. under the good event of Lemma B.3,
Hln A
Σ (s))b)))s))) +0 H2, k.h.a
REG <
+ 16 K
n
Proof. Using standard entropy regularized OMD guarantee (Lemma E.5),
A
(s) s) (1%(),)) - ())))))
REG <
2n
k= h,s.a
In
K
2m
Σ
(s) (s, 2 + 161/1 K,
k=1 h,3,0
21

---

Near-optimal Regret Using Policy Optimization in Online MDPs with Aggregate Bandit Feedback
where in the second inequality use the fact that (s) 4H and thus, (s, a) S 4H2 For the middle term,
Σ (a(()) 8) 1 s, s. = a}
2n Σ (a()))(aa (s, S 2n k.h.s,a
(5,0) + 7)
k,h,a,a
(a(s) 5)
+ (
H
< 27
( +7
11
72
k,,,s,a
2
H
1
72
37
k.h.s
H
Σ (T)))
3
k,h.s
The second inequality above is under the good event G4, and the last inequality since r/ S H
27
C.4. Bound on BONUS
Lemma C.9. Under the good event,
BONUS S Σ (
k.b,s
Proof. Let 5h be the transition function chosen by the algorithm when calculating 8 It holds that
Ens((s (T Th s), (l.
h
Σ (1)
E (M(ss)((aa ( (s.
b,800
h,
Σ (3) I (s)
Σ (as s) (1(s)) + Σ ph(s') (s,a) ( Bh)
h,s.0
s'aal
S Σ (a) (s. Σ (a)
(1()) + Σ
Epuld' pulo' is, (s (dd
h,s,a
h,,,a
Σ b,8,0
Σ (8) b,e
(a B) (
h,
(4)
where the inequality is since p E pk under event Gi, and ø maximizes the term in the parentheses. (+) uses E.a (s) s)pu(s' a,a) = (h+)(s') and then change the variables s' and a' s and a. (i) is telescopic sum, and recall that B #+ O. Thus,
(1) = Σ ((())=((a) (s) = Σ aa((a (snse) (8ense: a)
(ni(s) = IIs = =sniet
3,0
ViT #* (simit)
Σnn h
Sh xt s" (s))((s)
< Σ (.)))
A
where the inequality is since p E Ppt and 7 (s) is the maximal occupancy with respect to transitions in Pk, Plugging (t) back the last display completes the proof.
22

---

Near-optimal Regret Using Policy Optimization in Online MDPs with Aggregate Bandit Feedback Lemma C.10. Under the good event,
BONUS SO A
Σ k.h,a
(1)
Proof. From lemma Lemma C.9,
BONUS E (s) + [1) - Σ (s)
k,h,,
k,h.,
k,h,
The first term is bounded by,
{a S 33112SAK
ΣΣ
(s)
3/H1
(1) +)
h,s
For the second term we use the good event G2,
Σ (s a) (1. a) (s,
(8, a) +
K,b,
$ H (s, a) - - (s,
h.hs
< H AKL + H A.2
where the last inequality is by Lemma E.7.
23

---

Near-optimal Regret Using Policy Optimization in Online MDPs with Aggregate Bandit Feedback
D. Lower Bound
Theorem D.1 (Restatement Theorem 6.2), Assume that H, H,S,AZ 2 and K 2S. Any learning algorithm for the online MDPs with known dynamics and aggregate bandit feedback problem must incur least DHH22VSAA expected regret in the worst case.
Proof. Consider an MDP with S states: $1, $2...., 8g where 31 is the initial state. The idea is encode hard multitask bandit problem with H 1 tasks in each of the states. The agent starts in the initial state where the loss is and any action transitions to each of the states .1...., with probability 1/S. Le., pi (s' a, 1/S for any s' and a. From time h 2 2 the agent stays at the same state, (s s,a) 1fs s}. Each state 8; encodes hard multitask bandit problem with H 1 tasks. That is, the losses are generated (independently for each state) from the (randomized) instance that attains the lower bound of Lemma 6.1.
Denote by Ti the number of times we transition to 8i. From Lemma 6.1 the expected regret from visits 8; is least 0(E[H /AT.). In total, we have lower bound on the regret of
SAT: ) - 12 = (IPSVAE[VX))
E 1
for ~ Bin(n = since each T, is a binomial random variable with parameters K and 1/S. By Lemma E.8, we have E 2 ((vp)) = (K(K) for 2 2S which proves the lower bound (HH2VAAK).
24

---

Near-optimal Regret Using Policy Optimization in Online MDPs with Aggregate Bandit Feedback
E. Auxiliary Lemmas
Lemma E.1 (Azuma-Hoefidiin inequality). Let {X1]221 be a real valued martingale difference sequence adapted to a filtration Fi S F2 ... (i.e. E[X; Fi] 0). If X,l I a.s. then with probability least 6,
R Thm 1
E
Lemma E.2 (A special form of Freedman's 's Inequality, Theorem 1 of Beygelzimer et al. (2011)), Let (Xi)e21 be real valued martingale difference sequence adapted to filtration Fi C F2 S (i.e., H[X, Fil 0). If |X,] I R a.s. then for any E (O,1/R), T E holds with probability at least 6,
T
T Σ
log (1/8)
Ex.sa
EX
Fil +
Lemma E.3 (Consequence of Freedman's Inequality, e.g., Lemma E.2 in (Cohen al., 2021a)). Let (X1)e21 be sequence of random variables, supported in [0, Rl, and adapted to a filtration Fi F ... For any T. with probability 1 - 5,
Σ X. S 28[X, Fd) + 4R 4olog 5" t=1
let = a) E [0, R| and i (s, a) E [0, be sequences of Fx Fy-measurable functions. If (s, a) E (0, R is a sequence of random variables such that BiZ F&] = (s, a) then with probability - 5,
Lemma E.4 (Lemma A.2 of Luo et al. (2021)). Given a filtration Fo
K
11 = s, a = (s, ()) +7
(T (8.
RH
S
27
h,s,a
k=1 h,,,a
Lemma E.S (Standard entropy regularized OMD guarantee, see e.g., (Hazan et al., 2016)). Let 1j > 0, and an arbitrary
sequence {gk 1K such that for all k E [K]. a E [d]. ge E Rd and (gg((a) 2 -. Let I E Aa be a sequence of vectors such that for all a, za) 1/n, for all le E [K], a E [d].
(=(a)e-
(a) En'e(n) Th (a' (a')e-nosse")
Then for any x² E Da.
K (gs, Th x) log d
au (1)))
k=1
k=
Lemma E.6 (Lemma Jin et al. (2020)). With probability
5. for all (ks, s s, a h).
(s s, a) log HSAK 8
log HSAK
(s 8, a)
(s' a,a) < <AV
max(m (s, a), + 10
max 1}
Lemma E.7 (Lemma 4 in Jin et al. (2020)). With probability 1 ò,
1 (s, o (HASSAAK ( log
KHSA
S3 A Alog² 2 KHSA
Σ
(s)
b,s.a.k
Lemma E.8. Let X ~ Bin(n,,) and assume that 2 2. Then, E[vX) 1 Top.
Proof. By Markov inequality we have:
/np
X Vnp
/np
up
/np (1-Pr Pr X 7
Pr
X
2
2
2
Thus, it suffices to show that Pr [X- assumption that 2/p.
< ap
< 1/2 which follows immediately from Multiplicative Chernoff bound and the
25


Reviews:
[{"review_id": "orpO5cEXuV", "reviewer": "Reviewer_3L6W", "summary": "The paper studies finite-horizon MDPs with adversarial losses under the aggregate bandit feedback model. In the known-dynamics case, the paper achieves the first optimal regret bound, while in the case of unknown dynamics it significantly improves the previous best known result.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the positive and constructive review. Below is our response to your comments and questions.\n\n> *I think that the bonus b(s) should not have π in the denominator (see, for example, the analysis in line 684)*\n\nNote that in line 684 the denominator has $\\mu_h^k (s,a)$ which is by definition $\\mu_h^k (s) \\pi_h^k (a \\mid s)$ (as in the bonus).\n\n> *Line 695: The variance term must contain E[Yk], since the martingale difference is Yk−E[Yk]. However, I believe that such minor errors across the analysis do not change the complexity results of the paper.*\n\nThank you for spotting that. This is indeed not a proper use of Lemma E.2 but has a simple fix: for the martingale difference, $|Y_k - \\mathbb{E}[Y_k]| \\leq \\max(Y_k, \\mathbb{E}[Y_k]) \\leq \\frac{H^2}{\\gamma}$, and the variance is bounded by the second moment: $\\mathbb{E}[(|Y_k - \\mathbb{E}[Y_k]|)^2] \\leq \\mathbb{E}[Y_k^2]$. We will correct this in the final version in line 695 and also in line 990 (which has the same minor error).\n\n> *(Line 326) Can the authors provide indicative works where the Bernstein sets are used?*\n\nYes, in the context of Policy Optimization see for example Shani et al. (2020); Luo et al. (2021). But it is also widely used in other types of algorithms such as in occupancy-measure-based algorithms (Jin et al., 2020) and FTPL (Dai et al., 2020). \nWe will reference those in line 326.\n\nDai, Yan, Haipeng Luo, and Liyu Chen. \"Follow-the-perturbed-leader for adversarial markov decision processes with bandit feedback.\"\n\n> *Can the authors provide the time complexity of the proposed algorithms?*\n\nFor the known dynamics case, the state occupancy measure can be computed using the following recursive formula: $\\mu_{h+1}^{\\pi}(s') = \\sum_{s,a} \\mu_{h}^{\\pi}(s) \\pi_{h}(a \\mid s) P(s' \\mid s,a)$, so that the full occupancy measure can be computed in $O(H S^2 A)$. The bonus $B$ is calculated via backward dynamic programming also in $O(H S^2 A)$, and the policy computation is done in $O(H S A)$. Thus, the total complexity per iteration is $O(H S^2 A)$.\n\nFor the unknown dynamics case, the upper/lower confidence occupancy measure computation can be done using Algorithm 3 in (Jin et al., 2020), with a complexity of $O(H S^2 A)$ per state. The same can be done for the computation of the bonus $\\hat{B}$.\n\nWe will include these details in the final version.\n\n> *In the unknown dynamics setting, how does Algorithm 2 compute μ? What is the time complexity per episode for these steps?*\n\nSee above.\n\n> *Have the authors tried a model-free approach?*\n\nTo the best of our knowledge, all existing regret minimization algorithms for MDPs with non-stochastic losses are model-based, even in the semi-bandit case. Achieving sub-linear regret under non-stochastic losses using a model-free algorithm is a very interesting future direction, already in the simpler context of semi-bandit feedback.", "claims_and_evidence": "Yes, the claims made in the paper are supported by clear and convincing evidence and proofs.", "methods_and_evaluation_criteria": "N/A. The paper is on the theory of reinforcement learning.", "theoretical_claims": "Yes. I checked many proofs of the paper, especially Appendix B. I have some minor points/questions to the authors:\n- I think that the bonus b(s) should not have $\\pi$ in the denominator (see, for example, the analysis in line 684).\n- Line 695: The variance term must contain $\\mathbb{E}[Y_k]$, since the martingale difference is $Y_k - \\mathbb{E}[Y_k]$. However, I believe that such minor errors across the analysis do not change the complexity results of the paper.", "experimental_designs_or_analyses": "N.A.", "relation_to_broader_scientific_literature": "I believe this paper is of great importance, as it solves an important problem of RL theory. More specifically, the paper deals with finite-horizon, tabular, adversarial MDPs under the relatively unexplored, but very interesting, full bandit setting.\n- The paper proposes the first optimal algorithm under known dynamics, matching the lower bound (proved by the authors) and the regret of [1] (semi-bandit).\n- The paper significantly improves the previous best regret upper bound of [2] under unknown dynamics. \n- From a technical standpoint, the authors introduce a novel RL objective, namely the U-function, which facilitates the proposed algorithms and the analysis for the full bandit setting. Based on the U-function, using well-established techniques, the paper achieves good and interesting results in this problem. \n\n[1] Zimin, A. and Neu, G. Online learning in episodic marko-\nvian decision processes by relative entropy policy search.\nIn Advances in Neural Information Processing Systems\n26: 27th Annual Conference on Neural Information Processing Systems 2013. Proceedings of a meeting held\nDecember 5-8, 2013, Lake Tahoe, Nevada, United States,\npp. 1583–1591, 2013.\n\n[2] Cohen, A., Kaplan, H., Koren, T., and Mansour, Y. Online\nmarkov decision processes with aggregate bandit feedback. In Conference on Learning Theory, pp. 1301–1329.\nPMLR, 2021b.", "essential_references_not_discussed": "The paper covers adequately the related work.", "other_strengths_and_weaknesses": "N/A.", "other_comments_or_suggestions": "- (Line 326) Can the authors provide indicative works where the Bernstein sets are used ?\n- Can the authors provide the time complexity of the proposed algorithms ?", "questions_for_authors": "- In the unknown dynamics setting, how does Algorithm 2 compute $\\mu$? What is the time complexity per episode for these steps?\n- Have the authors tried a model-free approach? (that is, without estimating the transition probabilities)", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "ziBuyyI4PF", "reviewer": "Reviewer_y9Yt", "summary": "This paper studies online episodic MDPs with adversarial costs and aggregate bandit feedback. Under aggregate bandit feedback, the agent only observes the entire episode loss, making it less informative than the full information setting (the agent observes the full cost function), and the bandit/semi-bandit feedback setting (the agent observes the loss over the agent's trajectory). The paper explores both known and unknown transition function scenarios and introduces a policy optimization algorithm for each case. Using a new tool called the U-function, the proposed algorithms improve upon existing regret bounds in the literature for both settings.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the positive and constructive review. Below is our response to your comments and questions.\n\n> *despite the paper’s theoretical focus, it would be interesting to include some experimental demonstrations of the U-functions in practice.*\n\nOur work is theoretically focused. Previous theoretical work has taken a more direct approach and faced challenges such as directly estimating the loss function and controlling the estimation bias in the regret bound. In our work, we introduce the concept of U-functions, which allows us to circumvent these challenges and handle aggregate bandit feedback much more elegantly. We hope this new concept will be insightful for future research, particularly for empirical studies and more practical applications. However, we believe that tabular MDPs would not be a good framework for demonstrating the practical applications of the U-function. Instead, an extensive empirical study that incorporates the U-function into a practical deep RL method, tested under a well-chosen set of benchmarks with large state spaces, would be more appropriate. We believe that this is an important area for future research and will include it in the future work section.\n\n> *…for the case with known dynamics… I wonder if a similar result could also be obtained without the exploration bonuses (as here the dynamics are known), using similar results as the Appendix B.3 from Jin et al 2020.*\n\nJin et al. 2020 employs an occupancy-measure-based algorithm where, indeed, one does not need to incorporate bonuses in the known dynamics case. On the other hand, in the Policy Optimization method, it is not clear how to achieve $\\sqrt{K}$ bounds without an exploration bonus. As mentioned in the paragraph starting at line 240, the purpose of the bonus in the known dynamics case is to address the distribution mismatch between $\\mu^\\star(s)$ and $\\mu^k(s)$ that appears in the regret bound (e.g., line 294, right column). This distribution mismatch is rather orthogonal from the additional challenges in the unknown dynamics case, and stems mainly from the fact that the value difference lemma breaks the regret over states with weights $\\mu^\\star(s)$, and that we run the OMD locally in each state (unlike the method in Jin et al. 2020, which is the framework that Cohen et al. (2021b) builds upon).", "claims_and_evidence": "All theoretical claims are followed by proofs in the appendix or in the main paper.", "methods_and_evaluation_criteria": "As a theoretical paper, the proposed algorithms are well-suited to the problem. Since a key advantage of policy optimization algorithms is their closed-form solutions, implementation should be relatively straightforward. Therefore, despite the paper’s theoretical focus, it would be interesting to include some experimental demonstrations of the U-functions in practice.", "theoretical_claims": "Proofs for theoretical claims seem correct.", "experimental_designs_or_analyses": "not applicable.", "relation_to_broader_scientific_literature": "The paper improves the current state-of-the-art bound for online MDPs with adversarial losses and aggregate bandit feedback when the dynamics are known and in this case they are the first to establish the near-optimal regret bound, and in the unknown dynamics setting they improve the terms related to the horizon, the state space size, and the action space size when compared to the previous approaches from the literature. \n\nThe main idea of the paper, the U-functions, seem new. The U-function at a given state-action pair computes the expect cost on the entire trajectory given that the agent visit this state-action pair. On the other hand, once the U-function is introduced, the rest of the paper (the Policy Optimization algorithm, the dilated bonus equation, and the regret analysis) follow from the work of Luo et al. (2021). The difference being that instead of considering an estimation of the Q-function, the paper considers an estimation of the U-function.", "essential_references_not_discussed": "All essential references seems to be discussed.", "other_strengths_and_weaknesses": "This is an interesting paper for the following reasons:\n        \n- The paper is well-written and organized.\n\n- The concept of the U-functions is new and is a simple and elegant way of attacking the bandit aggregate feedback problem. \n\n- While there are no additional technical novelties beyond the introduction of the U-function, demonstrating that the policy optimization algorithms from Luo et al. (2021), originally designed for bandit feedback, can be adapted, thanks to the U-functions, to the more challenging aggregate bandit feedback setting while maintaining comparable regret bounds is a significant contribution. It improves on previous results, and could open the way for new contributions on works of RL with trajectory feedback.", "other_comments_or_suggestions": "No other comments.", "questions_for_authors": "I checked the proof for the case with known dynamics and it sounds correct, but I wonder if a similar result could also be obtained without the exploration bonuses (as here the dynamics are known), using similar results as the Appendix B.3 from Jin et al 2020.\n\n*Jin et al., Learning adversarial markov decision processes with bandit feedback and unknwon transition, 2020.*", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "1R5dX4dDGp", "reviewer": "Reviewer_actv", "summary": "This paper studies regret minimization in tabular MDPs with adversarial losses, fixed transition kernel, and aggregate/trajectory/full- bandit feedback, meaning that at the end of each episode, the algorithm only receives the total loss among all the $H$ visited state-action pairs (i.e., the entire trajectory), rather than the loss of each pair (aka semi-bandit feedback).\n\nThis paper provides algorithms to achieve $O(H^2\\\\sqrt{SAK})$ known-transition upper bound, and $O(H^3S\\\\sqrt{AK})$ unknown-transition upper bound (ignoring log factors). This paper also shows a matching lower bound for the known-transitioin case, hence characterizing the minimax regret. The unknown-transition upper bound is the same as the best known one in the semi-bandit setting.\n\nTechinally, this is due to the Policy Optimization (PO) framework and a novel performance-difference-like regret decomposition w.r.t. the proposed \"U function\".", "questions": "", "limitations": "", "rating": 5, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the positive review and the great questions. We would be happy to discuss any of the points below in the final version that the reviewer believes will improve the paper.\n\n**Q1:** Indeed, our bounds are specific to the PO framework. The only 'occupancy measure + FTRL/OMD' algorithm for aggregate bandit feedback (ABF) is by Cohen et al. (2021b), where it is still unclear how to improve them using the occupancy measure approach. Given the regret structure in terms of occupancy measures, it is natural to attempt estimating the loss function itself; however, handling estimation bias under unknown dynamics is quite challenging since the learner does not precisely know the played occupancy measure.\nUnder known dynamics, it might be possible to achieve the optimal bound using 'occupancy measure + FTRL/OMD'. While the optimal bound for linear bandits over general convex sets is $d\\sqrt{T}$, in some special cases, such as the simplex, it is possible to achieve tighter bounds. Therefore, there may be room to improve the bounds for the set of occupancy measures.\nThis is an important and interesting open challenge for future research.\n\n**Q2:** Yes, the key novelty lies in the introduction of the U-function, which is easy to estimate under aggregate bandit feedback, and the regret decomposition with respect to it.\n\n**Q3:** No, in fact, one does not need the dilated component of Luo et al., 2021 (i.e., the $(1+\\frac{1}{H})$ factor in the backup operator), even in the semi-bandit case. For prior evidence, see [1].\n\n[1] Lancewicki, T., Rosenberg, A., & Sotnikov, D. \"Delay-adapted policy optimization and improved regret for adversarial MDP with delayed bandit feedback.\" ICML 2023\n\n**Q4:** That is a great question. The challenge in improving the lower bound under unknown dynamics is that ABF is not less informative about the dynamics, since the agent still observes the transitions. Thus, unlike in the semi-bandit case, under ABF it remains unclear whether unknown dynamics make the problem statistically harder.\n\n**Q5:** In the known dynamics case, full-bandit feedback is in fact statistically harder than semi-bandit feedback—the optimal bound in the semi-bandit case is $H \\sqrt{SAK}$, and our lower bound for the full-bandit case is $H^2 \\sqrt{SAK}$. As for the known dynamics case, it remains highly unclear, partly because the optimal bound in the semi-bandit case is also an open question. Under semi-bandit and unknown transitions, the best known upper bound is $H^2 S \\sqrt{AK}$ (Jin et al., 2020), while the best known lower bound is $\\Omega(H^{3/2} \\sqrt{SAK})$ (Jin et al., 2018). If the latter is optimal under semi-bandit, then due to our lower bound, ABF is statistically harder. We also conjecture that the $H^2$ dependency in our lower bound is optimal and that the extra $H$ in our upper bound is an artifact of the PO method (as PO currently has this artifact in the semi-bandit case). If this conjecture is true, and if $H^2 S \\sqrt{AK}$ is optimal under semi-bandit, then full-bandit would statistically be as easy as semi-bandit.", "claims_and_evidence": "yes", "methods_and_evaluation_criteria": "yes", "theoretical_claims": "I check the proof sketchs in the main body. Look correct to me.", "experimental_designs_or_analyses": "n/a", "relation_to_broader_scientific_literature": "relevant audience include researchers study online learning, reinforcement learning, policy optimization", "essential_references_not_discussed": "no", "other_strengths_and_weaknesses": "Strengths:\n\nThe new regret decompostion is novel. This is also naturally used in the algorithm design (e.g., now we need to build loss estimate for the U function which is simple). I am impressed by this idea.", "other_comments_or_suggestions": "n/a", "questions_for_authors": "The questions below are mainly for my curiosity and better understanding this paper:\n\n1. Seems that the boundes are specific to the PO framework (and the regret decomoposition). Does this mean that it's unclear whether occupancy measure + FTRL/OMD can achieve the same bound (as they do not come with such regret decomposition)?\n\n2. As long as we have this new regret decomposition, is the regret analysis pretty much the same as in Luo et al., 2021? If not, what are the key differences? (I don't view this as weakness, I just want to check my understanding).\n\n3. With trajectory feedback, we do not even need the complicated dialated bonus as in Luo et al., 2021. Is it still because now the loss estimate is w.r.t U function (which is already doing some sort of global exploration/optimization)?\n\n4. In the lower bound, why can not we utilize the unknown transition to prove a harder lower bound? What's the challenge?\n\n5. Do the authors believe semi-bandit is statiscally as easy as full-bandit, or the upper bound in semi-bandit can be improved?\n\nThanks in advance for sharing any thoughts.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "EBe5ikSZQU", "reviewer": "Reviewer_JehC", "summary": "This paper considers the problem of learning Adversarial (Tabular) MDPs with aggregated bandit feedback, which means only the total loss (instead of per-round losses) incurred in an episode is revealed. Using PO w.r.t. newly-proposed U-functions on each state,\n* with known transitions, an $\\tilde{\\mathcal O}(H^2 \\sqrt{SAK})$-regret algorithm is proposed, matching the lower bound up to logarithmic factors;\n* without transition information, an $\\tilde{\\mathcal O}(H^3 S \\sqrt{AK})$ upper bound is derived; and\n* a lower bound of $\\Omega(H^2 \\sqrt{SAK})$ is given via the reduction to multi-task bandit problems.", "questions": "", "limitations": "", "rating": 2, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your constructive review. Below is our response to your comments and questions.\n\n> *Aside from the innovation of U-function and corresponding performance difference lemma, are there other technical innovations that might be independent interest?*\n\nMajor contributions of our work:  \nThe key novelty lies in the introduction of the U-function, which is easy to estimate under aggregate bandit feedback, and the regret decomposition with respect to it. This contrasts with previous approaches that directly tried to estimate the loss function, inducing several challenges under aggregate bandit feedback such as controlling the estimation bias—this results in a relatively complex algorithm and technical analysis. We believe that the U-function is an interesting concept that elegantly circumvents previous technical challenges and results in an intuitive and simple technical analysis. We believe that this new concept could be insightful for future research on RL with aggregate bandit feedback.\n\n> *The removal of dilated bonuses may sound hand-waving... It'd be good to refer the readers to (Lancewicki et al., ICML'23)...*\n\nThank you for your suggestion - we will add a reference to Lancewicki et al. (2023) and discuss the technical differences from Luo et al. (2021).", "claims_and_evidence": "Claims are supported by rigorous proofs.", "methods_and_evaluation_criteria": "The notion of regret is aligned with previous works in the literature, and the comparison with them is fair.", "theoretical_claims": "I read the statements of all the lemmas and checked several main steps in the proof.", "experimental_designs_or_analyses": "N/A", "relation_to_broader_scientific_literature": "I am sorry to say this, but as far as I can see, the main contributions seem to be really restricted to the specific setup of aggregated bandit feedback (detailed below).", "essential_references_not_discussed": "The literature review is pretty complete, except for a tiny bit regarding the removal of dilated bonuses (see below).", "other_strengths_and_weaknesses": "The results are good to have given the recent interest on MDPs with aggreggated bandit feedback in the literature. The observation of the U-function and the corresponding version of performance difference lemma is cool, which avoids the reduction to linear bandits by Cohen et al. (2021b). However, besides these, it looks like the remaining components like implicit exploration, confidence sets on transitions and occupancy measures, and PO analysis for AMDPs, are more-or-less standard. Therefore I feel it's really a borderline result and can be much more interesting if the authors can utilize more properties of the U-functions (unfortunately, as the authors discuss in the Conclusion part, the structure of U-functions is fragile when the state/action space become infinite).", "other_comments_or_suggestions": "The removal of dilated bonuses may sound hand-waving by only saying \"$B_h^k (s,a)$ is computed using standard Bellman equations, which is simpler and more intuitive than the dilated version of Luo et al. (2021).\" It'd be good to refer the readers to (Lancewicki et al., ICML'23) and roughly explain it's because this specific $b_h^k(s,a)=\\mathcal O(1)$, which means the extra term $\\eta\\sum_k B_k^2$ in `Reg` can be directly controlled as $\\mathcal O(\\eta K)=\\mathcal O(\\sqrt K)$ instead of the original approach $\\eta \\sum_k B_k^2 = \\mathcal O(\\sum_k B_k)$.\n\n* Tal Lancewicki, Aviv Rosenberg, Dmitry Sotnikov. Delay-Adapted Policy Optimization and Improved Regret for Adversarial MDP with Delayed Bandit Feedback. ICML 2023.", "questions_for_authors": "Aside from the innovation of U-function and corresponding performance difference lemma, are there other technical innovations that might be independent interest? As I mentioned, I feel the U-functions are nice and elegant, but are really restricted to the specific setup of aggregated bandit feedback (and do not generalize to function approximations since I am not sure whether it makes sense to assume the U-functions are linear in some $\\phi(s,a)$'s, which is an analog of the linear-Q assumption in the literature).\n\nIf there're any technical contribution that I missed, I'd be happy to re-evaluate this paper.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper studies online episodic MDPs with adversarial costs and aggregate bandit feedback. The paper studies both known and unknown transition function scenarios and introduces a policy optimization algorithm for each case. Using a new tool called the U-function, in the known-dynamics case, the paper achieves the first optimal regret bound, while in the case of unknown dynamics it significantly improves the previous best known result.

Reviewers think the results are strong and there are novelties in the techniques. The AC agrees and thus recommends acceptance.
Decision: Accept (poster)