Confidence-Budget Matching for Sequential Budgeted Learning
  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.
