論文の概要: Improved Multi-Dimensional Forecasting for Swap Regret
- arxiv url: http://arxiv.org/abs/2606.29533v1
- Date: Sun, 28 Jun 2026 17:57:40 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-06-30 18:07:15.952708
- Title: Improved Multi-Dimensional Forecasting for Swap Regret
- Title（参考訳）: スワップレグレストのための多次元予測の改良
- Abstract要約: 目的不明な下流エージェントの任意の数の予測問題について検討する。
サブリニアスワップを同時に保証する単一予測器を探している。
任意の$d$に対して、$tildeO(dsqrtkT)$ swap regretを保証する予測アルゴリズムを提供します。
- 参考スコア（独自算出の注目度）: 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.
- Abstract（参考訳）: 本研究では,予測者の予測に最もよく反応する,未知の目的を持つ下流エージェントの任意の数の予測問題について検討する。
サブリニアスワップを同時に保証する単一予測器を探している。
2次元の結果空間に対して、$\tilde{O}(\sqrt{kT})$が$k$アクションを持つ下流エージェントに対する後悔をスワップする多項式時間アルゴリズムを与える。
これは、既知の$\tilde{O}(kT^{5/8})$よりも改善され、この設定で前のアルゴリズムの$T$ランタイムの指数関数を避ける。
我々のアルゴリズムは、他の低次元環境に優しく拡張され、$\tilde{O}(\sqrt{T})$下流スワップ後悔を保ちながら、後悔境界における$k$の指数とランニング時間における$T$の指数はどちらも次元的に増大する。
任意の次元の$d$に対して、予測アルゴリズムは$\tilde{O}(d\sqrt{kT})$スワップ後悔を保証する。
これは、$\tilde{O}(T^{2/3})$依存性を持ち、追加の振る舞い仮定を必要とする以前の高次元保証を改善する。
関連論文リスト
- Efficient Online Inverse Optimization with $O(d)$ Regret [26.77597743186513]
オンライン逆線形最適化のための決定論的アルゴリズムを,残差$O(d)$,地平線一様,ラウンド毎の$O(d2)$時間で提供する。
この順序の境界は最近Dewasurendraによって得られたが、全てのスケールでカバーを列挙する不適切な規則により、1ラウンド当たり$T(d)の費用がかかる。
論文 参考訳（メタデータ） (2026-09-11T18:55:31Z) - Asymptotically Optimal Regret for Reinforcement Learning without Horizon Dependence [54.59847568544922]
有限水平時間同質なマルコフ決定過程に対して、$A$状態、$A$アクション、hoighty $H$、および1ドルで有界なトラジェクティブ当たりの合計報酬について、地平自由な後悔について検討する。
失敗確率$$K$はエピソード数で$tilde O(sqrtSAK+S3K)$ hides $mathsfpolyである。
論文 参考訳（メタデータ） (2026-07-22T07:42:19Z) - A Reduction from Delayed to Immediate Feedback for Online Convex Optimization with Improved Guarantees [58.59385794080679]
本稿では,後悔を遅延非依存の学習項と遅延誘発のドリフト項に分解する連続時間モデルを提案する。
バンディット凸最適化では,最先端の1次数に適合する遅延依存項を用いて,既存の残差境界を大幅に改善する。
論文 参考訳（メタデータ） (2026-02-02T18:17:34Z) - Multi-Objective $\ extit{min-max}$ Online Convex Optimization [4.6838063911731025]
オンライン凸最適化(OCO)では、1つの損失関数列がT$の時間的水平線上で明らかにされる。
本稿では,多目的OCOについて考察する。
期待されている$textitmin-max$ regretが$O(sqrtT log K)$であることを示す。
論文 参考訳（メタデータ） (2025-10-15T13:59:44Z) - Full Swap Regret and Discretized Calibration [18.944031222413294]
構造化正規形式ゲームにおけるスワップ後悔の最小化問題について検討する。
我々は、Emphfullスワップリ後悔の最小化という新しいオンライン学習問題を導入する
また、これらのツールをオンライン予測問題に適用し、校正誤差を補正する。
論文 参考訳（メタデータ） (2025-02-13T13:49:52Z) - Online Inverse Linear Optimization: Efficient Logarithmic-Regret Algorithm, Robustness to Suboptimality, and Lower Bound [25.50155563108198]
ラウンド単位の複雑さが$T$に依存しない最初の対数-回帰法を提案する。
我々の方法は極めて単純であり、オンラインニュートンステップ(ONS)を適切なexp-concave損失関数に適用する。
また、$Omega(n)$ の下限を示し、$O(nln T)$ 境界が $O(ln T)$ 係数まで固であることを示す。
論文 参考訳（メタデータ） (2025-01-24T09:19:15Z) - p-Mean Regret for Stochastic Bandits [52.828710025519996]
単純で統一された UCB ベースのアルゴリズムを導入し、新しい$p$-mean の後悔境界を実現する。
我々の枠組みは、特別な場合として、平均的な累積的後悔とナッシュ後悔の両方を包含する。
論文 参考訳（メタデータ） (2024-12-14T08:38:26Z) - Efficient Frameworks for Generalized Low-Rank Matrix Bandit Problems [61.85150061213987]
一般化線形モデル (GLM) フレームワークを用いて, citelu2021low で提案した一般化低ランク行列帯域問題について検討する。
既存のアルゴリズムの計算不可能性と理論的制約を克服するため,まずG-ESTTフレームワークを提案する。
G-ESTT は $tildeO(sqrt(d_1+d_2)3/2Mr3/2T)$ bound of regret を達成でき、G-ESTS は $tildeO を達成できることを示す。
論文 参考訳（メタデータ） (2024-01-14T14:14:19Z) - Non-stationary Delayed Online Convex Optimization: From Full-information to Bandit Setting [71.82716109461967]
遅延勾配が利用できる全情報ケースに対して Mild-OGD というアルゴリズムを提案する。
ミルド-OGDのダイナミックな後悔は、順番の仮定の下で$O(sqrtbardT(P_T+1))$で自動的に束縛されることを示す。
Mild-OGDのバンディット版も開発し,損失値の遅れのみを考慮に入れた,より困難なケースについて検討した。
論文 参考訳（メタデータ） (2023-05-20T07:54:07Z) - Projection-free Online Exp-concave Optimization [21.30065439295409]
LOOをベースとしたONSスタイルのアルゴリズムを提案する。これは全体$O(T)$コールを使用して,$widetildeO(n2/3T2/3)$でバウンドされた最悪のケースを保証します。
我々のアルゴリズムは、重要かつ確実な低次元データシナリオにおいて最も興味深い。
論文 参考訳（メタデータ） (2023-02-09T18:58:05Z) - Refined Regret for Adversarial MDPs with Linear Function Approximation [50.00022394876222]
我々は,損失関数が約1,300ドル以上のエピソードに対して任意に変化するような,敵対的決定過程(MDP)の学習を検討する。
本稿では,同じ設定で$tildemathcal O(K2/3)$に対する後悔を改善する2つのアルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-01-30T14:37:21Z) - Minimal Expected Regret in Linear Quadratic Control [79.81807680370677]
オンライン学習アルゴリズムを考案し、その期待された後悔を保証します。
当時のこの後悔は、$A$と$B$が未知の場合、$widetildeO((d_u+d_x)sqrtd_xT)$によって上界(i)となる。
論文 参考訳（メタデータ） (2021-09-29T14:07:21Z) - Taking a hint: How to leverage loss predictors in contextual bandits? [63.546913998407405]
我々は,損失予測の助けを借りて,文脈的包帯における学習を研究する。
最適な後悔は$mathcalO(minsqrtT, sqrtmathcalETfrac13)$である。
論文 参考訳（メタデータ） (2020-03-04T07:36:38Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。