Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 4: Ok but not good enough - rejection
review_content: The authors consider analyzing the EXP3.P algorithm for the case of unbounded reward functions, in the sense that the rewards are governed by a Gaussian distribution. The authors first demonstrate a regret lower bound result on the Gaussian MABs when the time horizon is bounded from above. Then, the authors proceed to the analysis of the EXP3.P algorithm on the Gaussian MABs, and establish a regret bound similar to that of Auer et al. 2002. Finally, the authors apply the EXP3.P, where an expert corresponds to a Q-learning network, in the EXP4-RL algorithm, and evaluate it on multiple RL instances.

Major comments: The major technical contributions seem to be the regret bound for EXP3.P for the case of Gaussian MAB, as stated in Theorem 4. Based on the authors' notation in the first paragraph of page 3, the Gaussian reward distribution is stationary across time. This contribution appears marginal, since the Theorem appears to be a straightforward consequence of the EXP3.P regret by Auer et al. 2002 by conditioning on all realized rewards to lie in [-\Delta, \Delta]. The technical part on how to identify the best expert is already dealt with by the analysis in Auer et al. 2002. 

Another contributions are Theorems 1-3, which are regret lower bounds for Gaussian MABs. I am not sure how to interpret these regret lower bounds, since they require the horizon length to be bounded from above. More precisely, the authors show that for any algorithm, there exists a Gaussian MAB instance such that $\text{Reg}(T) \geq c T$ when $T\leq C$, where $c, C$ are instance-dependent  constants. While this bound is a mathematically sound statement, it does not imply anything about the difficulty of the underlying problem when T is large. For example, for regret upper bound of an MAB algorithm, one almost always establishes a guarantee of the form $\text{Reg}(T) \leq \text{Bound}(T)$ for all $T \geq C'$, where $C'$ an instance dependent constant. I am not too sure what is the message the authors are trying to convey here, since we know that the state-of-the-art regret lower bound is $\Omega(\sqrt{KT})$ for sufficiently large T. 

Finally, if I understand the underlying motivation of the authors correctly, the ultimate problem that the authors are trying to address seems to be a stochastic best arm identification problem with (sub-)Gaussian rewards, where an arm here corresponds to a Q-network. I am not sure why the authors resort to EXP type algorithms for a stochastic problem. 

Minor Comments:

I believe that the inequality w RL(T) ≥ O(√T · γ ) on page 4 should be \leq.

In Algorithm 1, in the initialization, w_i should be replaced by w_i(1).

In Algorithm 2, it requires to compute  y_k = E[ˆx_{kj} ], and the authors should elaborate on how the expectation is computed.

In general, there are quite a few typos, and some parts of the writing are  a bit ambiguous in the way they are phrased. I advise the authors to proofread and also polish the writing.
review_title: Contributions appear marginal, and some doubts about the regret lower bound.

final_score: rating: 4: Ok but not good enough - rejection
review_content: This paper contributes to the study of EXP-based algorithms in two aspects. One is on the theoretical aspect: It analyzes the lower and upper bounds of EXP-3 for Gaussian multi-bandit setting for which the reward can be unbounded. The other is on the empirical aspect: It applied EXP4, originally developed for MAB, to Rl applications and demonstrated its advanced empirical performance. 

This paper is overall clearly written. However, my general feeling is EXP3 part and EXP4 part are quite separated and have different flavors. Other than both are algorithms in the EXP family, I did not find much connection between them. 


For the EXP3P part, I have difficulty to appreciate the value of a linear-in-T lower bound for small T. (And this small T range further depends on bandit setting such as \mu, q). In fact, the lower bound has in Theorem also involves \epsilon, which together with T are restricted by an inequality. If I further manipulate the lower bound expression and the required T range, I think it is not hard to obtain quadric or cubic in T lower bound. (One extremal but obviously non-interesting lower bound is  constant*T^n for any  with T<=1).  So I really want to understand why a bound for small T is useful? Even if it is useful, why the order regarding T matters?

The lower bound part also has some basic conceptual mistakes.  When you study a lower bound, please use \Omega() or \Theta() instead of O(). You can say your regret has a lower bound given by \Theta() or simply say your regret = (or \in) \Omega().  But don't say your regret has a lower bound O(), which means nothing. (Technically, T^2 has a lower bound O(T^3) is still correct because T = (or \in) O(T^3).   Further, big O notation is asymptotical notation, i.e., meaningful only for large T. I don't think you can use O(T) to represent a lower bound for small T. 


The experiments only compare Alg 2 with RND. What if you consider a baseline that involve multiple different DQNs and randomizes/explores among them?




review_title: This paper studied EXP algorithms from interesting angles but its results are not strong enough

final_score: rating: 4: Ok but not good enough - rejection
review_content: This paper develops EXP4-style algorithms for Gaussian bandit and RL, proving upper and lower bounds and give empirical evaluations. I have a few questions:

1. I think MAB with unbounded loss is a solved problem? At least these regret bound should be known. For example , see [Hannan consistency in on-line learning in case of unbounded losses under partial monitoring]
2. The RL part is even more confusing. Say we have n experts:
(1) when n is big, then we need to maintain n DQN simultaneously, which sounds unrealistic.
(2) when n is small, as in this paper, a good ensemble can only guarantee you get to match the better one of the two experts.  However, a simple way to do that is to train them and evaluate the policies separately. A lot of technicalities can be avoided this way. So why bother using EXP4?
3. Actually many existing algorithms, at least in tabular RL, are inspired by EXP4. Indeed, consider the policy gradient method on a MAB, then you get an EXP-style algorithm (of course this also depends on the feedback model). See [On the Theory of Policy Gradient Methods: Optimality, Approximation, and Distribution Shift] for example. More sophisticated ways like the Nash V-learning algorithm in [ Near-Optimal Reinforcement Learning with Self-Play], could be applied to solve competitive RL problems. 

Of course, these papers are for tabular RL, which is too simplified. How to use function approximation with EXP4 is an interesting yet challenging question. I think the main weakness of the approaches in this paper is that, it is not clear why exploration with EXP4 is more desirable and why a naive combination with DQN should work. Indeed, I think this comination can be very data inefficient.
review_title: This paper develops EXP4-style algorithms for Gaussian bandit and RL, proving upper and lower bounds and give empirical evaluations. I have a few questions:

Meta-review: This paper consider a classical multi-armed bandit problem (then a more general RL setting) and prove some upper and lower bounds, in cases that were not explicitly studied in the literature.

However, those results are very incremental and do not justify (maybe yet, going beyond the sub-Gaussian case could be interesting) yet acceptance.
Decision: Reject