Regret Bounds and Reinforcement Learning Exploration of EXP-based Algorithms

Authors: Mengfan Xu, Diego Klabjan
Primary area: learning theory
Keywords: Bandit, reinforcement learning, EXP-based algorithms

Abstract:
We study the challenging exploration incentive problem in both bandit and reinforcement learning, where the rewards are scale-free and potentially unbounded, driven by real-world scenarios and differing from existing work. Past works in reinforcement learning either assume costly interactions with an environment or propose algorithms finding potentially low quality local maxima. Motivated by EXP-type methods that integrate multiple agents (experts) for exploration in bandits with the assumption that rewards are bounded, we propose new algorithms, namely EXP4.P and EXP4-RL for exploration in the unbounded reward case, and demonstrate their effectiveness in these new settings. Unbounded rewards introduce challenges as the regret cannot be limited by the number of trials, and selecting suboptimal arms may lead to infinite regret.  Specifically, we establish EXP4.P's regret upper bounds in both bounded and unbounded linear and stochastic contextual bandits. Surprisingly, we also find that by including one sufficiently competent expert, EXP4.P can achieve global optimality in the linear case. This unbounded reward result is also applicable to a revised version of EXP3.P in the Multi-armed Bandit scenario. In EXP4-RL, we extend EXP4.P from bandit scenarios to reinforcement learning to incentivize exploration by multiple agents, including one high-performing agent, for both efficiency and excellence. This algorithm has been tested on difficult-to-explore games and shows significant improvements in exploration compared to state-of-the-art.

Decision: reject
Reviewer scores: 5, 5, 3, 3

Reviews and discussion:
<thread>
creation date:
1730220570828

thread_type:
official_review

<thread_object>
creator: reviewer_pf6n

<content>
summary:
The paper proposes several variants of EXP algorithms for bandits and RL. It provides high probability regret bounds for different settings, and evaluates the performances on some RL games.

strengths:
MAB/RL with unbounded rewards is a challenging setting.

weaknesses:
- The presentation of this work lacks clarity and requires significant improvement. The problem formulation is unclear, with various assumptions scattered throughout the paper. 
- Several theoretical results seem problematic. For example, the high probability results in this work show that the regret bounds hold with probability (1-\delta)(1-\eta)^T. However, as $T$ increases, this probability can become arbitrarily small, which indicates that the bounds do not hold “in high probability” any more. 
- Another questionable result is the Corollary in Sec 3.1. It claims that when the horizon becomes 1, EXP4.P and EXP4-RL can become equivalent, thus the results of Theorems 4 and 7 apply to this case.  However, the design of EXP4-RL has a fundamental differences with EXP4.P: EXP4-RL updates the policy chosen by each expert (Q-network) after each episode with the collected data, while that under EXP4.P is not updated by the algorithm. The updating of the experts’ policies introduce complicated interactions between the experts and the decision-making agent, which is not captured in the analysis of EXP4.P, thus the results no longer hold.

questions:
- MAB/RL with sub-gaussian rewards has been well-studied in the literature. What are the new challenges in the problems considered in this work?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730593842244

thread_type:
official_review

<thread_object>
creator: reviewer_hmke

<content>
summary:
The paper introduces a novel algorithm, EXP4.P, designed to efficiently explore adversarial contextual bandit problems with unbounded rewards. This algorithm is further extended to EXP4-RL for exploring Markov Decision Processes (MDPs) with unbounded rewards. The authors evaluate EXP4-RL on challenging environments, demonstrating state-of-the-art performance.

strengths:
1. The exploration of environments with unbounded rewards is a crucial and challenging issue in the field.

2. The algorithms are supported by strong theoretical guarantees and comprehensive experimental comparisons.

3. The paper extends the understanding of EXP-type algorithms, offering techniques that may be generalizable to similar algorithms.

weaknesses:
The presentation needs improvement.
- The introduction is too extensive, which may dilute the focus on the core contributions. A more concise introduction with a clear statement of contributions could be better. The comparisons with related works could be separately discussed.
- The main results, particularly Theorems 2 to 4, are not presented clearly. If these theorems share common assumptions, it would be beneficial to outline these assumptions outside the theorems. Consolidating the main results into one or two comprehensive theorems, followed by corollaries for additional insights, could improve clarity.
- In line 786, there are '(authors)?' not addressed yet.

questions:
1. Could the authors offer a more detailed comparison with closely related works? Specifically, it would be helpful to understand the contexts in which unbounded rewards have not been thoroughly studied versus where they have been adequately addressed. For instance, stochastic contextual linear bandits do not typically suffer from issues with sub-Gaussian noise on rewards, as discussed in [1].

2. Could the authors provide an intuitive explanation of why unbounded rewards pose significant difficulties in adversarial settings? And why the modification in EXP4.P is in the spirit of EXP3.P but the terms are much different?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730672364635

thread_type:
official_review

<thread_object>
creator: reviewer_ud4p

<content>
summary:
This work studies the problem of EXP-based exploration in bandits and RL. A set of theoretical results have been provided, including contextual bandit with bounded reward, linear/stochastic contextual bandit with unbounded reward, MAB with unbounded reward, and also MDP. Experimental results on RL games are also reported to demonstrate the efficiency of the proposed design.

strengths:
- The problem of EXP-based exploration is an interesting theoretical topic worth exploration in both bandits and RL. While I am not exactly familiar with the SOTA studies, this work claims to address several requirements (e.g., bounded rewards) and also new problem settings (e.g., high probability bounds), which I believe is of interests to the community.

- The study is comprehensive in both theory and experiments. Different settings ranging from MAB, contextual bandits and RL are studied. The experimental results are also helpful in providing supporting evidences to the proposed designs.

weaknesses:
My main concern of this work is on its clarity, especially regarding the following aspects:

- The main contribution of this work. This work targets a lot of problems, which is a strength; however, at the same time, I believe the authors can do a better job by explaining the addressed core problems and settings more clearly, instead of providing all the results in the main paper. The discussions in Appendix G are helpful, while I do not think it covers the entire work (e.g., the studies on RL).

- Another suggestion is that probably the presentation can be improved if the notations of the settings, e.g., the different regrets can be defined when they are discussed. The current presentation with all notations flooded in Section 2 is a bit dry in the first place, while hard to refer to upon the discussions.

-  I am in general wondering about the core technical contributions/technical challenges in this work. The authors have provided a full set of results, which I appreciated; however, there are limited discussions on the intuitions. E.g., in EXP4.P, the highlighted terms are the keys in obtaining the desired results I conjecture, whose form (i.e., why they are constructed this way) can be explained a bit more.

questions:
My main suggestions are listed in the weakness section, please find below for a few additional questions:

- In line 256, it claims that the regret in Theorem 1 does not depend on N, while it seems there are several terms that depending on N in the formula, especially the second term that is of order $\sqrt{NT}$?

- In line 226, it claims that the expected regret is bounded using  Rademacher complexity and VC dimension, I would appreciate a pointer to where such usage happens.
</content>
</thread_object>

</thread>
<thread>
creation date:
1731334211820

thread_type:
official_review

<thread_object>
creator: reviewer_ukfj

<content>
summary:
The paper studies EXP-type algorithms for adversarial bandits and contextual bandits with unbounded rewards. It proposes EXP3.P and EXP4.P algorithms for these settings, and derived corresponding regret bounds. It also proposes an extension of EXP4.P to RL setting and derive regret bound for it. Further numerical experiments are done with EXP4-RL for Mountain Car and Montezuma's revenge to show that EXP4-RL induces better exploratory behaviour than RND (Random Network Distillation).

strengths:
1. Extending EXP type algorithms to unbounded reward settings is interesting.
2. Specifically, its impact for stochastic contextual bandits with unbounded rewards is novel and can be helpful to remove the typical bounded reward assumptions in contextual bandits.
3. Further generalisation of EXP4.P to RL and its numerical validations are useful contributions to design exploration strategies in hard RL problems.

weaknesses:
1. The writing is very hard to decode. It is better 
2. The citation style is strange and uninformative. Generally () is for eqref and [] for citation. Also, there are improperly compiled (e.g. (author?) (3)). Please check them for better readability.
3. The simple regret definition used here is a bit strange. (Expected) simple regret is the difference in expected reward obtained by optimal policy and present policy at time $t$ [1,2]. Why calling this new definition "simple regret"? 
4. The experimental evaluations have some shortcomings. Please check questions 2-4.

[1] Bubeck, S., Munos, R., and Stoltz, G. (2009). Pure exploration in multi-armed bandits problems. In The 20st International conference on Algorithmic learning theory, pages 23–37. Springer.
[2] Zixin Zhong, Wang Chi Cheung, Vincent Y. F. Tan (2023). Achieving the Pareto Frontier of Regret Minimization and Best Arm Identification in Multi-Armed Bandits. Trans. Mach. Learn. Res.

questions:
1. What is the main technical novelty that allows you to take EXP4 to unbounded reward settings? What was the main technical challenge and which key lemmas allow you to solve it? This is not explicit from the writing but it is the main technical contribution in my view. Can you explicate it?
2. Why choosing (only) RND for experiments? Why not any other and more established baseline for Deep RL, like intrinsic motivation, entropy regularized RL (e.g. SAC)? A more exhaustive experimental evaluation in the deep RL setting would be convincing.
3. Why not demonstrating the cumulative reward in each of the experiments? In the end, the theoretical claims are that making the proposed changes make EXP4 a regret-efficient algorithm in unbounded reward setting. I do not see how this is reflect in experiments. 
4. In experiments, the environments studied have only bounded rewards. Can we see some numerical evidence where EXP3 and EXP4 fail while EXP4.P and variants are better performing? 
5. How does the result compare with other stochastic contextual bandit algorithms that can handle unbounded rewards, such as [3], [4] etc.
6. A philosophical query is: why studying unbounded rewards in adversarial setting is interesting? Except technical challenges, what does it bring extra with respect to stochastic setting with unbounded rewards or unbounded corruptions?

[3] Marc Abeille and Alessandro Lazaric. Linear thompson sampling revisited. In AISTATS, 2017.
[4] Vecchia, R.D., & Basu, D. (2023). Stochastic Online Instrumental Variable Regression: Regrets for Endogeneity and Bandit Feedback. arXIv 2302.09357.
</content>
</thread_object>

</thread>


Metareview: