論文の概要: Time-Dependent Blackwell Approachability and Application to Absorbing Games

• arxiv url: http://arxiv.org/abs/2303.04956v2
• Date: Thu, 22 Aug 2024 20:44:46 GMT
• ステータス: 処理完了
• システム内更新日: 2024-08-26 20:34:38.702166
• Title: Time-Dependent Blackwell Approachability and Application to Absorbing Games
• Title（参考訳）: 時間依存型ブラックウェルアプローチと吸収ゲームへの応用
• Authors: Joon Kwon, Yijun Wan, Bruno Ziliotto,
• Abstract要約: 平均結果の座標ごとに異なる収束速度が得られる時間依存内積の族を示す。 この枠組みをブラックウェルのアルゴリズムを用いて$varepsilon$-uniformly optimal strategyを構築するゲームに応用する。
• 参考スコア（独自算出の注目度）: 3.7141182051230914
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Blackwell's approachability (Blackwell, 1954, 1956) is a very general online learning framework where a Decision Maker obtains vector-valued outcomes, and aims at the convergence of the average outcome to a given ``target'' set. Blackwell gave a sufficient condition for the decision maker having a strategy guaranteeing such a convergence against an adversarial environment, as well as what we now call the Blackwell's algorithm, which then ensures convergence. Blackwell's approachability has since been applied to numerous problems, in regret minimization and game theory, in particular. We extend this framework by allowing the outcome function and the inner product to be time-dependent. We establish a general guarantee for the natural extension to this framework of Blackwell's algorithm. In the case where the target set is an orthant, we present a family of time-dependent inner products which yields different convergence speeds for each coordinate of the average outcome. We apply this framework to absorbing games (an important class of stochastic games) for which we construct $\varepsilon$-uniformly optimal strategies using Blackwell's algorithm in a well-chosen auxiliary approachability problem, thereby giving a novel illustration of the relevance of online learning tools for solving games.
• Abstract（参考訳）: Blackwell's approachability (Blackwell, 1954, 1956) は、決定因子がベクトル値の結果を得る、非常に一般的なオンライン学習フレームワークであり、与えられた 'target' 集合への平均結果の収束を目指している。 ブラックウェルは、敵の環境に対してそのような収束を保証する戦略と、現在ブラックウェルのアルゴリズムと呼ばれるものを持ち、収束を保証する戦略を持つ意思決定者に十分な条件を与えた。 ブラックウェルのアプローチ性はその後、後悔の最小化やゲーム理論など多くの問題に適用された。 結果関数と内部積を時間依存にすることで、このフレームワークを拡張します。 我々は、ブラックウェルのアルゴリズムのこのフレームワークへの自然な拡張に対する一般的な保証を確立する。 対象集合がオルサントである場合、平均結果の座標ごとに異なる収束速度が得られる時間依存内積の族を示す。 我々はこの枠組みを,ブラックウェルのアルゴリズムを用いたゲーム(確率ゲームの重要なクラス)の吸収に適用し,ゲーム解決におけるオンライン学習ツールの関連性を示す。

関連論文リスト

• A unified stochastic approximation framework for learning in games [82.74514886461257]
  ゲームにおける学習の長期的挙動(連続的・有限的)を解析するためのフレキシブルな近似フレームワークを開発する。 提案する分析テンプレートには,勾配に基づく手法,有限ゲームでの学習のための指数的/乗算的重み付け,楽観的および帯域的変異など,幅広い一般的な学習アルゴリズムが組み込まれている。
  論文  参考訳（メタデータ） (2022-06-08T14:30:38Z)
• Contextual Model Aggregation for Fast and Robust Federated Learning in Edge Computing [88.76112371510999]
  フェデレーション学習は、ネットワークエッジにおける分散機械学習の第一候補である。 既存のアルゴリズムは、性能の緩やかな収束や堅牢性の問題に直面している。 そこで本稿では,損失低減に対する最適コンテキスト依存境界を実現するためのコンテキストアグリゲーション手法を提案する。
  論文  参考訳（メタデータ） (2022-03-23T21:42:31Z)
• Preference learning along multiple criteria: A game-theoretic perspective [97.94912276610002]
  我々は、ブラックウェルの接近性からインスピレーションを得て、フォン・ノイマンの勝者の概念をマルチ基準設定に一般化する。 本フレームワークは,基準間の選好の非線形集約を可能にし,多目的最適化から線形化に基づくアプローチを一般化する。 凸最適化問題の解法として,マルチ基準問題インスタンスのブラックウェルの勝者が計算可能であることを示す。
  論文  参考訳（メタデータ） (2021-05-05T03:23:11Z)
• Provably Efficient Algorithms for Multi-Objective Competitive RL [54.22598924633369]
  エージェントの報酬がベクトルとして表現される多目的強化学習(RL)について検討する。 エージェントが相手と競合する設定では、その平均戻りベクトルから目標セットまでの距離によってその性能を測定する。 統計的および計算学的に効率的なアルゴリズムを開発し、関連するターゲットセットにアプローチする。
  論文  参考訳（メタデータ） (2021-02-05T14:26:00Z)
• Efficient Pure Exploration for Combinatorial Bandits with Semi-Bandit Feedback [51.21673420940346]
  コンビナーシャルバンディットはマルチアームバンディットを一般化し、エージェントが腕のセットを選択し、選択したセットに含まれる各腕の騒々しい報酬を観察します。 我々は, 最善の腕を一定の信頼度で識別する純粋爆発問題と, 応答集合の構造が動作集合の1つと異なるような, より一般的な設定に注目する。 有限多面体に対するプロジェクションフリーオンライン学習アルゴリズムに基づいて、凸的に最適であり、競争力のある経験的性能を持つ最初の計算効率の良いアルゴリズムである。
  論文  参考訳（メタデータ） (2021-01-21T10:35:09Z)
• Blackwell Online Learning for Markov Decision Processes [28.79413432611949]
  本研究は,オンライン最適化の観点からのマルコフ決定過程(mdp)の新しい解釈を提供する。 MDPにより誘導されるブラックウェルゲームを構築し、後悔の最小化、ブラックウェルアプローチ可能性理論、MDPの学習理論のギャップを埋める。
  論文  参考訳（メタデータ） (2020-12-28T00:40:01Z)
• Refined approachability algorithms and application to regret minimization with global costs [0.38073142980732994]
  ブラックウェルのアプローチ可能性 (Blackwell's approachability) は、2人のプレイヤー、すなわち意思決定者(Decision Maker)と環境(Environment)がベクター価値のペイオフで繰り返しゲームをする枠組みである。 我々は、ブラックウェルのアプローチ可能性のために、正規化リーダアルゴリズム(FTRL)のクラスを構築し、分析する。 この柔軟性により、これらのアルゴリズムを適用して、様々なオンライン学習問題への関心度を極力最小化することができる。
  論文  参考訳（メタデータ） (2020-09-08T15:54:08Z)
• Faster Game Solving via Predictive Blackwell Approachability: Connecting Regret Matching and Mirror Descent [119.5481797273995]
  FTRL (Follow-the-regularized-leader) とオンラインミラー降下 (OMD) は、オンライン凸最適化における最も一般的な後悔の最小化手法である。 RMとRM+はFTRLとOMDをそれぞれ実行し、ブラックウェルのアプローチ性ゲームにおいて、ハーフスペースを常に強制的に選択するアルゴリズムであることを示す。 18の共通ゼロサムワイドフォームベンチマークゲームを対象とした実験では,予測的RM+と反ファクト的後悔の最小化が,最速のアルゴリズムよりもはるかに高速に収束することを示した。
  論文  参考訳（メタデータ） (2020-07-28T16:49:55Z)

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

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