A new preprint presents a closed-form solution to the stationary prediction-with-expert-advice partial differential equation in the case of five experts. The solution is split into three regions, with the first two given by the four-expert result plus a single integral term. The paper also characterizes the exact set on which the COMB aggregation strategy is optimal.
This paper studies adversarial multi-armed bandit problems in which the benchmark arm sequence may change up to S times over the course of play, a setting known as switching regret. It reviews and develops regret guarantees of order the square root of (S+1)KT, which prior work showed is achievable when S is known in advance. The work aims to pin down the optimal achievable rate under an oblivious adversary.
A new arXiv paper examines constrained online convex optimization where both constraint values and gradients are observed with noise. The authors introduce an algorithm called LEDGER, which they show achieves O(√T) expected regret and constraint violation under standard feasibility assumptions. The work targets settings with adversarial constraints and conditionally unbiased, finite-variance observations.
A new arXiv paper presents a deterministic algorithm for online inverse linear optimization that attains O(d) regret, a bound that holds uniformly across the time horizon. Each round requires O(d^2) computation time. The result matches a recent bound by Dewasurendra and addresses an open question raised by Gollapudi and colleagues.
A new arXiv preprint addresses a question raised by Attias, Hanneke, and Ramaswami (NeurIPS 2025) about whether randomized learners can provably get by with fewer oracle calls than deterministic ones when a hypothesis class is accessible only through an oracle. Focusing on the instance they singled out, transductive online learning of thresholds over an unknown ordering, the authors establish an exponential separation between deterministic and randomized ERM-oracle complexity, showing randomization can reduce the required number of calls exponentially.
Researchers address online inverse linear optimization, where a learner predicts weights, observes the agent's optimal action, and updates its estimate each round. Their new small-gradient skipping technique achieves constant regret and only a finite number of mistakes for integer linear optimization problems. This improves on prior bounds that left a logarithmic gap between upper and lower regret limits.
A newly posted arXiv paper investigates how online learning methods such as gradient descent, mirror descent, and follow-the-regularized-leader behave when measured against more demanding, action-dependent benchmarks rather than fixed comparison points. Moving past the standard external regret framing, the authors pursue a geometric account of these deviations and derive closed-form expressions for the resulting regret bounds.
A new research paper addresses how to learn the gain, the scale parameter that multiplies the scaled log-likelihood score in score-driven filters, directly online. Rather than fixing this coefficient beforehand, the method treats each admissible gain as selecting a reachable next state given the current state and the realized scaled score. This allows the filter's update step to adapt during operation.