On the Complexity of Adversarial Decision Making
Authors: Dylan J Foster
Alexander Rakhlin
Ayush Sekhari
Karthik Sridharan
Venue: NeurIPS 2022 Accept (2022)
Keywords: Decision making
learning theory
bandits
reinforcement learning theory
online learning
adversarial
non-stochastic
decision-estimation coefficient
information ratio

Abstract: A central problem in online learning and decision making---from bandits to reinforcement learning---is to understand what modeling assumptions lead to sample-efficient learning guarantees. We consider a general adversarial decision making framework that encompasses (structured) bandit problems with adversarial rewards and reinforcement learning problems with adversarial dynamics. Our main result is to show---via new upper and lower bounds---that the Decision-Estimation Coefficient, a complexity measure introduced by Foster et al. in the stochastic counterpart to our setting, is necessary and sufficient to obtain low regret for adversarial decision making. However, compared to the stochastic setting, one must apply the Decision-Estimation Coefficient to the convex hull of the class of models (or, hypotheses) under consideration. This establishes that the price of accommodating adversarial rewards or dynamics is governed by the behavior of the model class under convexification, and recovers a number of existing results --both positive and negative. En route to obtaining these guarantees, we provide new structural results that connect the Decision-Estimation Coefficient to variants of other well-known complexity measures, including the Information Ratio of Russo and Van Roy and the Exploration-by-Optimization objective of Lattimore and György.

On the Complexity of Adversarial Decision Making
Dylan J. Foster sylanffosterrmicrroofff.. com
Alexander Rakhlin
Ayush Sekhari sekhari@mit.edd
Karthik Sridharan ks9990cornell.
rakhlin@mit.edu
Abstract
A central problem in online learning and decision making-frive bandits to rein- forcement learning-is is to understand what modeling assumptions lead to sample- efficient learning guarantees. We consider general adversarial decision making framework that encompasses (structured) bandit problems with adversarial rewards and reinforcement learning problems with adversarial dynamics. Our main sult is to show-vis new upper and lower bounds-that the Decision-Estimatto Coefficient, complexity measure introduced by Foster al. [17] in the stochas- tic counterpart to our setting, is necessary and sufficient to obtain low regret for adversarial decision making. However, compared to the stochastic setting, one must apply the Decision-Estimation Coefficient to the convex hull of the class of models (or, hypotheses) under consideration. This establishes that the price of accommodating adversarial rewards or dynamics is governed by the behavior of the model class under convexification, and recovers number of existing results both positive and negative. En route to obtaining these guarantees, we provide new structural results that connect the other well-known complexity measures, including the Information Ratio of Russo and Van Roy [47] and the Aettoration-b--Opmmiiatttii objective of Lattimore and György [32].
Estimation Coefficient to variants of
Introduction
To reliably deploy data-driven decision making methods in real-world systems where safety is critical, such methods should satisfy two desiderata: (i) provable robustness in the face of dynamic even adversarial environments, and (ii) ability to effectively take advantage of problem structure modeled by the practitioner. In high-dimensional problems, this entails efficiently generalizing across states and actions while delicately exploring new decisions.
For decision making in static, stochastic environments, recent years have extensive investigation into optimal sample complexity and algorithm design principles, and the foundations are beginning to take shape. With emphasis
reinforcement learning, burgeoning body of research identifies specific modeling assumptions under which sample-efficient interactive decision making is possible [12, 54, 20, 39, 5, 27, 14, 36, 13, 56), well as general structural conditions that aim unify these assumptions [45, 19, 51, 53, 15, 21, 17]. For dynamic or adversarial settings, however, comparatively little known outside of (i) positive results for special cases such adversarial bandit problems [4, 3, 18, 10, 1, 7, 26, 16, 8, 29], and (ii) handful of negative results suggesting that online adversarial settings can actually be statistically intractable [48, 37]. These developments raise the following questions: (a) what are the underlying phenomena that govern the statistical complexity of decision making adversarial settings? (b) what are the corresponding algorithmic design principles that attain optimal statistical complexity?
reinforcement learning in agnostic
Contributions. We consider an adversarial variant of the Decision Making with Structured Observations (DMSO) framework introduced in Foster et al. [17], where a learner or decision-maker interacts with sequence of models (reward distributions in the case of bandits, MDPs in the case of reinforcement learning) chosen by an adaptive adversary, and aims to minimize regret against the
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

best decision in hindsight. Models are assumed to belong to known model class, which reflects the leamner' prior knowledge about the problem. The main question we investigate How does the structure of the model class determine the minimax regret for adversarial decision making? We show:
1. For any model class, one can obtain high-probability regret bounds that scale with convexified version of the Decision-Estimation Coefficient (DEC), complexity measure introduced by Foster al. [17].
2. For any algorithm with "reasonable" tail behavior, the optimal regret for adversarial decision making is lower bounded by (a suitably localized version of) the convexified DEC.
In the process of obtaining these results, we draw new connections to several existing complexity measures.
1.1 Problem Setting
We adopt adversarial variant of the DMSO framework of Foster et al. [17] consisting of T rounds, where at each round = 1,....
1. The learner selects decision T( E II, where II is the decision space.
2. Nature selects a model M E M, where M is a model class.
3. The learner receives a reward r( E RR S R and observation o sampled via (r(0) ol0)) ) ("),, where O is the observation space. We abbreviate 20t) == (r(9, o())
and Z = R O.
Here, each model M ((, |.) E .M is conditional distribution M II -> A(R O) that maps the learner's decision to a distribution over rewards and observations. This setting subsumes (adversarial) bandit problems, where models correspond to reward functions (or distributions), as well as adversarial reinforcement learning, where models correspond to Markov decision processes (MDPs). In both cases, the model class M encodes prior knowledge about the decision making problem, such as structure rewards or dynamics (e.g., linearity or convexity). The model class might be parameterized by linear models, neural networks, other rich function approximators depending on the problem domain.
For model M E M, [-] denotes expectation under the process (r.o) (x). We define (Mx(x) == MM [r] as the mean reward function and Ter == arg max fMT()) as the decision with greatest reward for M. We let FM = (fM M M) denote the induced class of reward functions. We measure performance via regret to the best fixed decision in hindsight:'
Regom sup Σ E 10 (p(t)))))
[nul]] (T** f (7 (TT)) )
This formulation-in which models are selected by potentially adaptive dalversary-generaiizee Foster al. [17], who considered a stochastic setting where (o _M* is fixed across all rounds.
Examples include:
Adversarial bandits. With observations (0 {Ø))), the adversarial DMSO framework is equivalent to the adversarial bandit problem with structured rewards. In this context, (T is typically referred as an action or arm and 11 is referred to as the action space. The most basic example here is the adversarial finite-armen bandit problem with A actions [4, 3, 18), where II {1. (1...... A} and FM A Other well-studied examples include adversarial linear bandits [10, 1, 7]. bandit convex optimization [26, 16, 8, 29], and nonparametric bandits [26, 6, 38].
Reinforcement learning. The adversarial DMSO framework encompasses fnite-horizon, episodic online reinforcement learning, with each round t corresponding to single episode:
'The results in this paper immediately extend to the regret sup e en Er (+*")) (*) through standard tail bounds.
TTypccllyy these examples are formulated with deterministic rewards, which we encompass by restricting models in A to be deterministic. Our formulation is more general and allows for, e.g., semi-stochasti adversaries.

---

T! is a policy (a mapping from state to actions) to play in the episode, r( is the cumulative reward in the episode, and the observation of is the episode's trajectory (sequence of observed states, actions, and rewards). Online reinforcement learning in the stochastic setting where Mo .** fixed has received extensive attention [19, 51, 20, 53, 15, 21, 17], but the adversarial setting we study has received less investigation. Examples include the adversarial MDP problem where an adversary chooses sequence of tabular MDPs, which is known to be intractable [37], and the easier problem in which there is fixed (known) MDP but rewards are adversarial [40, 57, 41, 22]. See Appendix D for more details.
We refer to Appendix B for additional measure-theoree theoretic details and background, and to Foster et al. [17] for further examples and detailed discussion."
Understanding statistical complexity (i.e., minimax regret) for the DMSO setting at this level of generality is challenging problem. Even if restricts only bandit-type problems with observations, any complexity measure must capture the role of structural assumptions such as convexity smoothness in determining the optimal rates. To go beyond bandit problems and handle the general setting, one must accommodate problems with rich, structured feedback such as reinforcement learning. where observations (as well as subtle features of the noise distribution) can reveal information about the underlying model.
1.2 Overview of Results
For model class M, reference model M E M, and scale parameter > 0, the Decision-Estimatinn Coefficient [17] is defined via
dec, (M, = inf sup Expp (T fa (x) - (MMM)
(2)
PE MEM
where we recall that for probability measures P and Q with common dominating measure (squared) Hellinger distance given by
Di - 1=
/
dP
dQ
du
du
We define dec,, (M) sup M (M, M), and let co(M) denote the convex hull of M, which can be viewed as the set of all mixtures of models M. Our main results show that the convexified Esstiint-ttittttoon Coefficient,
(co(M)))))
leads to upper and lower bounds the optimal regret for adversarial decision making. Theorem (informal). For any model class M, Algorithm I ensures that with high probability.
RegoM Z (cc,(cc(M)))-
where n satisfies the balance (eo,(co(( (M)( x 7 log Moreover, for any algoritlu with "rea- sonable" tail behavior (Section 2.2), regret must scale with a localized version of the same quantity.
As a consequence, there exists an algorithm for which Regooll S o(T)) if and only if (co(M))) ~P some p > 0.
For the stochastic version of our setting, Foster al. [17] give upper and lower bounds that scale with dec, (M), without convexifying (under appropriate technical assumptions; cf. Section 2.3). Hence, our results show that in general, the gap in optimal regret for stochastic and adversarial decision making (or, "price of adversarial outcomes") is governed by the behavior of the DEC under convexification. For example, multi-armed bandits, linear bandits, and convex bandits correspond to convex model classes (where co(M) M), which gives post-hoc explanation for why these problems are tractable in the adversarial setting. Finite state/action Markov decision processes do not correspond to convex model class, and have dec,(co (Co(M)) exponentially large compared to (M)); in this case, our results recover lower bounds of Liu al. [37].
Beyond these results, we prove that the convexified Decision-Essinn Estimation Coefficient is equivalent to:
'We mention in passing that the upper bounds in this paper encompass the more general setting where rewards are not observed by the learner (i.e., 200) does not contain the reward). thus subsuming the partial monitoring problem. Our lower bounds, however, require that rewards observed. See Appendix A.

---

1. a "parameterized" variant of the generalized Information Ratio of Lattimore and György [32].
2. a novel high-pun probability variant of the Exploration-by--priiiiici objective of Lattimore and Szepesvári [35], Lattimore and György [32].
Our techniques. On the lower bound side, we strengthen the approach from Foster et al. [17] with an improved change-of-meant and combine this with the simple idea of constructing adversaries based on static mixture models. On the upper bound side, we extend the powerful Exploration-be by -yOppimmizztiionn machinery of Lattimore and György [32] to the DMSO setting, and give a novel high-probability variant of the technique which leads regret bounds for adaptive adversaries. We show that the performance of this method is controlled by complexity measure whose value is equivalent to the convexified DEC, as well as parameterized variant of the Information Ratio (we present results in terms of the former to draw comparison to the stochastic setting).
argument (leading to improved results even in the stochastic setting),
Overall, results heavily draw on the work of Foster al. [17] and Lattimore and György [32], but we believe they play a valuable role in bridging these lines of research and formalizing connections.
Organization. Section 2 presents our main results, including upper and lower bounds regret and a characterization of learnability. In Section 3, we provide new structural results connecting the DEC to future directions (Section 4). Additional comparison to related work deferred to Appendix A. The appendix also contains proofs and additional results, including examples (Appendix D) and further structural results (Appendix E).
and the Information Ratio. We close with discussion of
2
Main Results
We now present our main results. First, using a new high-probability variant of the Exploration-by- Optimization technique [35, 32], we provide an upper bound on regret based on the (convexified) - Coefficient (Section 2.1). Next, we present a lower bound that scales with local- ized version of the same quantity (Section 2.2). Finally, we use these results to give a characterization for learnability (Section 2.3), and discuss the gap between stochastic and ad adversarial decision making,
To keep presentation as simple as possible, make the following assumption. Assumption 2.1. The decision space has III < po, and we have R = =00, 1].
This assumption only serves to facilitate the use of the minimax theorem, and we expect that our results can be generalized (e.g., with covering numbers in Section 3.4 of Foster al. [17]).
2.1 Upper Bound
In this section we give regret bounds for adversarial decision making based on the (convexified) -esision-Esttmattion Coefficient. A-priori, it is not obvious why the DEC should bear any relevance to the adversarial setting we consider: The algorithms and regret bounds based on the DEC that Foster et al. [17] introduce for the stochastic setting heavily rely on the ability to estimate a static underlying model, yet in the adversarial setting, the learner may only interact with each model a single time. This renders any sort of global estimation (e.g.. for dynamics of an MDP) impossible. In spite of this difficulty, we show that regret bounds can be achieved by building on the Exploration- -b-nnn------p Optimization technique of Lattimore and Szepesvári [35], Lattimore and György [32], which provides an elegant approach to estimating rewards that exploits the structure of the model class under consideration.
by Lattimore and Szepesvári [35] and substantially ex- panded in Lattimore and György [32]-can can be thought of as a generalization of the classical EXP3 algorithm [4] for finite-action bandits, which applies the exponential weights method for full-information online learning to a sequence of unbiased importance-weigeee wards. While EXP3 is near- optimal for bandits, it is unsuitable for general model classes because the reward estimators the algorithm uses do not exploit the structure of the decision space. Consequently, the regret scales linearly with [II] rather than with, e.g., dimension, as one might hope for problems like linear bandits. The idea behind Exploration-by- -b-oonnnt--Ottttttionnn is to solve an optimization problem at each round to search for (potentially biased) reward estimator and modified sampling distribution that better exploit the structure of the model class M, leading to information sharing and improved re- gret. Lattimore and György [32] showed that for general partial monitoring setting (cf. Appendix A),
estimators for re-

---

Algorithm 1 High-Probabilltty Exploration-by-Opiiiizziiee (ExO*)
parameters: Learning rate >
2: for = 1, do
3: Define q( (III) via exponential weights update:
exp Er
(T)
(5)
Ewen exp E (T))
4: Solve high-probability exploration-by optimizaatioon objective:
// See Eq. (8)
(pto) 9
arg min
sup T (0
(6)
(EA(TT),EG MEM,
5: Sample decision n pl and observe z(0) = (r((), ((")).
6: Form reward estimator:
(T) gdd 201) (T(())
the expected regret for this method and for more general family of algorithms based on Bregman divergences-is bounded by generalization of the Information Ratio of Russo and Van Roy [46, 47].
Our development builds that of Lattimore and György [32], but we pursue high-probability guarantees rather than in-expectation guarantees. This allows us to provide regret bounds that hold for adaptive adversaries, rather than oblivious adversaries considered in prior work. Beyond this basic motivation, our interest in sigh-probbbility guarantees comes from the lower bound in the sequel (Section 2.2), which shows that the convexified Decision-Estimatie bounds regret for algorithms with "reasonable" tail behavior. To develop high-proud ceth-bbbbbbbittty regret bounds and complement this lower bound, objective and a specialized analysis that goes beyond the Bregman divergence framework.
Coefficient lower
novel variant of the Exploration-by -eann-----pppaa by-OOtimization
Our algorithm, ExO+, is displayed in Algorithm 1. reference distribution q²)) A(TI) by applying the standard exponential weights update (with
At each round I, the algorithm computes
from previous rounds (Line 3). For the main step (Line 4), the algorithm obtains a sampling distribution n A(II) and an estimation function gd E C == (II x II x Z + R) by solving a minimax optimization problem Defining
learning rate > 0) to sequence of reward estimators fe.,...,,
based on new objective we term high-prooaybilityy
T q.n (P. 9; M) E ETpppl
"f [f*((m") (m))
(8)
(o(T'),, (00l::,,,))=(===(_0000 -1]
-
(aappeeMM(n) Exing exp ((T))
"
solve
(p 10 arg min sup PEA(M)) MEM Ig (P.gi',
Finally (Lines 5 and 6), the algorithm samples T0 p observes 200 (p(()),(t)),, and then
forms an importance-weighiee reward estimator via f (T) == (T; ",,, //p/p'' ( (1))..
The interpretation of the high-probability For given round I, the model M E . and decision x² E II should be thought of as proxy for the true model MD and optimal decision, respectively. By solving the minimax problem in (9), the min-ple min-player aims to-in the face of an unknown, worst-case model-fine find a sampling distribution that minimizes instantancous regret, yet ensures good tail behavior for the importance--eightee estimator g(:; ,, pT)) Tail behavior captured by the moment generating function-like term in (8), which penalizes the learner for over-estimating rewards under the reference distribution or esttimanin rewards under "
by--byy-izztttionn objective (8) is as follows:
'In general, in expeeettiion regret bounds do not imply peeehprrbbbilitty bounds. For example, in adversarial bandits, the EXP3 algorithm experience linear regret with constant probability [34].
5

---

We show that this approach leads to a bound on regret that scales with the convexified DEC. Theorem 2.1 (Main upper bound). For any choice of > O, Algorithm I ensures that for all with probability at least - 6,
0.
2 ") RegOM (ecn)ss/(o((M)) T+ log (T/)).
(10)
In particular, for any 5 > O, with appropriate v, the algorithm ensures that with probability at least
1 8,
RegDM I 0(1) inf (dec,(coM)) T log((11//0)}
(11)
y20
This regret bound holds for arbitrary, potentially adaptive adversaries. The result should be compared to the upper bound for the stochastic setting in Foster et al. [17] (e.g., Theorem 3.3), which takes a similar form, but scales with the weaker quantity sup Meeo dec,, (M, M.) See Appendix A for comparison to Lattimore and Szepesvári [35], Lattimore and György [32].
Equivalence of cnterrationn--OOimiiittte and Ppeision-Estimmaionn Coefficient. We now discuss a deeper connection between Exploration-bb--ptiiinaaa and the DEC. Define the minimax value of the high-probability esplorationby--Oiimizzze objective via
exo,(M, =
sup T (a M), PEA(TT) MEM
inf
(12)
and let (.V) ((I) (xo, This quantity can be interpreted complexity measure for M whose, value reflects the difficulty of exploration. The following structural result (Corollary 3. in Section 3), which critical to the proof of Theorem 2.1, shows that this complexity measure is equivalent to the convexified -estiain-stinatiion Coefficient:
de S (M) S (ec(sn)- Vn > 0.
(13)
As we show, the regret of Algorithm is controlled by the value of exo,(MM, and thus Theo- rem 2.1 follows. the process of proving (13), we also establish equivalence of the Exploration-by: Optimization objective and a parameterized version of the Information Ratio, which is of independent interest (cf. Section 3). Both results build on, but go beyond the Bregman divergence-basse frame- work in Lattimore and György [32], and exploit somewhat obscure connection between Hellinger distance and the moment generating function (MGF) for the logarithmic loss. particular, we use technical lemma (proven in Appendix C), which shows that up to constants, the Hellinger distance between two probability distributions can be expressed as variational problem based on the associated MGFs.
Lemma 2.1. Let P and Q be probability distributions over a measurable space (X,F). Then
1 PP
< sup (1 Epp[e]] Ba[e 31 S (2(P,)).
(14)
2
9:X-AR
The lower inequality in Lemma 2.1 is proven using trick similar to one used by Zhang [55] to prove high-pron nigh-probabiiltyy bounds for maximum likelihood estimation based on Hellinger distance. To prove the upper bound in (13), we apply the lower inequality in (14) with the test function taking the role objective.
of the estimation function in the Exploration-by-Opiime
Further remarks. The main focus of this work is statistical complexity (in particular, minimax regret), and the runtime and memory requirements of Algorithm which are linear in [11,, are not practical for large decision spaces. Improving the computational efficiency is an interesting question for future work. We mention in passing that Theorem 2.1 answers a question raised by Foster et al. [17] of obtaining in the frequentist setting a regret bound matching the Bayesian regret bound in their Theorem 3.6.
'If' a proper estimation algorithm (i.e., an algorithm producing estimators that lie in M) is available, Foster al. [17] (Theorem 4.1) gives tighter bounds scaling with (MM.

---

2.2
Lower Bound
We now complement the regret bound in the prequel with lower bound based on the convexified DEC. Our most general result shows that for any algorithm, either the expected regret or its (one-sided) second moment must scale with a localized version of the convexified DEC.
To state the result, we define the localized model class around model M via
Mc(M) = {M E M: 1M (TTar) 2 f - e),
and define (M) Eslimation Coesficient.
SUPMEM dec, (Mc M) the localized Decision- We let (x)) == max (x. 0} and define V(M)
SUPM,MEEN su o { MiAAK]
M[A e; finiteness of ((M) is not necessary, but
removes a log(T) factor from Theorem 2.2.
Theorem 2.2 (Main lower bound). Let C(T) == (-)) for sufficiently large numerical
constant c 0. Set Ey मc(тग.. For any algorithm, there exists oblivious adversary for which
E RegoM + B(RegoM) 2 2(1)
sup /2C(TTT
-T O(T))) (15)
Theorem 2.2 implies that for any algorithm (such as Algorithm 1) with tail behavior beyond what granted by control of the first moment, the regret in Theorem 2.1 cannot be substantially improved. In more detail, consider the notion of a sub- wub-Chebychev algorithm.
Definition 2.1 (Sub-Chebychev Algorithm). A regret minimization algorithm is said to be sub-
Chebychev with parameter R if for all ( 0,
I((RegDM)+ 2) S 12/e..
(16)
For sub-Chebychev algorithms, both the mean and (root) second moment of regret are bounded by the parameter R (cf. Appendix F.4), which has the following consequence. Corollary 2.1. Any regret minimization algorithm with sub-Chebychev parameter R >> 0 must have
R 2 2(1)
sup
dec (co(M)) T O
(17)
2CTTT
To interpret this result, suppose for simplicity that dec, and de,,,e, (c)(M) are continuous with respect y 0, and that dec,.e, (co(M)) 2 y-1, which is satisfied for non-trivial classes.? In this case, it follows from Theorem 2.1 (cf. Proposition F.2 for details) that by setting 6 1/T Algorithm is sub-Chebychev with parameter
R = Ō inf (dec . + log(( = Ödeec, (co(M) y>00
(18)
where "h satisfies the balance dec,, (co(M)) x Zs log/[T]. On the other hand, the lower bound in (17) can be shown to scale with
R > á (edderrres, (co .T).
(19)
where "e satisfies the balance de (co(M)) H. We conclude that the upper bound from Theorem 2.1 cannot be improved beyond (i) localization and (ii) dependence log
As an example, we show in Appendix D.3 that for the multi-armed bandit problem with =l= (I...., .......,,.. A). the upper bound in (18) yields R = Ō(VAT A), while the lower bound in (19) yields R = A(VAT). See Appendix D for additional examples which further illustrate the scaling in the upper and lower bounds.
RReaal (Appendix B) that M(. =) is conditional distribution given π. 'The dominant term dec...,(co (co(M)) T in (15) seales with T1/2 for any class that is non-trivial in the that it embeds the two-armed bandit problem, that the -0(11/2) term can be discarded.
7

---

The dependence on log II cannot be removed from the upper bound or made to appear in the lower bound general (cf. Section 3.5 of Foster et al. [17]). As shown Foster et al. [17], localization is inconsequential for most model classes commonly studied in the literature. The same is true for the examples we consider here (Appendix D), where Theorem 2.2 leads to the correct rate up to small polynomial factors. However, improving the upper bound to achieve localization, which Foster et al. [17] show is possible in the stochastic setting, is an interesting future direction.
See Appendix A for further discussion and for comparison to a related lower bound in Lattimore [31].
Why convexity? At this point, a natural question is why the convex hull co(M) plays fundamental role in the adversarial setting. For the lower bound, the intuition is simple: Given a model class M, the adversary can pick any mixture distribution μ (MM), then choose the sequence of models M by sampling M ~ j independently at each round. This is equivalent to playing a Eas-all [M] co(M), which is what allows us prove lower bound
static mixture model M based on the DEC for the set c)(M) of all such models. In view of the fact that the lower bound is obtained through this static (and stochastic) adversary, we believe the more surprising result here is that good behavior of the convexified DEC is also sufficient for low regret for fully adversarial decision making.
2.3 Learnability and Comparison to Stochastic Setting
Building on the upper and lower bounds in the prequel, we give a characterization for learnaiiiity (i.e., when non-trivial regret is possible) for adversarial decision making. This extends the learnability characterization for the stochastic setting in Foster et al. [17]. and follows a long tradition in learning theory [52, 2, 49, 44, 11]. To state the result, define the minimax regret for model class M
inf D), = p(i;....ppp
sup
Reegnll
M M
where p (II xI (II) and M (II z) M are policies for the learner and adversary, respectively. Our characterization is as follows.
Theorem 2.3. Suppose there exists Mo E M such that f is a constant finctinn, and that [II] < co.
1. If there exists > 0 such that lim,- (cc,(c))))) 70 0. then limr- for p <1.
2RM,T) 0
TF
2. If loo dec, (co(MM) of > 0 for all p > O, then limy +00
2R(MT) for all 1.
T5
The same conclusion holds when II Ily grows with T, but has log Ir ((T)) for any q 1.
Theorem 2.3 shows that polynomial decay of the convexified DEC is necessary and sufficient for low regret. We emphasize that this result is complementary to Theorem 2.2, and does not require localization or any assumption on the tail behavior of the algorithm. This is a consequence of the coarse, asymptotic nature of the result, which allows us the use of rescaling arguments to remove these conditions.
Comparison to stochastic setting. Having shown that the convexified cient leads to upper and lower bounds on the optimal regret for the adversarial DMSO setting, we now contrast with the stochastic setting. There, Foster et al. [17] obtain upper bounds on regret that have the same form as (11), but scale with the weaker quantity max MEcc((M) dec, M). For classes that are not convex, but where "proper" estimators are available (including finite-state/action MDPs), the upper bounds Foster al. [17] can further be improved to scale with (Mc, Hence, our results show that in general, the price of adversarial outcomes can be as large as dec, (co(M))/dec, Examples (see Appendix D for details and more) include:
Coeffi-
* For tabular stnite-staateacction) MDPs with horizon H, S states, and A actions, Fos- ter et al. [17] show that dec,() S poly S, A)/7, and use this to obtain regret
* "Allowing IT to grow with T is useful when considering infinite decision spaces, because it facilitates covering arguments. "Thoorem 3.1 Foster et al. [17] attains RegoM S inf max MecoMM) dMc, M) + loglM) with high probability.
8

---

S, Tabular MDPs are not a convex class, and co(M) is equivalent the class of so-called latent MDPs, which are known be intractable [28, 37J. Indeed, we show (Appendix D) that dec, (co(M)) 2 O (m)in( which implies an exponential lower bound on regret through Theorem 2.2. This highlights that in general, the gap between stochastic and adversarial outcomes can be quite large.
For many common bandit problems, one has co(M) = M, leading polynomial bounds on regret in the adversarial setting. For example, the multi-armed bandit problem with A actions has dec,, (co(M)) I ((A/7)) leading to VA7' A regret (via Theorem 2. and the linear bandit problem in d dimensions has (co(Mc)(M I O(d/r), leading to regret
v [dTlog|[1]
3 Connections Between Complexity Measures
The Crtision-Estimatiinn Coefficient bears resemblance to the generalized Information Ratio introduced by Lattimore and György [32]. Lattimore [30] which extends the original Information Ratio of Russo and Van Roy [46, 47]. In what follows, we establish deeper connections between these complexity measures. All of the results in this section are proven in Appendix E.
Let us call any function D || -)= A(T) x (IT) - RR+ divergence-lik function. We restate the generalized Information Ratio from Lattimore [31]. For distribution 1t E A(M x II) and decision distribution p E (II), let IP be the law of the process (M, TT*) M, ~ p, 2 M (T), and define (T") := P( = r') and (T' z) := PP = nT (I,, 2)). The distribution μle should be thought of as the prior over '², and Mpo should be thought of as the posterior over n² after observing (z, T); note that the law μpo does not depend on the distribution p. For parameter À > 1, Lattimore
[31] defines the generalized Information Ratio for a class M vi
(B( ExNpl (T*) - (T)))*
(M = sup inf (MI(MXII PEA(T))
(20)
Enep E.ja D (ppo Mpr)]
Here, we have slightly generalized the original definition in Lattimore [31] by incorporating models in M rather than placing an arbitrary prior over observations directly. We also use a general divergence-like function, while Lattimore [31] uses KL divergence and Lattimore and György [32] use Bregman divergences.
To understand the connection to the another variant of the Information Ratio, which we call the parameterized Information Ratio.
Coefficient, will be helpful to introduce
Definition 3.1. For divergence-like function D(- [I (TT) (TII) R., the parameterized Information Ratio is given by
inf2(MM)
(21)
sup inf Eawp \all" fT)( - Expp Exln DD (3 2) || Ppr)]] PEA(MII) (EA(IT)
The parameterized Information Ratio is always bounded by the generalized Information Ratio in (20);
in particular, we have inf (M) S (Px(M)/)) / Vy > O. All regret bounds based on the gen- eralized Information Ratio that we are aware of [32, 31] implicitly bound regret by the parameterized Information Ratio, and then invoke the inequality above to move the generalized Information Ratio. In general though, it does not appear that these notions are equivalent. Informally, this is because the notion (20) is equivalent to requiring that a single distribution p certify certain bound on the value in (21) for all values of the parameter y simultaneously, while the parameterized Information Ratio allows the distribution p to vary as function of > 0 (hence the name); see also Appendix
Letting in (M) denote the parameterized Information Ratio with D = ()), we show that this notion is equivalent to the convexified
-astiiattin Coefficient.
Theorem 3.1. For all 7 > O, inf (M) < (cc,(c)(MM) < inf# inf*// (M).
10 Lattimore and György [32] give slightly different but essentially equivalent definition; ef. Appendix E.

---

This result is special case of Theorem E. in Appendix E, which shows that similar equivalence holds for class of general Bregman divergences. The idea is to use Bayes' law to move from the Decision-Fstimatti Coefficient, which considers distance between distributions over observations, to the Information Ratio, which considers distance between distributions over decisions.
f-divergences that includes KL divergence, but not necessarily for
In light of this characterization, the results in this paper could have equivalently been presented in terms of the parameterized Information Ratio. We chose to present them in terms of the Decision- Estimation Coefficient order to draw parallels to the stochastic setting. where guarantees that scale with dec, (MM) (without convexification) are available. It is unclear whether the Information Ratio can accurately reflect the complexity for both stochastic and adversarial settings in the same fashion, because- unlike the DEC- it is invariant under convexification, as the following proposition shows."! !!
Proposition 3.1. For any divergence-like DI: +), we have
inf (M) = (co(M)), by > O.
For final structural result, show that up to constants, the parameterized Information Ratio is equivalent to the high-probabillty Exploration-by Oppiiiiiaoo objective.
Theorem 3.2. For all > O, i S exo,(M) < inf (8n) (M)
This result is proven through a direct argument (ef. Section 2.1), and the equivalence of the DEC and cerpattionnb-OOiimizeeee the equivalence:
in (13) is proven by combining with Theorem 3.1. Summarizing
Corollary 3.1. For all 17 > 0,
(co(M)) s inft) (M) S (x),(M) S inf (8n) (M) (co()))
Since this equivalence depends of the value of the parameter > 0 in the parameterized Information Ratio, it is not clear whether similar equivalence can be established using the generalized Informa- tion Ratio in (20). We note in passing that one can use similar arguments to lower bound the Bregman divergence-based Exploration-by -bOtiiiiizziiiioonn objective in Lattimore and György [32] by the param- eterized Information Ratio for the Bregman divergence of interest, complementing their upper bound.
4 Discussion
We have shown that the convexified Decision-Estimation Coefficient is necessary and sufficient to achieve low regret for adversarial interactive decision making, establishing that convexity governs the price of adversarial outcomes. Our results elucidate the relationship between the DEC, Exploration-by- Opptmmiiiaiiiiiiiiinn... and the Information Ratio, and we hope they will find broader use.
This work adds to a growing body of research which shows that online reinforcement learning with agnostic or adversarial outcomes can be statistically intractable [48, 37J. A promising future direction is to extend our techniques natural semi-adversarial models which reinforcement learning is tractable. Another interesting direction is to address the issue of computational efficiency for large decision spaces.
Acknowledgements
We thank Zak Mhammedi for useful comments and feedback. AR acknowledges support from the ONR through awards N00014-20-1- 12336 and N00014-20-1 1-2944, from the ARO through award W91 W911NN-2111-0328, and from the DOE through award DF-SC0022199, Part of this work was completed while DF was visiting the Simons Institute for the Theory of Computing. KS acknowledges support from NSF CAREER Award 1750575.
The variants in Lattimore and György [32], Lattimore [31] are also invariant under convexification.
10

---

References
[1] J. Abernethy, E. Hazan, and A. Rakhlin. Competing in the dark: An efficient algorithm for bandit linear optimization. In Proc. of the 21st Annual Conference on Learning Theory (COLT), 2008.
[2] N. Alon, S. Ben-David, N. Cesa-Bianchi, and D. Haussler. Scale-sensitive dimensions, uniform convergence, and learnability. Journal of the ACM, 44:615-631, 1997.
[3] J.-Y. Audibert and S. Bubeck. Minimax policies for adversarial and stochastic bandits. In COLT, volume 7, pages 1-122, 2009.
[4] Auer, N. Besa-Bianchi, Y. Freund, and R. E. Schapire. The nonstochastic multiarmed bandit problem. SIAM Journal Computing, 32(():48 77, 2002.
[5] A. Ayoub, Z. Jia, C. Szepesvari, M. Wang, and L. Yang. Model- -ased reinforcement learning with targeted regression. In International Conference Machine Learning, pages 463-474. PMLR, 2020.
[6] S. Bubeck, R. Munos, G. Stoltz, and C. Szepesvári. X-armed bandits. Journal of Machine Learning Research, 12(5), 2011.
[7] S. Bubeck, N. optimization with bandit feedback. Conference on Learning Theory, pages 41-1. JMLR Workshop and Conference Proceedings, 2012.
and S. M. Kakade. Towards minimax policies for online linear
[8] S. Bubeck, Y. T. Lee, and R. Eldan. Kernel-based methods for bandit convex optimization. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, pages 72-85, 2017.
[9] N. Desa-Bianchi and G. Lugosi. Prediction, Learning, and Games. Cambridge University Press, New York, NY, USA, 2006. ISBN 0521841089.
[10] V. Dani, T. P. Hayes, and S. Kakade. The price of bandit information for online optimization. 2007.
[11] A. Daniely, S. Sabato, S. Ben-David, and S. Shalev-Shwartz. Multiclass learnability and the ERM principle. In Proceedings of the 24th Annual Conference on Learning Theory, pages 207-232. 2011.
[12] S. Dean, H. Mania, N. Matni, B. Recht, and S. Tu. On the sample complexity of the linear quadratic regulator. Foundations of Computational Mathematics, 20(4):633-67) 2020.
[13] S. Dong, B. Van Roy, and Z. Zhou. Provably efficient reinforcement learning with aggregated states. arXiv preprint arXiv: 1912.0691100666 2019.
[14] Du, A. Krishnamurthy, Jiang, A. Agarwal, M. Dudik, and J. Langford. Provably efficient RL with rich observations via latent state decoding. In International Conference Machine Learning, pages 1665-1674. PMLR, 2019.
(15) S. S. Du, S. M. Kakade, J. D. Lee, S. Lovett, G. Mahajan, W. Sun, and R. Wang. Bilinear classes: A structural framework for provable generalization RL. International Conference on Machine Learning, 2021.
[16] A. D. Flaxman, A. T. Kalai, and H. B. McMahan. Online convex optimization in the bandit setting: gradient descent without gradient. In Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, pages 385-394, 2005.
[17] D. Foster, S. M. Kakade, J. Qian, and A. Rakhlin. The statistical complexity of interactive decision making. arXiv preprint arXiv:2112.13487, 2021.
[18] E. Hazan and S. Kale. Better algorithms for benign bandits. Journal of Machine Learning Research, 12(4), 2011.
[19] N. Jiang, A. Krishnamurthy, A. Agarwal, J. Langford, and R. E. Schapire. Contextual decision processes with low Bellman rank are PAC-learnable, International Conference on Machine Learning, pages 1704-1713, 2017.
11

---

[20] C. Jin, Z. Yang, Z. Wang, and M. I. Jordan. Provably efficient reinforcement learning with linear function approximation. In Conference on Learning Theory, pages 2137-2143, 2020.
[21] C. Jin, Q. Liu, and S. Miryoosefi. Bellman eluder dimension: New rich classes of RL problems, and sample-efficiet algorithms. Neural Information Processing Systems, 2021.
[22] T. Jin and H. Luo. Simultaneously learning stochastic and adversarial episodic MDPs with known transition. Advances in neural information processing systems, 33:16557-16566, 2020.
[23] J. Kirschner. Informattio-Diirecte ETH Zurich, 2021.
Frapliing-Fruuentisst Analysis and Applications. PhD thesis,
[24] J. Kirschner, T. Lattimore, and A. Krause. Information directed sampling for linear partial monitoring, In Conference on Learning Theory, pages 2328-2369. PMLR, 2020.
[25] J. Kirschner, T. Lattimore, C. Vernade, and C. Szepesvári. Asymptotically optimal information- directed sampling. In Conference on Learning Theory, pages 2777-2821 PMLR, 2021.
[26] R. Kleinberg. Nearly tight bounds for the continuum-armer bandit problem. Advances in Neural Information Processing Systems, 17:697-704, 2004.
[27] A. Krishnamurthy, A. Agarwal, and J. Langford. PAC reinforcement learning with rich observa- tions. In Advances in Neural Information Processing Systems, pages 1840-1848, 2016.
[28] J. Kwon, Y. Efroni, C. Caramanis, and S. Mannor. RL for latent MDPs: Regret guarantees and lower bound. Advances in Neural Information Processing Systems, 34, 2021.
[29] T. Lattimore. Improved regret for zeroth-order adversarial bandit convex optimisation. Mathe- matical Statistics and Learning, (3)):11-3344 2020.
[30] T. Lattimore. Minimax regret for bandit convex optimisation of ridge functions. arXiv preprint arXiv:2106.00444, 2021.
[31] T. Lattimore. Minimax regret for partial monitoring; Infinite outcomes and rustichini' ss regret. arXiv preprini arXiv:2202. 10997, 2022.
[32] T. Lattimore and A. György. Mirror descent and the information ratio. In Conference on Learning Theory, pages 2965- 2992.. PMLR, 2021.
[33] T. Lattimore and C. Szepesvári. An information-theoreee approach to minimax regret in partial monitoring. In Conference Learning Theory, pages 21 2111-2139. PMLR, 2019.
[34] T. Lattimore and C. Szepesvári. Bandit algorithms. Cambridge University Press, 2020.
[35] T. Lattimore and C. Szepesvári. Exploration by optimisation in partial monitoring. In Conference on Learning Theory, pages 2488-2515. PMLR, 2020.
[36] L. Li. A unifying framework for computational reinforcement learning theory. Rutgers, The State University of New Jersey-No New Brunswick, 2009.
[37] Q Liu, Y. Wang, and C. Jin. Learning markov games with adversarial opponents: Efficient algorithms and fundamental limits. arXiv preprint arXiv:2203.066 066800 2022.
[38] S. Magureanu, R. Combes, and A. Proutiere. Lipschitz bandits: Regret lower bound and optimal algorithms. In Conference on Learning Theory, pages 975-999. PMLR, 2014.
[39] A. Modi, N. Jiang, A. Tewari, and S. Singh. Sample complexity of reinforcement learning using linearly combined model ensembles. International Conference on Artificial Intelligence and Statistics, pages 2010-2020. PMLR, 2020.
[40] G. Neu, A. György, C. Szepesvári, al. The online loop-free stochastic shortest-pal path problem. In COLT, volume 2010, pages 231-243. Citeseer, 2010.
[41] G. Neu, A. György, C. Szepesvári, and A. Antos. Online Markov decision processes under bandit feedback. IEEE Transactions Automatic Control, 59:676-691, 2014.
[42] Y. Polyanskiy. Information theoretic methods in statisties and computer science. 2020. URL. https: //people lids. mit. t. hetu/ypp/homppagee/// httpom/pppaeespp___oursssrs course, html.
12

---

[43] Y. Polyanskiy and Y. Wu. Lecture notes on information theory. 2014.
[44] A. Rakhlin, K. Sridharan, and A. Tewari. Online learning; Random averages. combinatorial parameters, and lcarnability. Advances in Neural Information Processing Systems 23, pages 1984-1992 1992, 2010.
[45] D. Russo and B. Van Roy. Eluder dimension and the sample complexity of optimistic exploration.
In Advances in Neural Information Processing Systems, pages 2256-22 2264, 2013.
[46] D. Russo and B. Van Roy. Learning to optimize via posterior sampling, Mathematics of Operations Research, 39(4):1221 11-2211123,, 2014.
[47] D. Russo and B. Van Roy. Learning to optimize via information-directed sampling, Operations Research, 66(1):230-255) 2018.
[48] A. Sekhari, C. Dann, M. Mohri, Y. Mansour, and K. Sridharan. Agnostic reinforcement learning with low-rank MDPs and rich observations. Advances Neural Information Processing Systems, 34, 2021.
[49] Shalev-Shwarke O. Shamir, N. Srebro, and Sridharan. Learnability, stability, and uniform convergence. Journal of Machine Learning Research (JMLR), 2010.
[50] M. Sion. On general minimax theorems. Pacific J. Math., 8:171-176, 1958.
[51] W. Sun, N. Jiang, A. Krishnamurthy, A. Agarwal, and J. Langford. Model-based RL in contextual decision processes: PAC bounds and exponential improvements over model-free approaches. In Conference on learning theory, pages 2898-2933. PMLR, 2019.
[52] V. N. Vapnik. The nature of statistical learning theory. 1995.
[53] R. Wang, R. R. Salakhutdinov, and L. Yang. Reinforcement learning with general value function approximation: Provably efficient approach via bounded eluder dimension. Advances in Neural
Information Processing Systems, 33, 2020.
[54] I.. Yang and M. Wang. Sample-optimal parametric Q-learning using linearly additive features. In International Conference on Machine Learning, pages 6995-7004. PMLR, 2019.
[55] T. Zhang. From c-entropy to KL-entropy: Analysis of minimum information complexity density estimation. The Annals of Statistics, 34(5):2180-2211) 2006.
[56] D. Zhou, Q. Gu, and C. Szepesvari. Nearly minimax optimal reinforcement learning for linear mixture markov decision processes. In Conference on Learning Theory, pages 4532-4576. PMLR, 2021.
[57] A. Zimin and G. Neu. Online learning in episodic markovian decision processes by relative entropy policy search. Advances in neural information processing systems, 26, 2013.
13

---

Checklist
Did you include the license the code and datasets? [No] The code and the data are The checklist follows the references. Please read the checklist guidelines carefully for information on how to answer these questions. For each question, change the default [TODO] to [Yes], [No], , or [N/A] - You are strongly encouraged to include justification your answer, either by referencing the appropriate section of your paper or providing a brief inline description. For example:
Did you include the license to the code and datasets? [Yes]
proprietary.
Did you include the license to the code and datasets? [N/A]
Please do modify the questions and only use the provided macros for your answers. Note that the Checklist section does not count towards the page limit. In your paper, please delete this instructions block and only keep the Checklist section heading above along with the questions/answers below,
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes]
(c) Did you discuss any potential negative societal impacts of your work? [Yes]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes]
3. If you experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or as URL)? [N/A]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [N/A]
(c) Did you report error bars (e.g.. with respect the random seed after running experi- ments multiple times)? [N/A]
(d) Did you include the total amount of compute and the type of resources used (c.g., type of GPUs, internal cluster, or cloud provider)? [N/A]
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you'l 'rere using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
14


Reviews:
[{"review_id": "uUVYHhs92i", "reviewer": "Reviewer_d2Qa", "summary": "The paper considers a general adversarial decision making framework that encompasses (structured) bandit problems with adversarial rewards and reinforcement learning problems with adversarial dynamics. The main result shows that the Decision-Estimation Coefficient is both necessary and sufficient for low regret in the adversarial setting. The paper also provides other interesting results, such as the connection of the Decision-Estimation Coefficient to variants of other well-known complexity measures. ", "questions": "* What are the implications of the work on the practical side as informed by the theoretical development?\n* Please provide some intuitive explanations of what V(\\mathcal{M}) represents, and comment on the conditions for which to be finite. \n* While the authors have explained the role of convexity in lower bound, it is not clear what is the cost we need to pay by taking the convex hull of model class for the upper bound. ", "limitations": "The authors have discussed the limitations of the work.", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths: \n* The paper is a nontrivial extension of the study by Foster et al. [18] in the stochastic setting to the adversarial setting.\n* The results are theoretically sound and novel.\n\nWeakness:\n* While the focus of the work is primarily on sample complexity, Algorithm 1 may not be practical for large decision spaces. Thus, the contributions are limited to theoretical understandings.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "e3SD-RtP7OW", "reviewer": "Reviewer_iALf", "summary": "The paper proposes a new measure of complexity for sequential decision making in the adversarial setting, called (convexified) Decision-Estimation Coefficient (DEC in the following), in term of which matching upper and lower bounds on the regret can be established. This follows directly from the work by Foster et al. (2021) that did the same thing for the stochastic setting.\nIn the stochastic setting, intuitively, the DEC captures the tradeoff between playing high-reward actions (exploitation) and revealing information about the reward model by playing potentially suboptimal actions (exploration). It is then a function of the model class $\\mathcal{M}$ and a trade-off parameter $\\gamma$. The main intuition from the present paper is that the DEC can be used for the adversarial setting by replacing $\\mathcal{M}$ with the convex hull of $\\mathcal{M}$. Intuitively, this is because the adversary could fix a distribution over models and sample a model from it at each round.\nFollowing the same outline as Foster et al. (2021), first a general regret upper bound is established for an abstract algorithm. The algorithm is inspired by the Exploration-by-Optimization framework (Lattimore and Gyorgy, 2021), but allows to establish high-probability regret bounds rather than in expectation. Then, a matching lower bound is established for a meaningful class of algorithms. This is established by first refining the lower bound for the stochastic setting from Foster et al. (2021) by using a novel change-of-measure result. Both are of independent interest. Finally, some concrete examples are given, recovering known results in bandits and RL. Interestingly, convexification provides a very clear picture of what problems are easy and which are not in the adversarial setting: problems that are known to be tractable have $\\mathcal{M}=co(\\mathcal{M})$. ", "questions": "1. How practical is the ExO+ algorithm once instantiated to the bandit and MDP examples? How hard is the optimization problem from line 4? Is the linear time complexity from the exponential weights update from line 3? I think more discussion on the algorithm itself would be helpful.\n2. I checked the main proofs and they seem sound, but I am still a bit puzzled by the fact that convexification is enough to capture the hardness of the adversarial problem. An adversary that commits to a model distribution just seems too easy. Do you have any further intuition about why small convexified DEC is sufficient for small regret?\n3. Do you know of any concrete example where $co(\\mathcal{M})$ is strictly larger than $\\mathcal{M}$ but the adversarial problem is still tractable?\n\nMinor:\n- line 338: structural\n- line 579: \"in fact paper\" ?\n- line 681: where is this Chi-squared-Hellinger inequality from?", "limitations": "Limitations are sufficiently discussed, I just suggest to expand the discussion on the algorithm.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The paper builds heavily on Foster et al. (2021) and is incremental in nature, but has several original and significant contributions, such as the high probability variant of exploration-by-optimization and the refined change-of-measure arguments.\nMostly, this work inherits the strengths and weaknesses of its stochastic predecessor: the main strength being its generality and unification power, the main weakness being the abstractness and highly technical nature of the central result. Specifically, the DEC encodes the exploration-exploitation trade-off in such a literal way that it looks more like an intermediate proof step than a measure of complexity. \nHowever, the effort to establish a general theory of adversarial sequential decision making is remarkable, and a lot of insight can be gained from reading this paper.\nThe paper is also very well written. The technical results are clearly stated and backed up by intuition, the notation is consistent, the separation between existing results and original contributions is clearly established, and the proofs of the main theorems are also well commented and easy to follow.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "CsYRIhtVy87", "reviewer": "Reviewer_tHnk", "summary": "The paper studies a general adversarial decision-making framework and proposes a new complexity measure, the decision estimation coefficient. It also presents a general algorithm, for which algorithm-specific upper bounds are given with respect to the decision estimation coefficient. An algorithm agnostic lower bound is also given.", "questions": "1. It seems the first step of algorithm 1 is fixed to be exponential weights and theorem 2.1 is algorithm-specific. Is it possible to extend eq(4) to other forms of updates (e.g. OMD/FTRL)?\n\n2. The main step of the algorithm involves solving the high probability exploration by optimization objective eq(5). It is not very clear to me if this minimax objective is convex-concave and I am wondering if this can be solved efficiently.  \n\n3. for the reward estimator eq(6), I suppose that one would still need some information about the transition (for p^t(\\pi^t), not required for bandits, but needed for online RL)? However, the transition information is often assumed to be unknown (e.g. see [1]). \n\n[1] Learning Adversarial Markov Decision Processes with Bandit Feedback and Unknown Transition by Chi Jin, Tiancheng Jin, Haipeng Luo, Suvrit Sra, Tiancheng Yu, ICML 2020\n\n=== === === === ===\nThe authors have cleared my concerns after their responses. I do enjoy reading the paper and I've raised my score accordingly. Good luck!", "limitations": "This work is theoretical, thus have no potential negative social impact.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n1. The paper gives one of the first characterizations of complexity in adversarial decision making, which may facilitate further study in bandits/RL etc. The upper and lower bound is new and non-trivial.\n2. The paper is also well-written. The relationships between complexities in adversarial/stochastic settings, and connections between different complexity notions are well explained.\n\nWeaknesses:\nThere is a few places that I am not very clear about. Please see the questions section.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept