Planning and learning strategies optimize delayed reward decisions under budgets
Planned Restlessness: Delayed Meta Bandits with Budgets
Machine LearningData Structures and Algorithms
Summary
This paper studies a way to make smart choices when trying different options repeatedly over time, with limits on how many tries or resources are allowed each round. The authors look at situations where feedback about the choices comes back late, not immediately, which makes deciding more complicated. They create a mathematical framework that helps plan which options to try and when, balancing learning about them and getting rewards. Their approach also handles constraints like budgets and delayed information, and they prove theoretical guarantees for how well their strategies work over many rounds.
What this means in practice
- •For online advertising teams: Optimize ad selection strategies with delayed user response and spending caps per campaign period.
- •For wireless network schedulers: Schedule transmissions with delayed acknowledgements under strict per-period resource limits to improve learning and performance.
Authors
Sudipto Guha
Abstract
We study episodic finite-horizon Bayesian bandits, or meta-bandits, with independent arms. Each episode draws fresh arm qualities from unknown recurring priors. Observations arrive after known delays, and plays obey hard per-episode caps and total budgets. A play earns reward and informs both the current quality and the recurring prior: the learner must explore, use, and generalize. We formulate a common planning optimization over learning trajectories. Its LP relaxation values experiments through current reward, resource consumption and continuation: the value of future decisions from the learning state produced. Dual prices separate the arms into local programs and certify every admissible policy, including hierarchical Thompson sampling. Execution enforces the hard constraints while preserving the promised learning transitions or accounting for their loss. The framework also represents risk-sensitive objectives and prices purchased observations and buyout options. Delayed reports create planned restlessness: an arm's information changes while it is not played, through reports of its own earlier plays arriving on a known calendar. For stationary priors, finite reward alphabets, bounded report lag and nonbinding budgets, posterior sampling over the recurring priors bounds the price of not knowing them by $O(\sqrt{N})$ over $N$ episodes, with other parameters fixed. For one undelayed $T$-step episode with arms capped at $T/X$ plays each, we obtain the LP-relative approximation factor $1+(2πX)^{-1/2}+O(X^{-1})$, improving previous factors, with a matching lower bound for the leading term.