Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: 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.
In 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.
Following 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})$. 
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.
Mostly, 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. 
However, 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.
The 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.
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.
2. 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?
3. Do you know of any concrete example where $co(\mathcal{M})$ is strictly larger than $\mathcal{M}$ but the adversarial problem is still tractable?

Minor:
- line 338: structural
- line 579: "in fact paper" ?
- 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.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: 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. 
strengths_and_weaknesses: Strengths: 
* The paper is a nontrivial extension of the study by Foster et al. [18] in the stochastic setting to the adversarial setting.
* The results are theoretically sound and novel.

Weakness:
* 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.

questions: * What are the implications of the work on the practical side as informed by the theoretical development?
* Please provide some intuitive explanations of what V(\mathcal{M}) represents, and comment on the conditions for which to be finite. 
* 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.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: 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.
strengths_and_weaknesses: Strengths:
1. 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.
2. The paper is also well-written. The relationships between complexities in adversarial/stochastic settings, and connections between different complexity notions are well explained.

Weaknesses:
There is a few places that I am not very clear about. Please see the questions section.
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)?

2. 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.  

3. 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]). 

[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

=== === === === ===
The 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.
review_title: null

Meta-review: metareview: The submission studies the important problem of quantifying the complexity of learning in adversarial sequential decision problems with partial feedback. Although the problem is well-studied in the full-information setting, the same problems in the bandit and reinforcement learning settings are largely open. It is still not clear how the optimal regret depends on the shape of the action and parameter spaces. 

This paper makes a significant contribution in this area. It shows that the Decision-Estimation Coefficient (introduced by Foster et al. 2021) quantifies the complexity of learning in many adversarial sequential decision problems. This result would be of interest to the online learning community in NeurIPS. Although the paper does not really resolve any open questions or show substantial improvements that wouldn't be possible with other techniques, the paper provides new important insights, and I believe the introduced tools and techniques in this paper will ultimately lead to such improvements. 
confidence: Certain
Decision: Accept