Diminishing Exploration: A Minimalist Approach to Piecewise Stationary Multi-Armed Bandits

Authors: Kuan-Ta Li, Ping-Chun Hsieh, Yu-Chih Huang
Primary area: reinforcement learning
Keywords: Piecewise-stationary bandit, multi-armed bandit, regret analysis, change detection

Abstract:
The piecewise-stationary bandit problem is an important variant of the multi-armed bandit problem that further considers abrupt changes in the reward distributions. The main theme of the problem is the trade-off between exploration for detecting environment changes and exploitation of traditional bandit algorithms. While this problem has been extensively investigated, existing works either assume knowledge about the number of change points $M$ or require extremely high computational complexity. In this work, we revisit the piecewise-stationary bandit problem from a minimalist perspective. We propose a novel and generic exploration mechanism, called diminishing exploration, which eliminates the need for knowledge about $M$ and can be used in conjunction with an existing change detection-based algorithm to achieve near-optimal regret scaling. Simulation results show that despite oblivious of $M$, equipping existing algorithms with the proposed diminishing exploration generally achieves better empirical regret than the traditional uniform exploration.

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

Reviews and discussion:
<thread>
creation date:
1729161133971

thread_type:
official_review

<thread_object>
creator: reviewer_zgn5

<content>
summary:
The paper targets piece-wise stationary bandit setting. In this paper, a diminishing exploration mechanism is proposed. Apparently, the mechanism does not require the prior knowledge of the number of stationary segments. This mechanism can be integrated into those algorithms that rely on change point detectors. The authors claim that by using their mechanism in optimizing the forced exploration, they achieve better empirical regret than the traditional forced exploration methods.

strengths:
Their work is authentic and original.

weaknesses:
1. Usually in these kind of settings, there is an assumption that sets a minimum distance between any two consecutive change points in the environment. This type of assumption exists to make sure that the change-point-detector-based algorithm have (statistically) enough time to detect any possible change in the environment and hence the algorithm is able to detect any change to the environment. Naturally, this implies that, as we get more distance from a change point in the environment, the probability of facing another change in the environment is more than the time when we were closer to the last change point. Hence we need to collect more samples from various arms to see if there has been a change that makes our current decisions sub-optimal. This argument (which i believe is correct) has contradiction with the nature of your method in decreasing forced exploration as we get distance from the last change point.

2. The experiments section needs to be clarified more by providing more clear information about the setups. 

3. The number of arms involved in the synthetic data experiment is low and it raises the question about the performance of the proposed technique in scenarios with more arms. 

4. The writing of the text is not smooth to follow. It can definitely be improved.

questions:
The effect of the mechanism is not motivated within the context of real-life applications. For instance, the question i can ask is; in which application scenario reducing this forced exploration can play an important role? you might want to point to applications with large number of arms. Then I can ask; then why do the experiments focus on small number of arms and do not show the performance of the proposed method in scenarios with a large number of arms?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730425454940

thread_type:
official_review

<thread_object>
creator: reviewer_o4hn

<content>
summary:
This paper considers the non-stationary stochastic bandit problem, where the reward distributions of arms can change over time. The challenge is to balance the trade-off between variations in these distributions and following a bandit algorithm to optimize the current reward at each stage. To this end, the paper proposes a new change detection algorithm using a diminishing exploration rate, which can be coupled with existing change detection frameworks and bandit algorithms. The paper provides a theoretical guarantee for the proposed algorithm, demonstrated by an optimal regret guarantee. Additionally, it extends the problem to a specific setting involving arm changes and shows a regret guarantee for this case as well. Lastly, a numerical study with simulation experiments demonstrates significant improvement over existing algorithms.

strengths:
1. The paper is clearly written and easy to follow. The comparison with existing work in Table 1 is particularly helpful in understanding the contributions of this paper.
2. The proposed diminishing rate is novel in this specific non-stationary bandit setting. In addition, the algorithm does not require knowledge of the total variation and is relatively easy to implement.
3. The claims are well-supported by the theoretical guarantees. Clear explanations of the theorems are provided, aiding in understanding the key takeaways.
4. Extensive numerical experiments are conducted to demonstrate the algorithm’s performance, showing significantly smaller regret compared to existing benchmarks.

weaknesses:
1. If I understand this paper correctly, one of the main contributions of the paper is that the proposed algorithm does not require knowledge of $M$ and achieves a $\sqrt{MT}$ guarantee and $KT$ computation complexity. One of my major concerns is that, based on Table 1, it seems like (Wei & Luo 2021) has studied the setting without knowledge of $M$, proposing the algorithm Master, which also achieves optimal regret and the same computational complexity. So I am a bit confused by the paper's claim that it studies this novel setting with an optimal guarantee.

2. Additionally, aside from this single parameter change (exploration rate), it would be helpful to understand what other novelties are introduced. Based on the current modification, it is somewhat unclear how the algorithm stands out in terms of novelty.

3. The second concern is about the choice of $\alpha$. It seems like the paper never explicitly states how to choose the parameter $\alpha$, which, however, is key in the algorithm and used in almost all cases. Also, the regret bound has a dependency on $\alpha$. Therefore, without this, it is hard to quantify how we can deploy this algorithm without parameter tuning and how the regret really changes with $T$.

4. The paper lists the statement about the computational complexity in Table 1, which is $KT$. However, it seems like there is no theoretical or formal statement explaining why this is true. A further demonstration would be very helpful.

5. I have a further question: Why not consider the line of work on total variation (TV) in non-stationary bandits? There is a rich body of work in that area.

questions:
I would kindly refer to the weakness part. I would appreciate the authors' responses to the main points.
</content>
</thread_object>

</thread>
<thread>
creation date:
1731106267465

thread_type:
official_review

<thread_object>
creator: reviewer_rfsn

<content>
summary:
This paper revisits a well-studied problem, the piecewise stationary multi-armed bandit problem, and proposes a new exploration scheme, referred to as "diminishing exploration (DE)", which can be used in conjunction with change detection-based approaches. Regret bounds have been developed for the proposed algorithms, and preliminary experiment results are demonstrated in Section 6.

strengths:
- The paper is well-written and the authors clearly present their main ideas. 

- The diminishing exploration (DE) approach can be applied to many change detection based algorithms.

weaknesses:
- This paper seems to lack novelty. The standard piecewise stationary bandits have been extensively studied in the past decade. Also, the main idea of this paper, the diminishing exploration (DE), seems to be quite straightforward.

- There is also not much novelty in the analysis techniques. The regret analyses in this paper seem standard.

- The assumptions in this paper also seem restrictive. For instance, Assumption 4.2 seems both unnatural and unnecessary. It seems that some assumptions (e.g. Assumption 4.2) are from previous literatures, but it is better to get rid of such unnatural and unnecessary assumptions. Can the authors develop regret bounds for DE without such restrictive assumptions? Please explain.

questions:
Please try to address the weaknesses above.
</content>
</thread_object>

</thread>
<thread>
creation date:
1731256440855

thread_type:
official_review

<thread_object>
creator: reviewer_mdqn

<content>
summary:
This paper considers stochastic multi-armed bandits with structured nonstationarity, specifically where the arms change value at $M$ points throughout the time horizon $T$ (where $M$ is unknown) but are otherwise stationary. The authors develop a new algorithm to handle the exploration aspect of this problem, which they combine with an existing change-detection algorithm.

They show theoretically that this approach achieves sublinear, $\mathcal{O}(\sqrt{MT})$ regret with computational complexity $\mathcal{O}(KT)$, and show strong empirical performance on a simulator based on a public dataset from Yahoo.

strengths:
1. Nonstationarity is an important challenge for multi-armed bandits essential to making this approach useful for a broad range of real-world problems. This paper is part of the literature on "active methods" in piecewise-stationary bandits that actively try to detect and adapt to change points. This paper overcomes a limiting assumption in existing work, which is the assumption that the number of change points are known a priori (thus the existing algorithms could tune specifically with that knowledge). This advance could help make MAB solvers with piecewise stationarity more useful.

2. The authors propose a novel approach for exploration, using a "diminishing exploration" approach where the amount of exploration decays with time. This method does not require prior knowledge of the number of change points $M$, and can be paired with a range of existing change detection algorithms. The algorithm moves from an exploration stage, then update initial estimates of $u$, then act following a UCB approach (based on M-UCB), while doing a per-timestep check for change detection. The authors add a heuristic that adds a skipping mechanism (algorithm 2) to ignore potentially unnecessary arms, with a tuning parameter $\eta$ that describes how conservative to be in skipping. 

3. The authors show theoretically that the regret is bounded by $\tilde{\mathcal{O}} \sqrt{MKT})$. This result is found by studying the number of times the optimal arm changes $S$ (referred to as the number of "super-segments").

weaknesses:
1. The choice to model nonstationarity as a series of piecewise-stationary with a fixed number of change points is not very well justified. What are some examples for why this assumption would arise, rather than a smoother type of nonstationarity?

2. Related to #1, this paper compares to other literature in piecewise-stationary bandits (theoretically and empirically), but there is a greater amount of literature on nonstationary bandits. One possible analysis that could help strengthen the usefulness of this paper is to empirically evaluate your method on more general nonstationary settings, and compare your performance with existing methods for nonstationary bandits. I imagine this would be a more realistic model for the vast array of real-world settings. If you are able to perform well even in those settings, that would be extremely useful. However even if not, it would still be useful to show/quantify.

3. Algorithm 2 (the skipping mechanism) is a heuristic approach, but the importance of this heuristic is not studied. It would help to include an ablation to shows the impact of this heuristic --- how much of the improved performance depends on this?

4. GLR-UCB seems to perform very similarly with and without your diminishing exploration approach? Same as CUSUM-UCB, with and without diminishing exploration, as T scales and on the Yahoo dataset. 


*Detailed comments*

There are small grammatical things that could be improved throughout the paper. 
- line 21: "despite oblivious" -> "despite being oblivious"
- line 23: delete "the"
- line 36: delete both "the"s


Small issues:
- line 213: "however, in the other sense." ends the sentence. This is an incomplete sentence?
- line 220: "a perfect balance" -> "an optimal balance"

- in Intro, M-UCB and GLR-UCB is not defined or described.
- Plots are very small and hard to read, especially to distinguish the line and clarify which approaches are your vs. existing methods.

questions:
1. Experiments describe that evaluations beyond 20,000 timesteps was infeasible because of long runtime. But Figure 4d appears to show up to $T=200,000$?

2. The M-UCB and GLR-UCB approaches that this algorithm builds off of does not seem to be described? How do they work? What does the "M" in M-UCB stand for?
</content>
</thread_object>

</thread>
<thread>
creation date:
1732561222955

thread_type:
public_comment

<thread_object>
creator: ~argyrios_gerogiannis1

<content>
title:
Reference Suggestion

comment:
Dear Authors of Submission 5906,

Thank you for this interesting work on Piecewise Stationary Multi-Armed Bandits and for discussing our work on MASTER (https://arxiv.org/abs/2410.13772) in the reviewer discussions. We appreciate your acknowledgment of its relevance to your study.

To further help readers understand MASTER's limitations, I kindly suggest citing our paper, "Is Prior-Free Black-Box Non-Stationary Reinforcement Learning Feasible?" in the next version of your paper. I believe it would complement your research and provide additional context.

Thank you for considering this suggestion.
</content>
</thread_object>

</thread>
<thread>
creation date:
1732629569564

thread_type:
official_comment

<thread_object>
creator: authors

<content>
comment:
Thanks to the reminder by Reviewer mdQN, we became aware that there were typos in our previous links to the new figures. We have corrected the links and provided the updated figures below:

The figure of the slowly changing environment:
https://imgur.com/a/slow-change-environment-Q76TBxB

The figure of slowly changing environment regret:
https://imgur.com/a/slowly-change-regret-b9UPCsV

Regret with Skipping Mechanism:
https://imgur.com/a/Sqr845R

Regret of Yahoo Dataset with a larger horizon $T$:
https://imgur.com/a/vIpgAqZ

A zoomed-in view of Figure 3(c):
https://imgur.com/a/YDdYMAf
</content>
</thread_object>

</thread>
<thread>
creation date:
1732794408452

thread_type:
official_comment

<thread_object>
creator: authors

<content>
comment:
We sincerely thank all the reviewers for their valuable feedback, which has greatly contributed to improving our work. In response to your comments, we have revised the paper, and we believe the latest version represents a significant enhancement. Below, we summarize the key improvements:  

- We corrected typos and grammatical issues throughout the paper to improve clarity and readability.  

-  The introduction has been refined with more detailed descriptions and additional references, resulting in a smoother and more comprehensive presentation.  

- We completed the parameter configurations for the experiments and added a table to enhance readability and accessibility.  

* Due to space constraints, we were unable to enlarge the figures in Section 6. However, we have included zoomed-in versions of the simulation figures in Appendix G for better visualization.  

* M-UCB and GLR-UCB algorithms are now explicitly explained in the Introduction.  

* A new reference (Gerogiannis et al. 2024) has been added to highlight that MASTER may not perform well in practical scenarios, providing stronger motivation for our proposed approach.  

- All new experimental results on piecewise stationary scenarios generated during the rebuttal period have been included in Appendix F.  

- The extension section has been slightly revised to clarify that the underlying change detection (CD) algorithm must be reset each time a (not necessarily optimal-arm) change is detected.  

We deeply appreciate your thoughtful feedback, which has been invaluable in refining and improving our paper. We sincerely hope the reviewers can see the merits in devising a minimalist approach and rigorously proving that this scheme can perform near optimally with extremely low complexity. Thank you for your time and effort.
</content>
</thread_object>

</thread>


Metareview:
metareview:
There are various concerns raised about the novelty and relevance of the setting. In my opinion these concerns are of minor relevance. However, the more serious issue is the comparison to MASTER. A lack of novelty is not that important if there are clear cut advantages to new methods. However, in this paper the improvement shows only in experiments and not in the regret or complexity analyses. I believe that more is needed and that the paper needs to improve on that front to make it publishable in a top conference.