Reproduce “Towards Efficient and Optimal Covariance-Adaptive Algorithms for Combinatorial Semi-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
Julien Zhou, Pierre Gaillard, Thibaud Rahier, Houssam Zenati, Julyan Arbel
OLS-UCB-C and COS-V learn bundle choices in combinatorial semi-bandits by using item-level feedback; OLS-UCB-C estimates item means and covariances online to guide optimistic action scores, while COS-V uses estimated variances alone. The authors prove OLS-UCB-C has a gap-free regret bound sensitive to positive covariance and action structure. Their lower bound matches its structure up to logarithmic factors for specified instances.
Key insights
- Optimal covariance-adaptive regret, specifically O(√T) gap-free performance, can be achieved for both deterministic and sampling-based combinatorial semi-bandits through careful construction of confidence bounds or biased sampling distributions.
- The utility of semi-bandit feedback extends beyond scenarios where the action set is exponentially larger than the base item set, providing consistent advantages even when the number of actions is comparable to or less than the number of items.
- A novel gap-free lower bound for the pseudo-regret explicitly incorporates the problem's structure and the covariance matrix, serving as a benchmark for algorithmic optimality in this setting.
Summary by alphaXiv.
Tip: change arxiv.org to autoarxiv.org in any arXiv abstract link to open the paper here.