CRW-FTRL matches corruption-free regret under strong bandit corruption
For K actions in d dimensions it reaches Õ(√(dT log K)+dC) regret and settles the compact-set rate.
Stories per day · 30 days
Relatedregret-bounds2adversarial-learning1approachability1classifiers1constrained-optimization1corruption1differential-privacy1error-control1expert-advice1fairness1gradient-equilibrium1human-oversight1language-agents1linear-bandits1llm1memory1multi-armed-bandit1no-regret1
17 stories, newest first · one card per story
Stories tagged #online-learning
Paper characterizes constrained gradient equilibrium under local adversaries
Constrained gradient equilibrium can fail under simple constraints unless the adversary is locally restricted.
Selective auditing bounds unaudited AI errors while cutting expert reviews
A family of algorithms includes one that asymptotically attains the best auditing rate for adversarial and i.i.d. streams.
Private expert prediction reaches square-root-of-best-loss regret
For constant privacy and oblivious inputs, the bound matches the non-private lower bound up to polylog factors.
Warm-Start UCB personalizes memory gating for language agents
The policy learns which facts to keep from delayed retrieval feedback and beat baselines across memory budgets.
Bayesian Learning to Select Fair Classifiers
Researchers use Thompson Sampling to pick classifiers that balance accuracy and subgroup fairness online.
Accelerating Linear Bandits with Persistent Candidate Sets
PC-LinUCB keeps a small persistent action set so linear bandits avoid scoring every arm each round.
Recurrent Harness for Agentic Continual Learning
ReHarness revises retrieved agent reflections after each task, improving continual learning across three benchmarks and three backbones.
Oracle-Efficient and Parameter-Free Agnostic Smoothed Online Learning
A parameter-free Follow-The-Perturbed-Leader method gets near-optimal agnostic smoothed online regret without knowing the base measure.
Linear Bandits under Exact Sliding-Window Constraints
A rare-switching bandit algorithm keeps exact sliding-window feasibility with near-optimal regret.
Optimal and Efficient Online Inverse Optimization
A deterministic polynomial-time algorithm achieves optimal O(sqrt d) regret for online inverse linear optimization.
Private online learning and prediction for Littlestone classes
Differentially private online learning of Littlestone classes needs more mistakes than private prediction.
Minimax Optimal Regret for Causal Logistic Bandits with Counterfactual Fairness
The paper proves matching minimax regret bounds for causal logistic bandits under counterfactual fairness.
Online Learning via Learned Latent Bayesian Tracking
AURA learns a latent state space so deep models adapt online via Kalman filtering under distribution shift.
Multiplicative Optimism for Constant Regret in Games
Multiplicatively Optimistic Regret Matching gives near-constant external regret in general-sum games under self-play.
Minimax-Optimal Online Contract Design with Unrestricted Bounded Contracts
The paper proves minimax-optimal regret of order T^(m/(m+1)) for repeated online contract design with unrestricted bounded contracts and arbitrary agent action spaces.
Online Learning with LLM Experts from Limited Feedback
Paper proposes bandit algorithms for adaptively routing prompts to LLM experts, minimizing regret under limited feedback budgets.