A new arXiv paper examines how few models are needed in ensemble sampling, a randomized-exploration method for sequential decision problems, while still preserving theoretical regret bounds. Prior results relied on ensembles larger than practical implementations typically use, leaving the minimum viable size unclear. The work analyzes this setting for linear models.
A new arXiv paper studies an online learning problem where a system must repeatedly choose k paths through a network to keep the slowest path's transmission time as low as possible. The authors formalize this as a stochastic semi-bandit problem, where feedback is observed only for the paths actually selected. They propose and analyze algorithms for minimizing the longest path length under uncertainty.
This paper studies adversarial multi-armed bandit problems in which the benchmark arm sequence may change up to S times over the course of play, a setting known as switching regret. It reviews and develops regret guarantees of order the square root of (S+1)KT, which prior work showed is achievable when S is known in advance. The work aims to pin down the optimal achievable rate under an oblivious adversary.
A new arXiv paper studies stochastic linear contextual bandits where the set of available actions can vary arbitrarily, depending on both the unknown parameter and past interactions. The authors prove matching upper and lower bounds on regret that agree up to logarithmic factors, characterizing the problem's minimax rate.
A new arXiv paper studies a bandit setting where a learner may probe up to k of n arms per round and only observes the highest reward among those probed, rather than each individual reward. The authors derive two minimax laws characterizing when probing yields a statistical advantage over standard bandit learning, covering independent stochastic reward models. They also identify limits on what can be learned from this winner-only feedback.
A new arXiv paper analyzes KL-regularized contextual bandits under both reward and preference feedback. The authors show that a greedy sampling approach attains logarithmic regret without an explicit dependence on the eluder dimension. The work covers regret guarantees for the reward-feedback setting and extends the analysis to preference-based feedback.
Researchers introduce a quantity called gap entropy for the best-arm identification problem with independent Gaussian arms, where the goal is to find the highest-mean arm using as few samples as possible at a given confidence level. They show that an algorithm based on this measure comes close to the optimal sample complexity for each individual problem instance. The work is a theoretical contribution posted to arXiv and has not yet been peer reviewed.
A new arXiv paper in machine learning theory settles the gap-entropy conjecture, an open problem in best-arm identification for multi-armed bandits. The proof covers the fixed-confidence setting with independent unit-variance Gaussian arms, means bounded in [0,1], and a single optimal arm. The result confirms that the entropy of suboptimality gaps governs the sample complexity needed to identify the best arm.
A new arXiv paper presents Meta-LinEXP3, an algorithm that brings meta-learning to adversarial linear contextual bandits, a setting where earlier results largely covered only stochastic or non-contextual variants. The method uses an online-within-online framework to transfer knowledge across a sequence of bandit tasks.