Reproduce “Self-Concordant Perturbations for Linear Bandits” on OpenResearch
Turn your favorite coding agents into research agents that review literature, develop hypotheses, and run experiments.
Universal app for Apple silicon and Intel. Requires macOS 11 or later.
About this paper
Lucas Lévy, Jean-Lou Valeau, Arya Akhavan, Patrick Rebeschini
This research from the University of Oxford introduces Self-Concordant FTPL (Sc-Ftpl), a novel algorithm for adversarial linear bandits that employs self-concordant perturbations to achieve an O(d√n ln n) regret bound on the d-dimensional hypercube, matching the minimax optimal rate and improving previous self-concordant methods by a factor of √d. The work also establishes Bandits-Gbpa, a unifying theoretical framework for online linear bandit algorithms.
Key insights
- Properties of self-concordant barriers can be replicated through carefully chosen perturbation distributions within an Ftpl framework, leading to geometrically adaptive exploration.
- The analytical framework for Sc-Ftpl successfully decomposes regret, showing its control by the self-concordance parameter and the cumulative variance of local loss estimators.
- The estimator's local norm variance is a critical factor influencing regret bounds, with a reduction from d² to d for the hypercube directly explaining improved performance.
Summary by alphaXiv.
Tip: change arxiv.org to autoarxiv.org in any arXiv abstract link to open the paper here.