Tag
This paper resolves an open problem by showing that a single algorithm achieves optimal switching regret for every S against an oblivious adversary in multi-armed bandits.
This paper proves that Thompson sampling achieves polynomial regret for non-monotone convex ridge bandits, showing that monotonicity is not necessary, with a new regret bound of Õ(d^{9/2} √n).
This paper proposes algorithms for adaptively routing prompts to LLM experts in an online setting with limited feedback, formulated as a bandit problem to minimize regret and maximize response quality.
This paper formulates the adaptive routing of prompts to large language model experts as a contextual bandit problem with limited feedback, proposing algorithms that achieve sublinear regret and demonstrate efficient learning of high-quality routing strategies.
This paper proposes Absolute Thompson Sampling (ATS), a modification of Thompson Sampling that ensures optimism in expectation by using absolute exploration noise, enabling a simpler UCB-style regret analysis while maintaining computational efficiency. It achieves regret matching existing TS bounds, and introduces an ensemble variant that converges to UCB behavior.
Proposes GraphDR-LinUCB, a method for contextual bandits with graph-structured arms that projects features onto the graph's low-frequency spectral subspace. Achieves the first regret bound for spectral-projection-based contextual bandits and demonstrates 15x regret reduction on real datasets over full-dimensional LinUCB.
This paper proposes a constrained stochastic bandit algorithm for online selection of large language models under time-varying task demand and heterogeneous accuracy, latency, and cost profiles, with theoretical guarantees on regret and constraint violations.