Tag
该论文首次研究了可复制的对抗性多臂老虎机(replicable dueling bandits)问题,设计了在共享内部随机性下保证每次运行选择一致比较对的算法,并在多种随机传递性假设下证明了次线性后悔界,实验在合成数据和语言模型偏好上验证了可复制性。
该论文研究多智能体bandit学习中探索信号泄露带来的安全隐患,提出deceptive bandit learning(DBL)动力学,证明对手可通过耦合自身探索注入外部性使系统收敛到新的deceptive Nash equilibrium(DNE),并保持最优收敛速率且放宽了二阶光滑性假设。
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.