Improved Multi-Dimensional Forecasting for Swap Regret

• URL: http://arxiv.org/abs/2606.29533v1
• Date: Sun, 28 Jun 2026 17:57:40 GMT
• Title: Improved Multi-Dimensional Forecasting for Swap Regret
• Abstract summary: We study the problem of forecasting for an arbitrary number of downstream agents with unknown objectives.<n>We seek a single forecaster that guarantees sublinear swap regret for all downstream agents simultaneously.<n>For arbitrary $d$, we give a forecasting algorithm that guarantees $tildeO(dsqrtkT)$ swap regret.
• Score: 2.252575881846716
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study the problem of forecasting for an arbitrary number of downstream agents with unknown objectives, each of whom best responds to the forecaster's predictions. We seek a single forecaster that guarantees sublinear swap regret for all downstream agents simultaneously. For two-dimensional outcome spaces, we give a polynomial time algorithm that guarantees $\tilde{O}(\sqrt{kT})$ swap regret for any downstream agent with $k$ actions. This improves over the previously known bound of $\tilde{O}(kT^{5/8})$ and avoids the exponential in $T$ runtime of prior algorithms in this setting. Our algorithm extends nicely to other low dimensional environments, retaining $\tilde{O}(\sqrt{T})$ downstream swap regret while the exponent of $k$ in the regret bound and the exponent of $T$ in the running time both grow with dimension. For arbitrary dimension $d$, we give a forecasting algorithm that guarantees $\tilde{O}(d\sqrt{kT})$ swap regret, assuming the forecaster knows an upper bound $k$ on the number of actions available to any downstream agent, albeit with a much longer runtime. This improves upon previous high dimensional guarantees that had $\tilde{O}(T^{2/3})$ dependence and required additional behavioral assumptions.

Related papers

• Efficient Online Inverse Optimization with $O(d)$ Regret [26.77597743186513]
  We give a deterministic algorithm for online inverse linear optimization with regret $O(d)$, uniform in the horizon and $O(d2)$ time per round.<n>A bound of this order was obtained recently by Dewasurendra, but by an improper rule that enumerates covers at every scale and costs $T(d)$ a round.
  arXiv  Detail & Related papers  (2026-09-11T18:55:31Z)
• Asymptotically Optimal Regret for Reinforcement Learning without Horizon Dependence [54.59847568544922]
  We study horizon-free regret for finite-horizon time-homogeneous Markov decision processes with $A$ states, $A$ actions, horizon $H$, and per-trajectory total reward bounded by $1$.<n>We prove a regret upper bound [tilde O(sqrtSAK+S8A3)] with failure probability $$, where $K$ is the number of episodes and $tilde O(sqrtSAK+S3K)$ hides $mathsfpoly
  arXiv  Detail & Related papers  (2026-07-22T07:42:19Z)
• A Reduction from Delayed to Immediate Feedback for Online Convex Optimization with Improved Guarantees [58.59385794080679]
  We introduce a continuous-time model under which regret decomposes into a delay-independent learning term and a delay-induced drift term.<n>For bandit convex optimization, we significantly improve existing regret bounds, with delay-dependent terms matching state-of-the-art first-order rates.
  arXiv  Detail & Related papers  (2026-02-02T18:17:34Z)
• Multi-Objective $\ extit{min-max}$ Online Convex Optimization [4.6838063911731025]
  In online convex optimization (OCO), a single loss function sequence is revealed over a time horizon of $T$.<n>In this paper, we consider multi-objective OCO, where there are $K$ distinct loss function sequences.<n>We show that an expected $textitmin-max$ regret is $O(sqrtT log K)$.
  arXiv  Detail & Related papers  (2025-10-15T13:59:44Z)
• Full Swap Regret and Discretized Calibration [18.944031222413294]
  We study the problem of minimizing swap regret in structured normal-form games.<n>We introduce a new online learning problem we call emphfull swap regret minimization<n>We also apply these tools to the problem of online forecasting to calibration error.
  arXiv  Detail & Related papers  (2025-02-13T13:49:52Z)
• Online Inverse Linear Optimization: Efficient Logarithmic-Regret Algorithm, Robustness to Suboptimality, and Lower Bound [25.50155563108198]
  We present the first logarithmic-regret method whose per-round complexity is independent of $T$.<n>Our method is strikingly simple: it applies the online Newton step (ONS) to appropriate exp-concave loss functions.<n>We also present a lower bound of $Omega(n)$, showing that the $O(nln T)$ bound is tight up to an $O(ln T)$ factor.
  arXiv  Detail & Related papers  (2025-01-24T09:19:15Z)
• p-Mean Regret for Stochastic Bandits [52.828710025519996]
  We introduce a simple, unified UCB-based algorithm that achieves novel $p$-mean regret bounds.<n>Our framework encompasses both average cumulative regret and Nash regret as special cases.
  arXiv  Detail & Related papers  (2024-12-14T08:38:26Z)
• Efficient Frameworks for Generalized Low-Rank Matrix Bandit Problems [61.85150061213987]
  We study the generalized low-rank matrix bandit problem, proposed in citelu2021low under the Generalized Linear Model (GLM) framework. To overcome the computational infeasibility and theoretical restrain of existing algorithms, we first propose the G-ESTT framework. We show that G-ESTT can achieve the $tildeO(sqrt(d_1+d_2)3/2Mr3/2T)$ bound of regret while G-ESTS can achineve the $tildeO
  arXiv  Detail & Related papers  (2024-01-14T14:14:19Z)
• Non-stationary Delayed Online Convex Optimization: From Full-information to Bandit Setting [71.82716109461967]
  We propose an algorithm called Mild-OGD for the full-information case, where delayed gradients are available.<n>We show that the dynamic regret of Mild-OGD can be automatically bounded by $O(sqrtbardT(P_T+1))$ under the in-order assumption.<n>We also develop a bandit variant of Mild-OGD for a more challenging case with only delayed loss values.
  arXiv  Detail & Related papers  (2023-05-20T07:54:07Z)
• Projection-free Online Exp-concave Optimization [21.30065439295409]
  We present an LOO-based ONS-style algorithm, which using overall $O(T)$ calls to a LOO, guarantees in worst case regret bounded by $widetildeO(n2/3T2/3)$. Our algorithm is most interesting in an important and plausible low-dimensional data scenario.
  arXiv  Detail & Related papers  (2023-02-09T18:58:05Z)
• Refined Regret for Adversarial MDPs with Linear Function Approximation [50.00022394876222]
  We consider learning in an adversarial Decision Process (MDP) where the loss functions can change arbitrarily over $K$ episodes. This paper provides two algorithms that improve the regret to $tildemathcal O(K2/3)$ in the same setting.
  arXiv  Detail & Related papers  (2023-01-30T14:37:21Z)
• Minimal Expected Regret in Linear Quadratic Control [79.81807680370677]
  We devise an online learning algorithm and provide guarantees on its expected regret. This regret at time $T$ is upper bounded (i) by $widetildeO((d_u+d_x)sqrtd_xT)$ when $A$ and $B$ are unknown.
  arXiv  Detail & Related papers  (2021-09-29T14:07:21Z)
• Taking a hint: How to leverage loss predictors in contextual bandits? [63.546913998407405]
  We study learning in contextual bandits with the help of loss predictors. We show that the optimal regret is $mathcalO(minsqrtT, sqrtmathcalETfrac13)$ when $mathcalE$ is known.
  arXiv  Detail & Related papers  (2020-03-04T07:36:38Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.