No open-access location is known for this record yet.
No open-access location is known for this record yet.
The multi-armed bandit (MAB) problem features the classical tradeoff between exploration and exploitation. The input specifies several stochastic arms which evolve with each pull, and the goal is to maximize the expected reward after a fixed budget of pulls. The celebrated work of Gittins et al., surveyed in [8], presumes a condition on the arms called the martingale assumption. In [9], A. Gupta et al. obtained an LP-based -approximation for the problem with the martingale assumption removed. We improve the algorithm to a -approximation, with simpler analysis. Our algorithm also generalizes to the case of MAB superprocesses with (stochastic) multi-period actions. This generalization captures the framework introduced by Guha and Munagala in [11], and yields new results for their budgeted learning problems.
Loading…
Stored only when both papers are in the corpus — 26 citations exist upstream.
Imported from OpenAlex (CC0) — nothing here is generated.