論文の概要: Predict to Minimize Swap Regret for All Payoff-Bounded Tasks
- arxiv url: http://arxiv.org/abs/2404.13503v1
- Date: Sun, 21 Apr 2024 01:53:20 GMT
- ステータス: 処理完了
- システム内更新日: 2024-04-23 18:40:56.627057
- Title: Predict to Minimize Swap Regret for All Payoff-Bounded Tasks
- Title(参考訳): すべての支払バウンドタスクに対するスワップレグレットの最小化予測
- Authors: Lunjia Hu, Yifan Wu,
- Abstract要約: バイナリイベントの予測の最大スワップレグレット(MSR)について検討する。
我々は、$O(TlogT)$ expected MSRを保証する効率的なランダム化予測アルゴリズムを提案する。
- 参考スコア(独自算出の注目度): 15.793486463552144
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: A sequence of predictions is calibrated if and only if it induces no swap regret to all down-stream decision tasks. We study the Maximum Swap Regret (MSR) of predictions for binary events: the swap regret maximized over all downstream tasks with bounded payoffs. Previously, the best online prediction algorithm for minimizing MSR is obtained by minimizing the K1 calibration error, which upper bounds MSR up to a constant factor. However, recent work (Qiao and Valiant, 2021) gives an ${\Omega}(T^{0.528})$ lower bound for the worst-case expected K1 calibration error incurred by any randomized algorithm in T rounds, presenting a barrier to achieving better rates for MSR. Several relaxations of MSR have been considered to overcome this barrier, via external regret (Kleinberg et al., 2023) and regret bounds depending polynomially on the number of actions in downstream tasks (Noarov et al., 2023; Roth and Shi, 2024). We show that the barrier can be surpassed without any relaxations: we give an efficient randomized prediction algorithm that guarantees $O(TlogT)$ expected MSR. We also discuss the economic utility of calibration by viewing MSR as a decision-theoretic calibration error metric and study its relationship to existing metrics.
- Abstract(参考訳): 一連の予測がキャリブレーションされるのは、下流のすべての決定タスクに対してスワップ後悔を誘発しない場合に限られる。
本稿では,バイナリイベントの予測の最大スワップレグレット(MSR)について検討する。
これまで、MSRを最小化するための最良のオンライン予測アルゴリズムは、MSRの上限であるK1校正誤差を一定要素まで最小化することで得られる。
しかし、最近の研究 (Qiao and Valiant, 2021) は、Tラウンドにおける任意のランダム化アルゴリズムによって生じる最悪のケース予測K1キャリブレーション誤差に対して${\Omega}(T^{0.528})$低いバウンドを与え、MSRのより良いレートを達成するための障壁を提示している。
MSRのいくつかの緩和はこの障壁を克服すると考えられており、外部の後悔(Kleinberg et al , 2023)と、下流のタスクの作用数(Noarov et al , 2023; Roth and Shi, 2024)に多項式的に依存する後悔の限界を通じてである。
我々は、この障壁を緩和することなく超過することができることを示す:我々は、$O(TlogT)$期待のMSRを保証する効率的なランダム化予測アルゴリズムを提供する。
また、MSRを決定論的キャリブレーション誤差指標とみなし、キャリブレーションの経済的有用性についても検討し、既存の指標との関係について検討する。
関連論文リスト
- Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic
Shortest Path [80.60592344361073]
線形混合遷移カーネルを用いた最短経路(SSP)問題について検討する。
エージェントは繰り返し環境と対話し、累積コストを最小化しながら特定の目標状態に到達する。
既存の作業は、イテレーションコスト関数の厳密な下限や、最適ポリシーに対する期待長の上限を仮定することが多い。
論文 参考訳(メタデータ) (2024-02-14T07:52:00Z) - $(\epsilon, u)$-Adaptive Regret Minimization in Heavy-Tailed Bandits [29.966828248335972]
我々は,学習者に対して,$epsilon$と$u$が不明な場合に,後悔の最小化問題を調査する。
AdaR-UCBは、適応しない重みを帯びたケースとほぼ一致した後悔の保証を享受する最初のアルゴリズムである。
論文 参考訳(メタデータ) (2023-10-04T17:11:15Z) - U-Calibration: Forecasting for an Unknown Agent [29.3181385170725]
単一のスコアリングルールに対する予測を最適化することは、すべてのエージェントに対して低い後悔を保証できないことを示す。
予測列の最大後悔度に匹敵するU校正と呼ばれる予測を評価するための新しい指標を提案する。
論文 参考訳(メタデータ) (2023-06-30T23:05:26Z) - Minimum-Risk Recalibration of Classifiers [9.31067660373791]
平均二乗誤差分解の枠組みにおいて,最小リスク再校正の概念を導入する。
校正分類器の転送には,スクラッチから再校正するのに比べて,ターゲットサンプルが著しく少ないことが示されている。
論文 参考訳(メタデータ) (2023-05-18T11:27:02Z) - Variance-Dependent Regret Bounds for Linear Bandits and Reinforcement
Learning: Adaptivity and Computational Efficiency [90.40062452292091]
本稿では,不整合雑音を持つ線形帯域に対する計算効率のよい最初のアルゴリズムを提案する。
我々のアルゴリズムは未知のノイズの分散に適応し、$tildeO(d sqrtsum_k = 1K sigma_k2 + d)$ regretを達成する。
また、強化学習において、線形混合マルコフ決定過程(MDP)に対する分散適応アルゴリズムを提案する。
論文 参考訳(メタデータ) (2023-02-21T00:17:24Z) - Autoregressive Bandits [58.46584210388307]
本稿では,オンライン学習環境であるAutoregressive Banditsを提案する。
報酬プロセスの軽微な仮定の下では、最適ポリシーを便利に計算できることが示される。
次に、新しい楽観的後悔最小化アルゴリズム、すなわちAutoRegressive Upper Confidence Bound (AR-UCB)を考案し、$widetildemathcalO left( frac(k+1)3/2sqrtnT (1-G)のサブ線形後悔を被る。
論文 参考訳(メタデータ) (2022-12-12T21:37:36Z) - Corruption-Robust Algorithms with Uncertainty Weighting for Nonlinear
Contextual Bandits and Markov Decision Processes [59.61248760134937]
本稿では,$tildeO(sqrtT+zeta)$を後悔するアルゴリズムを提案する。
提案アルゴリズムは、最近開発された線形文脈帯域からの不確実性重み付き最小二乗回帰に依存する。
本稿では,提案アルゴリズムをエピソディックなMDP設定に一般化し,まず汚職レベル$zeta$への付加的依存を実現する。
論文 参考訳(メタデータ) (2022-12-12T15:04:56Z) - Can Q-Learning be Improved with Advice? [27.24260290748049]
本稿では,マルコフ決定過程(MDP)のオンライン学習において,後悔に対する最悪の下限を回避できるかどうかを論じる。
最適$Q$-値関数の予測が蒸留と呼ばれる合理的に弱い条件を満たす場合、状態-作用対の集合を、その予測が極端に不正確な状態-作用対の集合に置き換えることで、後悔境界を改善することができることを示す。
私たちの研究は、キャッシュやスケジューリングといった単純なオンライン問題に重点を置いていた予測を伴うアルゴリズムに関する最近の研究を、強化学習のより複雑で一般的な問題へと拡張しています。
論文 参考訳(メタデータ) (2021-10-25T15:44:20Z) - Online nonparametric regression with Sobolev kernels [99.12817345416846]
我々は、ソボレフ空間のクラス上の後悔の上限を$W_pbeta(mathcalX)$, $pgeq 2, beta>fracdp$ とする。
上界は minimax regret analysis で支えられ、$beta> fracd2$ または $p=infty$ の場合、これらの値は(本質的に)最適である。
論文 参考訳(メタデータ) (2021-02-06T15:05:14Z) - Fast Rates for the Regret of Offline Reinforcement Learning [69.23654172273085]
無限水平割引決定プロセス(MDP)における固定行動ポリシーによって生成されたオフラインデータからの強化学習の後悔について検討する。
最適品質関数 $Q*$ に対する任意の推定が与えられたとき、定義するポリシーの後悔は、$Q*$-estimate の点収束率の指数によって与えられる速度で収束することを示す。
論文 参考訳(メタデータ) (2021-01-31T16:17:56Z) - Optimal Algorithms for Stochastic Multi-Armed Bandits with Heavy Tailed
Rewards [24.983866845065926]
我々は、重い尾の報酬を持つマルチアームのバンディットを考えており、そのp$-thのモーメントは、定数$nu_p$が1pleq2$である。
本稿では,従来の情報として$nu_p$を必要としない新しいロバストな推定器を提案する。
提案した推定器の誤差確率は指数関数的に高速に減衰することを示す。
論文 参考訳(メタデータ) (2020-10-24T10:44:02Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。