論文の概要: Learning to Play Against Unknown Opponents
- arxiv url: http://arxiv.org/abs/2412.18297v1
- Date: Tue, 24 Dec 2024 09:05:06 GMT
- ステータス: 翻訳完了
- システム内更新日: 2024-12-25 15:53:52.239110
- Title: Learning to Play Against Unknown Opponents
- Title（参考訳）: 未知の反対者に対する遊び方を学ぶ
- Authors: Eshwar Ram Arunachaleswaran, Natalie Collina, Jon Schneider,
- Abstract要約: 本稿では,戦略的相手に対して,総和ゲームを繰り返し行う学習エージェントの問題点を考察する。
学習エージェントは、自身の支払機能を知っているが、相手の支払機能については不確実である。
エージェントは、自身の全ユーティリティを最大化するために、どのような学習アルゴリズムを実行するべきか?
- 参考スコア（独自算出の注目度）: 9.346742321348366
- License:
- Abstract: We consider the problem of a learning agent who has to repeatedly play a general sum game against a strategic opponent who acts to maximize their own payoff by optimally responding against the learner's algorithm. The learning agent knows their own payoff function, but is uncertain about the payoff of their opponent (knowing only that it is drawn from some distribution $\mathcal{D}$). What learning algorithm should the agent run in order to maximize their own total utility? We demonstrate how to construct an $\varepsilon$-optimal learning algorithm (obtaining average utility within $\varepsilon$ of the optimal utility) for this problem in time polynomial in the size of the input and $1/\varepsilon$ when either the size of the game or the support of $\mathcal{D}$ is constant. When the learning algorithm is further constrained to be a no-regret algorithm, we demonstrate how to efficiently construct an optimal learning algorithm (asymptotically achieving the optimal utility) in polynomial time, independent of any other assumptions. Both results make use of recently developed machinery that converts the analysis of learning algorithms to the study of the class of corresponding geometric objects known as menus.
- Abstract（参考訳）: 本稿では,学習者のアルゴリズムに最適に対応することで,自己の利益を最大化するために行動する戦略的相手に対して,総合的な総和ゲームを繰り返し行う学習エージェントの問題を考える。
学習エージェントは、自身のペイオフ関数を知っているが、相手のペイオフについて不確実である(ある分布から引き出されることのみを知っていれば、$\mathcal{D}$である)。
エージェントは、自身の全ユーティリティを最大化するために、どのような学習アルゴリズムを実行するべきか?
ゲームのサイズや$\mathcal{D}$のサポートが一定である場合、入力サイズの時間多項式と1/\varepsilon$におけるこの問題に対して、$\varepsilon$-Optimal Learningアルゴリズム(最適ユーティリティの$\varepsilon$の平均効用を得る)を構築する方法を示す。
学習アルゴリズムが非回帰アルゴリズムであるようにさらに制約された場合、多項式時間で最適な学習アルゴリズム(漸近的に最適効用を達成する)を、他の仮定とは無関係に効率的に構築する方法を実証する。
どちらも最近開発された機械を用いて、学習アルゴリズムの分析をメニューとして知られる幾何学的対象のクラスに変換する。
関連論文リスト
- Maximizing utility in multi-agent environments by anticipating the behavior of other learners [17.703508282875323]
マルチエージェント設定では、各エージェントの決定がユーティリティや他のエージェントに影響を与える可能性がある。
本稿では,2種類のエージェントを含む2人プレイヤゲームについて検討する。
論文 参考訳（メタデータ） (2024-07-05T23:16:18Z) - A Competitive Algorithm for Agnostic Active Learning [5.4579367210379335]
アクティブな学習のための最も一般的なアルゴリズムは、不一致係数と呼ばれるパラメータでその性能を表現する。
我々は、任意の二進仮説クラス$H$と分布$D_X$ over$X$に対して最適なアルゴリズムと競合するアルゴリズムを得る。
我々のアルゴリズムの$O(log |H|)$オーバーヘッドよりは、NPハードである。
論文 参考訳（メタデータ） (2023-10-28T19:01:16Z) - Efficiently Learning One-Hidden-Layer ReLU Networks via Schur
Polynomials [50.90125395570797]
正方形損失に関して、標準的なガウス分布の下での$k$ReLU活性化の線形結合をPAC学習する問題をmathbbRd$で検討する。
本研究の主な成果は,この学習課題に対して,サンプルおよび計算複雑性が$(dk/epsilon)O(k)$で,epsilon>0$が目標精度である。
論文 参考訳（メタデータ） (2023-07-24T14:37:22Z) - Streaming Algorithms for Learning with Experts: Deterministic Versus
Robust [62.98860182111096]
エキスパート問題を伴うオンライン学習では、アルゴリズムは、T$day(または時間)ごとに結果を予測する必要がある。
目標は最小限のコストで予測を行うことだ。
最良専門家が$M$の誤りを犯したとき、後悔する$R$を達成するような決定論的アルゴリズムに対して、$widetildeOmegaleft(fracnMRTright)$の空間下界を示す。
論文 参考訳（メタデータ） (2023-03-03T04:39:53Z) - Strategizing against Learners in Bayesian Games [74.46970859427907]
プレイヤーの1人である学習者が無学習の学習戦略を採用する2人プレイヤゲームについて検討した。
一般のベイズゲームでは,学習者と学習者の双方の報酬の支払いが,そのタイプに依存する可能性がある。
論文 参考訳（メタデータ） (2022-05-17T18:10:25Z) - Randomized Exploration for Reinforcement Learning with General Value
Function Approximation [122.70803181751135]
本稿では,ランダム化最小二乗値反復(RLSVI)アルゴリズムに着想を得たモデルレス強化学習アルゴリズムを提案する。
提案アルゴリズムは,スカラーノイズを用いたトレーニングデータを簡易に摂動させることにより,探索を促進する。
我々はこの理論を、既知の困難な探査課題にまたがる実証的な評価で補完する。
論文 参考訳（メタデータ） (2021-06-15T02:23:07Z) - Minimax Optimization with Smooth Algorithmic Adversaries [59.47122537182611]
対戦相手が展開するスムーズなアルゴリズムに対して,Min-playerの新しいアルゴリズムを提案する。
本アルゴリズムは,制限周期のない単調進行を保証し,適切な勾配上昇数を求める。
論文 参考訳（メタデータ） (2021-06-02T22:03:36Z) - Near-Optimal Reinforcement Learning with Self-Play [50.29853537456737]
我々は,直接の監督なしに自己対決で最適な政策を学習するセルフプレイアルゴリズムに焦点をあてる。
本稿では,サンプル複雑性を$tildemathcalO(SAB)$,サンプル複雑性を$tildemathcalO(S(A+B)$とする新しいemphNash Vラーニングアルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-06-22T05:00:13Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。