{"ID":2847777,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2511.00257","arxiv_id":"2511.00257","title":"A Tight Lower Bound for Non-stochastic Multi-armed Bandits with Expert Advice","abstract":"We determine the minimax optimal expected regret in the classic non-stochastic multi-armed bandit with expert advice problem, by proving a lower bound that matches the upper bound of Kale (2014). The two bounds determine the minimax optimal expected regret to be $Θ\\left( \\sqrt{T K \\log (N/K) } \\right)$, where $K$ is the number of arms, $N$ is the number of experts, and $T$ is the time horizon.","short_abstract":"We determine the minimax optimal expected regret in the classic non-stochastic multi-armed bandit with expert advice problem, by proving a lower bound that matches the upper bound of Kale (2014). The two bounds determine the minimax optimal expected regret to be $Θ\\left( \\sqrt{T K \\log (N/K) } \\right)$, where $K$ is th...","url_abs":"https://arxiv.org/abs/2511.00257","url_pdf":"https://arxiv.org/pdf/2511.00257v1","authors":"[\"Zachary Chase\",\"Shinji Ito\",\"Idan Mehalel\"]","published":"2025-10-31T21:01:53Z","proceeding":"cs.LG","tasks":"[\"cs.LG\",\"stat.ML\"]","methods":"[]","has_code":false}