Memory-Constrained No-Regret Learning in Adversarial Bandits
This addresses the problem of efficient learning in adversarial bandits for scenarios with limited memory, being the first work in this specific setting.
The paper tackles the adversarial bandit problem with memory constraints by developing a hierarchical learning policy that uses sublinear memory relative to the number of arms, achieving sublinear regret orders for both weak and shifting regret.
An adversarial bandit problem with memory constraints is studied where only the statistics of a subset of arms can be stored. A hierarchical learning policy that requires only a sublinear order of memory space in terms of the number of arms is developed. Its sublinear regret orders with respect to the time horizon are established for both weak regret and shifting regret. This work appears to be the first on memory-constrained bandit problems under the adversarial setting.