Crush Optimism with Pessimism: Structured Bandits Beyond Asymptotic Optimality
We study stochastic structured bandits for minimizing regret. The fact that the popular optimistic algorithms do not achieve the asymptotic instance-dependent regret optimality (asymptotic optimality for short) has recently alluded researchers. On the other hand, it is known that one can achieve bounded regret (i.e., does not grow indefinitely with $n$) in certain instances. Unfortunately, existing asymptotically optimal algorithms rely on forced sampling that introduces an $\omega(1)$ term w.r.t. the time horizon $n$ in their regret, failing to adapt to the "easiness" of the instance. In this paper, we focus on the finite hypothesis case and ask if one can achieve the asymptotic optimality while enjoying bounded regret whenever possible. We provide a positive answer by introducing a new algorithm called CRush Optimism with Pessimism (CROP) that eliminates optimistic hypotheses by pulling the informative arms indicated by a pessimistic hypothesis. Our finite-time analysis shows that CROP $(i)$ achieves a constant-factor asymptotic optimality and, thanks to the forced-exploration-free design, $(ii)$ adapts to bounded regret, and $(iii)$ its regret bound scales not with $K$ but with an effective number of arms $K_\psi$ that we introduce. We also discuss a problem class where CROP can be exponentially better than existing algorithms in \textit{nonasymptotic} regimes. This problem class also reveals a surprising fact that even a clairvoyant oracle who plays according to the asymptotically optimal arm pull scheme may suffer a linear worst-case regret.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Exploring Pessimism and Optimism Dynamics in Deep Reinforcement Learning
Off-policy actor-critic algorithms have shown promise in deep reinforcement learning for continuous control tasks. Their success largely stems from leveraging pessimistic state-action value function updates, which effect…
continuous-controlContinuous ControlDeep Reinforcement Learningreinforcement-learning+1Detecting Optimism in Tweets using Knowledge Distillation and Linguistic Analysis of Optimism
Finding the polarity of feelings in texts is a far-reaching task. Whilst the field of natural language processing has established sentiment analysis as an alluring problem, many feelings are left uncharted. In this study…
Hate Speech DetectionKnowledge DistillationSentiment AnalysisDROP: Distributional and Regular Optimism and Pessimism for Reinforcement Learning
In reinforcement learning (RL), temporal difference (TD) error is known to be related to the firing rate of dopamine neurons. It has been observed that each dopamine neuron does not behave uniformly, but each responds to…
Ensemble Learningreinforcement-learningReinforcement LearningReinforcement Learning (RL)Exploring Optimism and Pessimism in Twitter Using Deep Learning
Identifying optimistic and pessimistic viewpoints and users from Twitter is useful for providing better social support to those who need such support, and for minimizing the negative influence among users and maximizing …
Deep LearningAnxiety for the pandemic and trust in financial markets
The COVID-19 pandemic has generated disruptive changes in many fields. Here we focus on the relationship between the anxiety felt by people during the pandemic and the trust in the future performance of financial markets…