Multi-Armed Bandits with Abstention
This addresses a strategic enhancement in online decision-making for scenarios where abstention is beneficial, though it is incremental to existing bandit frameworks.
The paper tackles the multi-armed bandit problem by adding an abstention option, where the agent can choose to abstain from rewards, and develops algorithms that achieve asymptotic and minimax optimal regret, meeting information-theoretic lower bounds.
We introduce a novel extension of the canonical multi-armed bandit problem that incorporates an additional strategic element: abstention. In this enhanced framework, the agent is not only tasked with selecting an arm at each time step, but also has the option to abstain from accepting the stochastic instantaneous reward before observing it. When opting for abstention, the agent either suffers a fixed regret or gains a guaranteed reward. Given this added layer of complexity, we ask whether we can develop efficient algorithms that are both asymptotically and minimax optimal. We answer this question affirmatively by designing and analyzing algorithms whose regrets meet their corresponding information-theoretic lower bounds. Our results offer valuable quantitative insights into the benefits of the abstention option, laying the groundwork for further exploration in other online decision-making problems with such an option. Numerical results further corroborate our theoretical findings.