Tight Policy Regret Bounds for Improving and Decaying Bandits

Hoda Heidari, Michael J. Kearns, Aaron RothIJCAI 2016 · OpenReview

Abstract: We consider a variant of the well-studied multiarmed bandit problem in which the reward from each action evolves monotonically in the number of times the decision maker chooses to take that action. We are motivated by settings in which we must give a series of homogeneous tasks to a finite set of arms (workers) whose performance may improve (due to learning) or decay (due to loss of interest) with repeated trials. We assume that the arm-dependent rates at which the rewards change are unknown to the decision maker, and propose algorithms with provably optimal policy regret bounds, a much stronger notion than the often-studied external regret. For the case where the rewards are increasing and concave, we give an algorithm whose policy regret is sublinear and has a (provably necessary) dependence on the time required to distinguish the optimal arm from the rest. We illustrate the behavior and performance of this algorithm via simulations. For the decreasing case, we present a simple greedy approach and show that the policy regret of this algorithm is constant and upper bounded by the number of arms.

Introduction

In the classic Multi-Armed Bandit (MAB) problem, a decision-maker seeks to identify the optimal action to maximize cumulative rewards. Traditional models assume rewards are static or drawn from fixed distributions. However, real-world applications like crowdsourcing involve dynamic rewards: a worker's performance may improve through learning or decay due to fatigue. Crucially, in these settings, the reward of an arm depends on its specific pull history.

This paper addresses Policy Regret, a benchmark significantly more challenging than standard external regret. While external regret compares performance against the best single arm in hindsight, policy regret compares the algorithm against the best possible sequence of actions. This distinction is vital in adaptive environments where the optimal strategy might involve switching arms as their rewards evolve.

Methods for Monotonic Rewards

The research categorizes the problem into two distinct monotonic cases: improving and decaying rewards.

Improving (Concave) Rewards

For arms that improve over time, the authors assume a concave reward function, representing diminishing returns. They introduce Algorithm 1 ($\mathcal{A}_1$), which manages a set of candidate arms by calculating optimistic and pessimistic bounds.

Geometric construction of optimistic and pessimistic reward estimates (a) and the distinguishability parameter $\tau$ (b).

As shown in Figure 2(a), the algorithm maintains a Pessimistic Estimate ($f'_k$), the minimum reward if improvement stops, and an Optimistic Estimate ($f''_k$), the maximum potential if current improvement rates persist. Arms are eliminated when their optimistic potential falls below the pessimistic floor of a superior arm. The efficiency of this elimination is tied to the Distinguishability Parameter ($\tau$), illustrated in Figure 2(b), which represents the time required to identify the optimal arm.

Decaying Rewards

Conversely, for arms that only degrade over time, the authors propose Algorithm 2 ($\mathcal{A}_2$), a simple greedy strategy. This algorithm consistently selects the arm that yielded the highest reward in its most recent trial. While seemingly naive, the authors prove that any loss incurred by not exploring is self-limiting, as the rewards of all arms are strictly non-increasing.

Key Results and Empirical Analysis

The theoretical contributions are validated through synthetic simulations using various reward curves, such as power laws and asymptotic functions.

Per-step regret as a function of the time horizon $T$ for various reward functions.

As illustrated in Figure 5, the per-step regret for the improving case decreases as the time horizon $T$ increases, confirming that Algorithm $\mathcal{A}_1$ achieves sublinear policy regret. Specifically, the regret is bounded by $n\tau(T)$, where $n$ is the number of arms. For the decaying case, Algorithm $\mathcal{A}_2$ achieves a remarkable constant policy regret, upper-bounded simply by the number of arms ($n$), regardless of the duration of the game. These bounds are mathematically proven to be "tight," representing the best possible theoretical performance for these bandit classes.

Conclusion and Future Work

This work provides a robust framework for managing bandits with history-dependent rewards. While concavity provides a powerful tool for elimination in improving scenarios, and greedy strategies suffice for decay, several challenges remain. Future research may explore non-concave improvement curves (such as S-curves), U-shaped reward trajectories (learning followed by fatigue), and high-variance stochastic environments where rewards are subject to significant noise.

Summary updated

Abstract

We consider a variant of the well-studied multiarmed bandit problem in which the reward from each action evolves monotonically in the number of times the decision maker chooses to take that action. We are motivated by settings in which we must give a series of homogeneous tasks to a finite set of arms (workers) whose performance may improve (due to learning) or decay (due to loss of interest) with repeated trials. We assume that the arm-dependent rates at which the rewards change are unknown to the decision maker, and propose algorithms with provably optimal policy regret bounds, a much stronger notion than the often-studied external regret. For the case where the rewards are increasing and concave, we give an algorithm whose policy regret is sublinear and has a (provably necessary) dependence on the time required to distinguish the optimal arm from the rest. We illustrate the behavior and performance of this algorithm via simulations. For the decreasing case, we present a simple greedy approach and show that the policy regret of this algorithm is constant and upper bounded by the number of arms.
BibTeX
@inproceedings{heidari2016tight,
  author = {Hoda Heidari and Michael J. Kearns and Aaron Roth},
  title = {{Tight Policy Regret Bounds for Improving and Decaying Bandits}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2016},
  url = {https://openreview.net/forum?id=HyEeHrMdZS},
}
Figure