論文の概要: Refined approachability algorithms and application to regret minimization with global costs

• arxiv url: http://arxiv.org/abs/2009.03831v4
• Date: Tue, 7 Sep 2021 15:22:28 GMT
• ステータス: 処理完了
• システム内更新日: 2022-10-20 21:04:50.295038
• Title: Refined approachability algorithms and application to regret minimization with global costs
• Title（参考訳）: 精巧なアプローチ可能性アルゴリズムとグローバルコストによる後悔の最小化への応用
• Authors: Joon Kwon
• Abstract要約: ブラックウェルのアプローチ可能性 (Blackwell's approachability) は、2人のプレイヤー、すなわち意思決定者(Decision Maker)と環境(Environment)がベクター価値のペイオフで繰り返しゲームをする枠組みである。 我々は、ブラックウェルのアプローチ可能性のために、正規化リーダアルゴリズム(FTRL)のクラスを構築し、分析する。 この柔軟性により、これらのアルゴリズムを適用して、様々なオンライン学習問題への関心度を極力最小化することができる。
• 参考スコア（独自算出の注目度）: 0.38073142980732994
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Blackwell's approachability is a framework where two players, the Decision Maker and the Environment, play a repeated game with vector-valued payoffs. The goal of the Decision Maker is to make the average payoff converge to a given set called the target. When this is indeed possible, simple algorithms which guarantee the convergence are known. This abstract tool was successfully used for the construction of optimal strategies in various repeated games, but also found several applications in online learning. By extending an approach proposed by (Abernethy et al., 2011), we construct and analyze a class of Follow the Regularized Leader algorithms (FTRL) for Blackwell's approachability which are able to minimize not only the Euclidean distance to the target set (as it is often the case in the context of Blackwell's approachability) but a wide range of distance-like quantities. This flexibility enables us to apply these algorithms to closely minimize the quantity of interest in various online learning problems. In particular, for regret minimization with $\ell_p$ global costs, we obtain the first bounds with explicit dependence in $p$ and the dimension $d$.
• Abstract（参考訳）: ブラックウェルのアプローチ可能性(英: approachability)は、意思決定者と環境の2人のプレイヤーが、ベクター価値のある支払いで繰り返しゲームをするフレームワークである。 Decision Makerの目標は、平均的なペイオフをターゲットと呼ばれる特定のセットに収束させることだ。 これが可能であれば、収束を保証する単純なアルゴリズムが知られている。 この抽象ツールは、様々な繰り返しゲームにおける最適戦略の構築に成功し、オンライン学習にもいくつかの応用が見つかった。 Abernethy et al., 2011) によって提案されたアプローチを拡張して、対象集合へのユークリッド距離を最小化できるブラックウェルのアプローチ可能性に対する正規化リーダアルゴリズム(FTRL)のクラスを構築し、解析する(ブラックウェルのアプローチ可能性の文脈ではしばしばそうであるように)。 この柔軟性により、様々なオンライン学習問題に対する関心を最小化するために、これらのアルゴリズムを適用できます。 特に、$\ell_p$グローバルコストによる後悔の最小化に対して、$p$と次元$d$に明示的に依存する最初の境界を得る。

関連論文リスト

• Learning to Cover: Online Learning and Optimization with Irreversible Decisions [50.5775508521174]
  後悔は$Thetaleft(mfrac12cdotfrac11-2-Tright)$で半直線的に成長するので、指数関数的に$Theta(sqrtm)$に収束する。 これらの調査結果は、限定的なオンライン学習と最適化の利点を浮き彫りにしている。
  論文  参考訳（メタデータ） (2024-06-20T23:00:25Z)
• Pseudonorm Approachability and Applications to Regret Minimization [73.54127663296906]
  我々は、高次元 $ell_infty$-approachability 問題を、低次元の擬ノルムアプローチ可能性問題に変換する。 我々は、$ell$や他のノルムに対するアプローチ可能性に関する以前の研究に類似した疑似ノルムアプローチ可能性のアルゴリズム理論を開発する。
  論文  参考訳（メタデータ） (2023-02-03T03:19:14Z)
• PDE-Based Optimal Strategy for Unconstrained Online Learning [40.61498562988079]
  部分微分方程式(PDE)を解くことによって時間変化ポテンシャル関数を生成するフレームワークを提案する。 我々のフレームワークは、いくつかの古典的なポテンシャルを回復し、より重要なことは、新しいものを設計するための体系的なアプローチを提供する。 これは最適なリード定数を持つ最初のパラメータフリーアルゴリズムである。
  論文  参考訳（メタデータ） (2022-01-19T22:21:21Z)
• Online Allocation with Two-sided Resource Constraints [44.5635910908944]
  我々は,要求が順次到着する,リソース制約の低いオンラインアロケーション問題を考える。 提案手法では, リクエスト全体を知るオフライン問題に対して, 1-O (fracepsilonalpha-epsilon)$-competitive ratioを求めるアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-12-28T02:21:06Z)
• Adaptive Multi-Goal Exploration [118.40427257364729]
  我々は、AdaGoalが$epsilon$-optimal goal-conditioned policyを学習する目的を達成するためにどのように使えるかを示す。 AdaGoalは、ゴール条件の深い強化学習のための既存の手法の高レベルなアルゴリズム構造に固定されている。
  論文  参考訳（メタデータ） (2021-11-23T17:59:50Z)
• Breaking the Sample Complexity Barrier to Regret-Optimal Model-Free Reinforcement Learning [52.76230802067506]
  漸進的強化学習における後悔を最小限に抑えるために,新しいモデルフリーアルゴリズムを提案する。 提案アルゴリズムは、2つのQ-ラーニングシーケンスの助けを借りて、初期設定された参照更新ルールを用いる。 初期の分散還元法の設計原理は、他のRL設定とは独立した関心を持つかもしれない。
  論文  参考訳（メタデータ） (2021-10-09T21:13:48Z)
• Byzantine-Resilient Non-Convex Stochastic Gradient Descent [61.6382287971982]
  敵対的レジリエントな分散最適化。 機械は独立して勾配を計算し 協力することができます 私達のアルゴリズムは新しい集中の技術およびサンプル複雑性に基づいています。 それは非常に実用的です:それはないときすべての前の方法の性能を改善します。 セッティングマシンがあります。
  論文  参考訳（メタデータ） (2020-12-28T17:19:32Z)
• Online Model Selection for Reinforcement Learning with Function Approximation [50.008542459050155]
  我々は、$tildeO(L5/6 T2/3)$ regretで最適な複雑性に適応するメタアルゴリズムを提案する。 また、メタアルゴリズムは、インスタンス依存の後悔境界を著しく改善することを示す。
  論文  参考訳（メタデータ） (2020-11-19T10:00:54Z)

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

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