Confidence-Budget Matching for Sequential Budgeted Learning
This work tackles the problem of limited feedback in sequential decision-making for applications like recommendation systems, where excessive querying annoys users, by introducing a principled querying strategy.
This paper addresses sequential decision-making problems with a hard limit on reward queries, such as multi-armed bandits, linear bandits, and reinforcement learning. The authors propose the Confidence-Budget Matching (CBM) principle, which queries rewards when confidence intervals are wider than the inverse square root of the available budget, demonstrating good performance even with adversarial contexts, initial states, and budgets.
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.