論文の概要: 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' 集合への平均結果の収束を目指している。
ブラックウェルは、敵の環境に対してそのような収束を保証する戦略と、現在ブラックウェルのアルゴリズムと呼ばれるものを持ち、収束を保証する戦略を持つ意思決定者に十分な条件を与えた。
ブラックウェルのアプローチ性はその後、後悔の最小化やゲーム理論など多くの問題に適用された。
結果関数と内部積を時間依存にすることで、このフレームワークを拡張します。
我々は、ブラックウェルのアルゴリズムのこのフレームワークへの自然な拡張に対する一般的な保証を確立する。
対象集合がオルサントである場合、平均結果の座標ごとに異なる収束速度が得られる時間依存内積の族を示す。
我々はこの枠組みを,ブラックウェルのアルゴリズムを用いたゲーム(確率ゲームの重要なクラス)の吸収に適用し,ゲーム解決におけるオンライン学習ツールの関連性を示す。
関連論文リスト
- Margin theory for the scenario-based approach to robust optimization in
high dimension [0.0]
本稿では、ロバストな最適化のためのシナリオアプローチを扱う。
これは、問題の不確実性によって引き起こされる可能性のある無限個の制約のランダムサンプリングに依存する。
論文 参考訳(メタデータ) (2023-03-07T13:33:46Z) - Learning Equilibria in Matching Markets from Bandit Feedback [139.29934476625488]
不確実性の下で安定した市場成果を学習するためのフレームワークとアルゴリズムを開発する。
私たちの研究は、大規模なデータ駆動の市場において、いつ、どのように安定したマッチングが生じるかを明らかにするための第一歩を踏み出します。
論文 参考訳(メタデータ) (2021-08-19T17:59:28Z) - Bayesian decision-making under misspecified priors with applications to
meta-learning [64.38020203019013]
トンプソンサンプリングやその他のシーケンシャルな意思決定アルゴリズムは、文脈的包帯における探索と探索のトレードオフに取り組むための一般的なアプローチである。
性能は不特定な事前条件で優雅に低下することを示す。
論文 参考訳(メタデータ) (2021-07-03T23:17:26Z) - Preference learning along multiple criteria: A game-theoretic
perspective [97.94912276610002]
我々は、ブラックウェルの接近性からインスピレーションを得て、フォン・ノイマンの勝者の概念をマルチ基準設定に一般化する。
本フレームワークは,基準間の選好の非線形集約を可能にし,多目的最適化から線形化に基づくアプローチを一般化する。
凸最適化問題の解法として,マルチ基準問題インスタンスのブラックウェルの勝者が計算可能であることを示す。
論文 参考訳(メタデータ) (2021-05-05T03:23:11Z) - On the Optimality of Batch Policy Optimization Algorithms [106.89498352537682]
バッチポリシー最適化は、環境と対話する前に既存のデータをポリシー構築に活用することを検討する。
信頼調整インデックスアルゴリズムは楽観的,悲観的,中立的いずれであってもミニマックス最適であることを示す。
最適値予測の本来の難易度を考慮した新しい重み付き最小値基準を提案する。
論文 参考訳(メタデータ) (2021-04-06T05:23:20Z) - 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) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。