論文の概要: 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 をブラックウェルのアルゴリズムにより、よく補足的なアプローチ可能性問題で与えられる。
関連論文リスト
- 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。