Paper bounds bandit regret when delayed rewards omit the round
Balanced Historical Optimism controls delay cost without optimal-arm reports; minimax regret is linear at c=1.
Stories per day · 30 days
3 RSS
Relatedonline-learning2adversarial-learning1corruption1decision-making1delayed-feedback1differential-privacy1expert-advice1linear-bandits1multi-armed-bandits1optimization1predict-then-optimize1reinforcement-learning1
10 stories, newest first · one card per story
Stories tagged #regret-bounds
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.
Paper compares predict-then-optimize and generate-then-optimize decisions
Regret bounds show smoothness can offset generate-then-optimize's extra dimensions, while nonnegative-weight methods face a smoothness limit.
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.
Accelerating Linear Bandits with Persistent Candidate Sets
PC-LinUCB keeps a small persistent action set so linear bandits avoid scoring every arm each round.
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.
Minimax Optimal Regret for Causal Logistic Bandits with Counterfactual Fairness
The paper proves matching minimax regret bounds for causal logistic bandits under counterfactual fairness.
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.
Near-Optimal Reinforcement Learning with Multi-Step Transition Lookahead
Theorists prove multi-step lookahead RL planning is NP-hard for every fixed rational discount factor yet give a randomized polynomial-time approximation scheme.