論文の概要: Rate-Preserving Reductions for Blackwell Approachability

• arxiv url: http://arxiv.org/abs/2406.07585v2
• Date: Wed, 17 Jul 2024 15:28:36 GMT
• ステータス: 処理完了
• システム内更新日: 2024-07-18 21:47:53.655733
• Title: Rate-Preserving Reductions for Blackwell Approachability
• Title（参考訳）: ブラックウェルの接近性に対する保存率低減
• Authors: Christoph Dann, Yishay Mansour, Mehryar Mohri, Jon Schneider, Balasubramanian Sivan,
• Abstract要約: Abernethy et al. (2011) はブラックウェルのアプローチ可能性と非回帰学習が等価であることを示した。 一般化された後悔最小化の例に対して、いかなるアプローチ可能性のインスタンスも厳格に削減できることが示される。
• 参考スコア（独自算出の注目度）: 72.03309261614991
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Abernethy et al. (2011) showed that Blackwell approachability and no-regret learning are equivalent, in the sense that any algorithm that solves a specific Blackwell approachability instance can be converted to a sublinear regret algorithm for a specific no-regret learning instance, and vice versa. In this paper, we study a more fine-grained form of such reductions, and ask when this translation between problems preserves not only a sublinear rate of convergence, but also preserves the optimal rate of convergence. That is, in which cases does it suffice to find the optimal regret bound for a no-regret learning instance in order to find the optimal rate of convergence for a corresponding approachability instance? We show that the reduction of Abernethy et al. (2011) does not preserve rates: their reduction may reduce a $d$-dimensional approachability instance $I_1$ with optimal convergence rate $R_1$ to a no-regret learning instance $I_2$ with optimal regret-per-round of $R_2$, with $R_{2}/R_{1}$ arbitrarily large (in particular, it is possible that $R_1 = 0$ and $R_{2} > 0$). On the other hand, we show that it is possible to tightly reduce any approachability instance to an instance of a generalized form of regret minimization we call improper $\phi$-regret minimization (a variant of the $\phi$-regret minimization of Gordon et al. (2008) where the transformation functions may map actions outside of the action set). Finally, we characterize when linear transformations suffice to reduce improper $\phi$-regret minimization problems to standard classes of regret minimization problems in a rate preserving manner. We prove that some improper $\phi$-regret minimization instances cannot be reduced to either subclass of instance in this way, suggesting that approachability can capture some problems that cannot be phrased in the language of online learning.
• Abstract（参考訳）: Abernethy et al (2011) は、特定のブラックウェルアプローチ性インスタンスを解くアルゴリズムは、特定の非回帰学習インスタンスのサブ線形後悔アルゴリズムに変換できるという意味で、ブラックウェルアプローチ性と非回帰学習は等価であることを示した。 本稿では,このような縮小のよりきめ細かな形式について検討し,この問題間の変換が収束のサブ線形率だけでなく,収束の最適率も保持するかどうかを問う。 つまり、対応するアプローチ可能性インスタンスに対する最適収束率を求めるために、非回帰学習インスタンスに対する最適後悔境界を見つけるのに十分である場合がありますか? Abernethy et al (2011) の減少は、例えば、$d$-dimensional approachability instance $I_1$ を、最適収束率$R_1$ を任意の再帰学習インスタンス $R_2$ に還元する(特に、$R_{2}/R_{1}$ は、$R_1 = 0$ と $R_{2} > 0$ が任意に大きい)。 一方、任意のアプローチ可能性のインスタンスを、不適切な$\phi$-regret最小化(Gordon et al (2008) の$\phi$-regret最小化の変種)と呼ぶ一般的な後悔の形のインスタンスに厳密に還元することは可能である。 最後に, 線形変換が不適切な$\phi$-regret最小化問題を, 保留率で最小化問題の標準クラスに還元するのに十分である場合を特徴付ける。 このような方法では,いくつかの不適切な$\phi$-regret最小化インスタンスをインスタンスのいずれのサブクラスにも還元できないことを証明する。

関連論文リスト

• An Equivalence Between Static and Dynamic Regret Minimization [10.812831455376218]
  線形損失に対して、動的後悔最小化は、拡張決定空間における静的後悔最小化と等価であることを示す。 R_T(u_1,dots,u_T)le tildeという形式の動的後悔を保証するアルゴリズムを提供する。
  論文  参考訳（メタデータ） (2024-06-03T17:54:58Z)
• Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic Shortest Path [80.60592344361073]
  線形混合遷移カーネルを用いた最短経路(SSP)問題について検討する。 エージェントは繰り返し環境と対話し、累積コストを最小化しながら特定の目標状態に到達する。 既存の作業は、イテレーションコスト関数の厳密な下限や、最適ポリシーに対する期待長の上限を仮定することが多い。
  論文  参考訳（メタデータ） (2024-02-14T07:52:00Z)
• Learning Adversarial Low-rank Markov Decision Processes with Unknown Transition and Full-information Feedback [30.23951525723659]
  本研究は,全情報フィードバック設定において,逆向きに損失が変化する低ランクMDPについて検討する。 政策最適化に基づくアルゴリズムPOLOを提案し、$widetildeO(Kfrac56Afrac12dln (1+M)/ (1-gamma)2)$ regret guarantee。
  論文  参考訳（メタデータ） (2023-11-14T03:12:43Z)
• From External to Swap Regret 2.0: An Efficient Reduction and Oblivious Adversary for Large Action Spaces [29.29647282754262]
  我々は、ある仮説クラスに対して外部回帰アルゴリズムが存在しない場合、同じクラスに対して非スワップ回帰アルゴリズムが存在することも示している。 我々の減少は、あるゲームで非回帰学習が可能であるならば、このゲームは近似された平衡を持つ必要があることを意味する。
  論文  参考訳（メタデータ） (2023-10-30T17:50:29Z)
• $(\epsilon, u)$-Adaptive Regret Minimization in Heavy-Tailed Bandits [29.966828248335972]
  我々は,学習者に対して,$epsilon$と$u$が不明な場合に,後悔の最小化問題を調査する。 AdaR-UCBは、適応しない重みを帯びたケースとほぼ一致した後悔の保証を享受する最初のアルゴリズムである。
  論文  参考訳（メタデータ） (2023-10-04T17:11:15Z)
• Pseudonorm Approachability and Applications to Regret Minimization [73.54127663296906]
  我々は、高次元 $ell_infty$-approachability 問題を、低次元の擬ノルムアプローチ可能性問題に変換する。 我々は、$ell$や他のノルムに対するアプローチ可能性に関する以前の研究に類似した疑似ノルムアプローチ可能性のアルゴリズム理論を開発する。
  論文  参考訳（メタデータ） (2023-02-03T03:19:14Z)
• The Best of Both Worlds: Reinforcement Learning with Logarithmic Regret and Policy Switches [84.54669549718075]
  漸進的強化学習(RL)における後悔の最小化問題について検討する。 一般関数クラスと一般モデルクラスで学ぶことに集中する。 対数的後悔境界は$O(log T)$スイッチングコストのアルゴリズムによって実現可能であることを示す。
  論文  参考訳（メタデータ） (2022-03-03T02:55:55Z)
• First-Order Regret in Reinforcement Learning with Linear Function Approximation: A Robust Estimation Approach [57.570201404222935]
  我々は,大規模状態空間を用いた強化学習において,$mathcalO(sqrtV_1star K)$として,後悔のスケーリングが得られることを示す。 この結果を得るためには,少なくとも2乗推定に基づく既存手法は不十分であることを示す。
  論文  参考訳（メタデータ） (2021-12-07T00:29:57Z)
• Breaking the Sample Complexity Barrier to Regret-Optimal Model-Free Reinforcement Learning [52.76230802067506]
  漸進的強化学習における後悔を最小限に抑えるために,新しいモデルフリーアルゴリズムを提案する。 提案アルゴリズムは、2つのQ-ラーニングシーケンスの助けを借りて、初期設定された参照更新ルールを用いる。 初期の分散還元法の設計原理は、他のRL設定とは独立した関心を持つかもしれない。
  論文  参考訳（メタデータ） (2021-10-09T21:13:48Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。