Reproduce “The Sample Complexity of Multiclass and Sparse Contextual 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
Liad Erez, Fan Chen, Alon Cohen, Tomer Koren, Yishay Mansour, Shay Moran, Alexander Rakhlin
The paper establishes a high-probability PAC sample-complexity bound for stochastic contextual bandits with sparse rewards. It uses sparsity to guide exploration and reduce variance when estimating policy values. After \widetilde O(((s/\varepsilon^2)+(|A|/\varepsilon))\log(|\Pi|/\delta)) rounds, it returns a policy within \varepsilon of the best in \Pi with probability at least 1-\delta. This is minimax optimal up to logarithmic factors; the action-count term remains.
Summary by alphaXiv.
Tip: change arxiv.org to autoarxiv.org in any arXiv abstract link to open the paper here.