Confidence-Budget Matching for Sequential Budgeted Learning

Abstract

A core element in decision-making under uncertainty is the feedback on the quality of the performed actions. However, in many applications, such feedback is restricted. For example, in recommendation systems, repeatedly asking the user to provide feedback on the quality of recommendations will annoy them. In this work, we formalize decision-making problems with querying budget, where there is a (possibly time-dependent) hard limit on the number of reward queries allowed. Specifically, we consider multi-armed bandits, linear bandits, and reinforcement learning problems. We start by analyzing the performance of `greedy' algorithms that query a reward whenever they can. We show that in fully stochastic settings, doing so performs surprisingly well, but in the presence of any adversity, this might lead to linear regret. To overcome this issue, we propose the Confidence-Budget Matching (CBM) principle that queries rewards when the confidence intervals are wider than the inverse square root of the available budget. We analyze the performance of CBM based algorithms in different settings and show that they perform well in the presence of adversity in the contexts, initial states, and budgets.

arXiv commentAccepted to ICML 2021

References in corpus (14)

• Analysis of Thompson Sampling for the multi-armed bandit problem
• Thompson Sampling for Contextual Bandits with Linear Payoffs
• Empirical Bernstein Bounds and Sample Variance Penalization
• Contextual Bandit Algorithms with Supervised Learning Guarantees
• Tighter Problem-Dependent Regret Bounds in Reinforcement Learning without Domain Knowledge using Value Function Bounds
• Minimax Regret Bounds for Reinforcement Learning
• Model selection for contextual bandits
• Learning Adversarial MDPs with Bandit Feedback and Unknown Transition
• Is Reinforcement Learning More Difficult Than Bandits? A Near-optimal Algorithm Escaping the Curse of Horizon
• Non-Asymptotic Gap-Dependent Regret Bounds for Tabular MDPs
• Instance-Dependent Complexity of Contextual Bandits and Reinforcement Learning: A Disagreement-Based Perspective
• Tight Lower Bounds for Combinatorial Multi-Armed Bandits
• No-Regret Exploration in Goal-Oriented Reinforcement Learning
• Near-optimal Regret Bounds for Stochastic Shortest Path

Cited by in corpus (1)

• Minimax Regret for Stochastic Shortest Path