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 framework for the reinforcement learning problem (specifically, the MAB and finite-horizon tabular MDP) when the instances can be divided into two groups; one group which tolerates risky action selections for the sake of exploration, and another group for which the agent just focuses on maximizing the rewards. A goal is to achieve the near-optimal O(logT) regret for the first group while achieving a time-horizon-independent constant regret for the second group.

Under the assumption that the underlying distributions of the sate, action, and reward are identical for the two groups, and that the proportion of the number of instances in the first vs second group is constant and fixed, the authors provide a framework algorithm which achieves the goal with high probability.

Specifically, the core of these algorithms is to make action decisions according to the "pessimism in the face of uncertainty" principle for the second group. For the bandit problem, the authors propose a specific algorithm which employs the usual UCB algorithm for the first group and select the maximizer of the LCB (Lower confidence bound) for the second group.
strengths_and_weaknesses: Strengths:

1. The authors provide detailed lower bound analysis for this problem. Specifically for the gap-independent case, the authors provide an example where it is impossible to do better than employing the near-optimal regret reinforcement learning algorithm to the whole instance sequence without making any distinction between the two groups.



2. The authors derive the regret guarantee for the "framework" algorithm rather than just a specific algorithm. The framework requries to use a near-optimal regret reinforcement learning algorithm (that satisfies Condition 4.6) for the first group and then use the pessimism in the face of uncertaint principle (satisfying Condition 4.4) for the second group. As long as Conditions 4.6 and 4.4 are satisfied, the algorithm can be diversified according to the specific inner algorithms used. Hence the framework can apply to a wide range of problems with different kinds of reward functions.



3. The regret guarantee hold without the assuming the uniqueness of the optimal policy.
questions: Questions

It would be good to have more details on the use of clipping operator. The authors use it in the algorithm but just refer the explanation to other papers
limitations: I did not find any discussion on societal impact .
review_title: null

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: This work focused on reinforcement learning and proposed a novel framework to utilize the tiered structure in applications. More specifically, the users are divided into two groups: a risk-tolerant group with the UCB-types algorithm and a risk-averse group with the LCB-types algorithm. With this structure, the author shows that there is nearly no advantage in the gap-independent instance but can improve the regret guarantee from log-T to constant in the gap-dependent instance. 

strengths_and_weaknesses: Strength:

1. This work proposed a novel structure to utilize the tiered structure in applications and can improve the performance to constant regret guarantee with the gap-dependent instance.

2. This work provides a theoretical lower bound for the gap-independent instance and shows that tiered can provide nearly no help in this case.

3. This work first considers the pessimism algorithm in online reinforcement learning and combines it with the optimistic rule, which may be of independent interest.

Weakness:

1. The algorithms require the initial state to be fixed ($s_1$), which is much more restrictive than previous work in reinforcement learning.

2. The intuition of introducing a tiered structure is not clear. For the tiered structure, the author mentions that users can be divided into multiple groups depending on their different preferences and tolerance of the risk that results from the necessary exploration to improve the policy. However, from the setting, there is no difference between these two groups in reward, transition, or regret. It is unclear what the critical difference between risk-tolerant and risk-averse people is. It is also unclear why we need to introduce the tiered structure and consider the two groups of people individually. A much more reasonable structure to represent different preferences and tolerance is introducing different rewards for different groups.


questions: 1. For both Algorithm 2 and Algorithm 3, only the data from online policy $\pi^O$ are used to design the policy, and other data from policy $\pi^E$ are ignored, which seems will deteriorate the algorithm performance. Is there some intuition behind it or just to protect the personal privacy of group E?

2. For the Gap-dependent setting, the author mentions recent advances in regret guarantees for reinforcement learning. More recent advanced works have focused on using the function approximation techniques in MDPs. For instance, He et al. [2022] first obtained a logarithmic regret with the gap-dependent setting. Therefore, it is better if the author can mention them or have some discussion about them.

He J, Zhou D, Gu Q. Logarithmic regret for reinforcement learning with linear function approximation. ICML2021


limitations: This paper provides theoretical guarantees for learning linear bandit and linear mixture MDP. There is no negative societal impact.
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: This paper formulated and studied the tiered RL problems where the uses are divided into two groups and treated separately. They showed that the constant and log K regret are achievable while keeping the online algorithm near-optimal for bandit and RL settings, respectively.
strengths_and_weaknesses: **Strengths**

1. This paper is well written and organized, and the insights behind the main results are well presented. 
2. Both MAB and RL settings are considered in this paper. The regret bound is comparable with the best existing results.

**Weakness**
1. The model assumes the users from two groups share the same transition and reward function, there is still some gap between the model and reality.
2. It would be great if the framework could model the total "toleration budgets" of different groups.
questions: 1. I have a general question about the Tiered RL Framework. Under the assumption that $Env^O = Env^E,$ if the definition of regret is the same for both groups, why do different groups' risk tolerances matter? Is exploration still necessary if the $Alg^E$ can already achieve constant regret after certain timesteps/episodes? We are eventually looking for an algorithm that can give us lower regret. Then maybe it is also worth looking at how many samples are needed by collecting with the online algorithm such that a constant regret is achievable by using an exploitation algorithm.

2. Since PVI and LCB are widely used in offline settings, can the authors clarify what the novel technical contributions of this paper are?

limitations: I don't think this paper has any potential negative societal impact.
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: - They investigate a 2-tiered play structure in the stochastic bandit and MDPs, one of which is the "exploiters".  
- Those two groups play the same instance simultaneously, and the exploiter group was shown to achieve a (gap-dependent) constant regret by using a conservative strategy (LCB) and exploit information from the other group (explorer). The regret of the explorer remains (near-)optimal.
- Although there exists studies of decoupled exploration-exploitation in bandit settings, the differential is that it can be naturally extended to MDPs by using an algorithm (UCB/LCB) which does not use sample weights, resulting in high compatibility to the MDPs.  
strengths_and_weaknesses: - Originality: somewhat weak
	- The idea of decoupled exploration-exploitation was inherited from previous work. Since the previous work considers adversarial setting also, its method uses sample-weights, which has a risk of the "curse of horizon" when extended to MDPs. It is not a surprising idea to use UCB/LCB to avoid the problem.  
- Quality: excellent
	- Their analysis is convincing since it proves the problem-dependent constant regret as well as the impossibility of the problem-independent constant regret.  
- Clarity: good
	- This paper is well organized and reads naturally from a simple MAB setup to a table RL setup.  
- Significance: good
	- It is a significant contribution that a constant regret can be achieved also in reinforcement learning by decoupling the explorers and the exploiters.  
questions: - Are there concrete examples of exploiter groups who share a homogeneous model with explorers?
limitations: - Limited to the setting where two parties continue to play at the same time.  
- Dividing into tiers and favoring one side (the exploiter group) would imply that there are differences that should be favored (e.g., they are wealthy, paying users). Such differences may have an impact on transitions and reward distributions, but they are using a homogeneous model. Therefore, it remains to be seen if there are specific examples that would have an impact in realistic problems.  
- In that case, since the method only learns the data from the explorer group, the exploiter group might suffer a linear regret.
review_title: null

Meta-review: metareview: The new two-group RL framework is interesting, even though it is somewhat restricted to assume the exact same model for both groups. Both the gap-independent and the gap-dependent settings are discussed properly, with lower and upper bounds. Overall we believe that the paper is worth publishing at NeurIPS.
confidence: Certain
Decision: Accept