Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper studies asymptotic instance optimality for interactive decision making with finite decision/action set. The model includes bandits and reinforcement learning, as long as the reward is a function of the observation.

The authors show that the standard, asymptotic lower bound by Lai and Robbins applies to this setting. They further adapt the approach by Lattimore et al (2017) to the more general setting to match the lower bound (asymptotically). Analysis is presented for both finite hypothesis classes and infinite hypothesis classes.
strength_and_weaknesses: The main contribution of the paper is the analysis of asymptotic optimality in a fairly general setting. The results require only mild conditions on the observation distributions, and the usual caveats of a finite action/decision space and a unique optimal action. At least in this context, I believe that the analysis of the log-likelihood ratio test is novel (Lemma 4.3 and its use in Theorem 3.3). The paper also discusses the required covering arguments to extend the result to infinite hpyothesis classes

On the other hand, the algorithmic approach is the same as in Lattimore et al (2017). The algorithm is neither practical from a sample complexity perspective (exponential lower order terms, horizon dependent, not worst-case optimal); nor computationally feasible unless both the hypothesis space and decision set is small. The result should therefore be understand a proof of concept with regard to the achievable sample complexity. It should also noted that going beyond this proof of concept is likely to require significantly further insights and assumptions.
clarity,_quality,_novelty_and_reproducibility: The paper is well written and the results are clearly presented. The body includes a proof sketch of the main result which greatly helps the reader. The main proof idea is solid; however I have not checked the appendix in detail.

Prior work is adequately discussed, however misses the important reference of [Komiyama et al; 2015]. In fact this previous paper encompasses the proposed setting as long as the observation space is finite. It would be great if the authors could add a discussion of this paper.

Komiyama, Junpei, Junya Honda, and Hiroshi Nakagawa. "Regret lower bound and optimal algorithm in finite stochastic partial monitoring." Advances in Neural Information Processing Systems 28 (2015).
summary_of_the_review: In summary, the conceptual contributions of this paper are somewhat limited as they more or less directly extend prior work; however the technical contributions due to the generality of the setting are non-trivial and could inspire follow up work.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: In Strength And Weaknesses
strength_and_weaknesses: This paper designs the first asymptotic instance-optimal algorithm for interactive decision making problems, while prior works mostly focus on the hardest instance. Overall, I think this paper is interesting and novel. However, due to my heavy review load, I feel so bad I can't go through all the details of this paper. Based on what I have read, I would highly recommend this paper and give it a score of 8.

In this part, I will list some questions about some details in this paper.
1. In the definition of $\mathcal{C}(f,n)$, the authors mention the last constraint (4) makes sure $w_{\pi}<\infty$ even if the decision has no regret. Could the authors be more specific in explaining how $w_{\pi}=\infty$ if we remove constraint (4)?
2. I'm a little confused with the instance complexity $\mathcal{C}(f)$ and some other instance complexity in [1,2]. Could the authors give some comparisons in rebuttal?
3. I understand this work provides a tight instance-optimal regret in the asymptotic regime. However, I'm more curious about how the technique used in this paper could inspire other future works. 
4. About the assumption that the optimal policy is unique. I'm thinking about a simple multi-arm bandit problem, where $\mu_1=\mu_2>\mu_i$ for $i=3,...,n$. If the optimal policy is not unique, will the instance-optimality still hold? Or how will it fail?

Due to my limited time, I will consider adding more questions in the rebuttal phase.

[1]Koulik Khamaru, Eric Xia, Martin J Wainwright, and Michael I Jordan. Instance-optimality in optimal value estimation: Adaptivity via variance-reduced Q-learning. arXiv preprint arXiv:2106.14352,2021b.
[2]Li X, Yang W, Zhang Z, et al. Polyak-Ruppert Averaged Q-Leaning is Statistically Efficient[J]. arXiv preprint arXiv:2112.14582, 2021

clarity,_quality,_novelty_and_reproducibility: In Strength And Weaknesses
summary_of_the_review: In Strength And Weaknesses
review_title: null

final_score: rating: 10: strong accept, should be highlighted at the conference
review_content: summary_of_the_paper: This paper studies the theoretical bounds of the classical stochastic MAB problems, and if the conclusion of this paper is not wrong, then as far as I know, this would be the first paper to close the gaps between the asymptotic instance-wise regret upper bounds and lower bounds. 
To be specific, this paper proves that for any consistent algorithm A with regret R_A(n) (n is the time horizon), it must satisfy that limsup_{n->\inf}R_A(n)/log(n) >= C where C is a number determined by the instance and is independent of n and the algorithm. Then, this paper proposes an algorithm with regret bound R(n) such that limsup_{n->\inf}R(n)/log(n) <= C, which perfectly matches the upper bound with no gap. 
strength_and_weaknesses: Strength: This paper's results are very strong and impactful to the community. If the result is not wrong, then this should be the first instance-wise asymptotic algorithm for stochastic MAB, and closes the gap that has been studied for decades. The algorithm proposed in this paper uses a pretty novel method, and the linear-optimization based instance-wise factor is also new.

Weakness: No major weakness, but it is hard for me to guarantee that the proofs and mathematical conclusions are 100% correct.
clarity,_quality,_novelty_and_reproducibility: Clarity is good. It is easy to follow this paper
This paper's conclusions are well supported by theoretical proofs.
The novelty is high, and the results are very good.
The paper does not have issues/concerns of reproducibility
summary_of_the_review: This paper studies a very fundamental problem of stochastic MAB, and proves the asymptotic upper bounds and lower bounds for this problem, which closes the gap that has existed for decades. The algorithm and and conclusions in this paper are novel, and should inspire and influence all MAB related researches to help improve the theoretical conclusions on the upper bounds and lower bounds. Thus, I tend to give a strong accept.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: The paper presents an asymptotic instance-optimal algorithm for decision problems under mild and natural conditions. This is interesting because it circumvents the weaknesses of minimax regret bounds. The idea behind the algorithm is that it alternates between having an estimate of the instance and testing whether estimate is correct. Doing this repeatedly results in increasing the confidence in the estimate. The optimality in the above statement, refers to comparing to the best \emph{consistent} algorithm for the instance at hand -- and consistent algorithms are very natural to consider for this purpose.


A typo: Page 2, belongs -> belong
strength_and_weaknesses: Strengths:
- interesting problem
- natural but elegant approach
- Well presented content


Weaknesses:
- the algorithm is not computable for every problem of interest, so it is unclear to me whether the results are also of practical relevance.

clarity,_quality,_novelty_and_reproducibility: The clarity, quality and novelty of the paper are very good. There is no experimental evaluation, so the reproducibility question is not relevant.
summary_of_the_review: This is a very interesting and good paper, I recommend acceptance.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This paper proposes the first asymptotic instance-optimal algorithm for general interactive decision-making problems with a finite number of decisions. It provides an exact characterization of the complexity of each problem instance ${\cal C}(f)$, which is related to the amount of information to distinguish instance $f$ from other instances with different optimal decisions. The paper designs a three step algorithm based on uniform sampling (to construct MLE of f), identification (to boost confidence in the estimate of f) and exploitation (to maximize reward), whose lengths are carefully adjusted, and proves an asymptotic regret of ${\cal C}(f) \log n$ recovering well-known instance-dependent regret bounds for bandits and improving upon instance-dependent regret bounds for reinforcement learning. 
strength_and_weaknesses: Strengths: 

-The paper proposes a framework for developing an instance-optimal algorithm that outperforms all consistent algorithms on every instance under mild conditions. The generality of the treatment in the paper, as it encompasses tabular reinforcement learning problems, is its main strength.

Weaknesses: 

-No numerical results. It will be interesting to see how the algorithm performs with a finite horizon. 

-Computational complexity of the algorithm can be prohibitive (this was mentioned as a limitation). More discussion on how it scales with the problem size and how to make it computationally efficient will greatly benefit the paper. Please comment on the computational complexity of different interactive decision-making problems.
 
-The algorithm requires the number of interactions as input.

clarity,_quality,_novelty_and_reproducibility: Clarity: 

-Writing is mostly clear. Does the setup also capture undiscounted non-episodic RL tasks? 

-Please provide more explanations of some assumptions made in the paper. For instance, why do you need to impose a unique optimal decision for each instance? 

Quality and Novelty:

-Characterization of instance-dependent complexity of interactive decision-making problems, providing an asymptotic regret lower bounds for any consistent algorithm and proposing an algorithm that achieves asymptotic optimal regret are significant and novel.

summary_of_the_review: Overall, this paper presents a solid theoretical contribution to interactive decision-making problems. The addition of insights about the finite-time performance and the practical applicability of the proposed algorithm will further strengthen the paper.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: This paper studies asymptotic instance optimality for interactive decision making with finite decision/action set. The model includes bandits and episodic reinforcement learning, as long as the reward is a function of the observation. The authors show that the standard, asymptotic lower bound applies to this setting. They further adapt the approach by Lattimore & Szepesvari (2017) to the more general setting to match the lower bound (asymptotically). Analysis is presented for both finite hypothesis classes and infinite hypothesis classes, under some mild assumptions. The main improvement over the work of Lattimore & Szepesvari is the application of a likelihood ratio test about the most likely hypothesis, which is necessary to achieve the generality presented in the paper. 

The paper contains a number of typos, so the authors are encouraged to carefully check and correct these for the final version.
justification_for_why_not_higher_score: While most reviewers are quite enthusiastic, I see two limitations of the paper:
- The model is not as general as suggested in the title (e.g., it does not apply to non-episodic RL).
- While the idea of using MLE estimation and the likelihood ratio test is novel in this context, the extension on top of the work of Lattimore & Szepesvari (2017) is somewhat limited.
- The algorithm is not practical in the general case.
justification_for_why_not_lower_score: The results are novel and of interest to the community working on sequential decision making problems.
Decision: Accept: poster