Research map / Bandits and online learning / Online convex optimization and games
Looking Through the Mirror: Minimax-Optimal Regularized Regrets in Online Learning and Bandits
Junghyun Lee, Yujun Kim, Chulhee Yun, Se-Young Yun
Read the paperCheck your idea against 137,217 papers
AI-extracted summary. Written by AI from the paper's abstract only. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Establishes minimax-optimal regularized regret bounds for online learning and bandits with strongly convex regularizers, under full-information and bandit feedback.
Problem
Regularized regret minimization over the simplex with adversarial rewards and a known strongly-convex regularizer, under full-information and bandit feedback; the minimax regularized regret was not established for a broad regularizer class.
Approach
Derives minimax-optimal regularized regret for a broad class of regularizers that are relatively (strongly) convex with respect to a reference, covering both full-information and bandit settings.
Experimental setup
Metrics: regularized regret
Builds on: mirror descent follow the regularized leader
Closest papers by meaning
- From Average Sensitivity to Small-Loss Regret Bounds under Random-Order Model (NeurIPS 2026 · similarity 0.91)
- Provably Efficient Regularized Online RLHF with Generalized Bilinear Preferences (NeurIPS 2026 · similarity 0.91)
- Regret Bounds for Adversarial Contextual Bandits with General Function Approximation and Delayed Feedback (NeurIPS 2025 · similarity 0.90)
- Near-Optimal Regret in Adversarial Kernel Bandits (NeurIPS 2026 · similarity 0.90)
- No-Regret is not enough! Bandits with General Constraints through Adaptive Regret Minimization (ICML 2025 · similarity 0.90)
- Improved Regret and Contextual Linear Extension for Pandora's Box and Prophet Inequality (NeurIPS 2025 · similarity 0.90)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.
