論文の概要: Blackwell's Approachability with Time-Dependent Outcome Functions and
Dot Products. Application to the Big Match
- arxiv url: http://arxiv.org/abs/2303.04956v1
- Date: Thu, 9 Mar 2023 00:14:46 GMT
- ステータス: 処理完了
- システム内更新日: 2023-03-10 16:29:43.321752
- Title: Blackwell's Approachability with Time-Dependent Outcome Functions and
Dot Products. Application to the Big Match
- Title（参考訳）: 時間依存結果関数とドット積を持つブラックウェルのアプローチ可能性。
ビッグマッチへの応用
- Authors: Joon Kwon, Bruno Ziliotto
- Abstract要約: Blackwellのアプローチ性は、決定メーカーがベクトル値の結果を得るシーケンシャルな決定フレームワークである。
結果関数とドット積を時間依存で可能にすることで、このフレームワークを拡張します。
- 参考スコア（独自算出の注目度）: 0.5330240017302619
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Blackwell's approachability is a very general sequential decision 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 online learning
and game theory, in particular. We extend this framework by allowing the
outcome function and the dot 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 dot products which yields different convergence speeds for
each coordinate of the average outcome. We apply this framework to the Big
Match (one of the most important toy examples of stochastic games) where an
$\epsilon$-uniformly optimal strategy for Player I is given by Blackwell's
algorithm in a well-chosen auxiliary approachability problem.
- Abstract（参考訳）: ブラックウェルのアプローチ可能性(blackwell's approachability)は、意思決定者がベクトル値の成果を得る非常に一般的なシーケンシャルな決定フレームワークであり、与えられた「目標」集合への平均結果の収束を目標としている。
ブラックウェルは、敵の環境に対してそのような収束を保証する戦略を持つ意思決定者に十分な条件を与え、我々が現在ブラックウェルのアルゴリズムと呼ぶものを与え、収束を確実にする。
ブラックウェルのアプローチ性は、オンライン学習やゲーム理論、特に多くの問題に応用されてきた。
結果関数とドット積を時間依存で可能にすることで、このフレームワークを拡張します。
我々は、ブラックウェルのアルゴリズムのこの枠組みの自然な拡張に対する一般的な保証を確立する。
対象集合がオルサントである場合、平均結果の座標ごとに異なる収束速度が得られる時間依存ドット積の族を示す。
我々はこのフレームワークをビッグマッチ(確率ゲームにおける最も重要な玩具の例)に適用し、プレイヤーIに対する$\epsilon$-uniformly optimal strategy をブラックウェルのアルゴリズムにより、よく補足的なアプローチ可能性問題で与えられる。
関連論文リスト
- 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。