Fugu-MT 論文翻訳(概要): Tracking the Best Strategy in an Extensive-Form Game

論文の概要: Tracking the Best Strategy in an Extensive-Form Game

arxiv url: http://arxiv.org/abs/2608.09501v1
Date: Mon, 10 Aug 2026 12:05:54 GMT
ステータス: 翻訳完了
システム内更新日: 2026-08-11 19:16:37.251024
Title: Tracking the Best Strategy in an Extensive-Form Game
Title（参考訳）: 総合型ゲームにおけるベストストラテジーの追跡
Abstract要約: 本稿では, 学習者の期待性能を, 振り返りにおける混合戦略のスイッチングシーケンスに対して測定する, 後悔の切り替えという概念に焦点をあてる。我々のアルゴリズムは非常に効率的で、トライアル時間は$mathcalO(HB)$で、そこでは$B$は学習者が任意の情報集合で利用できる最大アクション数である。
参考スコア（独自算出の注目度）: 6.572714770742585
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: We consider the extensive-form bandit problem where on each trial the learner plays an extensive-form game against an oblivious adversary. We focus on the notion of switching regret, which measures the expected performance of the learner against that of any switching sequence of mixed strategies in retrospect. Our algorithm takes a parameter $ρ>0$ and achieves a switching regret of $\tilde{\mathcal{O}}((1/ρ+ρK)\sqrt{H A T})$ where $K$ is the number of switches in the comparator sequence, $H$ is the maximum number of the learner's information sets that can be traversed during a play of the game and $A$ is the number of actions that the learner can possibly take. Our algorithm is extremely efficient, taking a per trial time of only $\mathcal{O}(H B)$ where $B$ is the maximum number of actions available to the learner at any of its information sets.
Abstract（参考訳）: 本研究では,各試行において,学習者が不愉快な相手に対して広義のゲームをする,広義の盗賊問題について考察する。本稿では, 学習者の期待性能を, 振り返りにおける混合戦略のスイッチングシーケンスに対して測定する, 後悔の切り替えという概念に焦点をあてる。我々のアルゴリズムはパラメータを$ρ>0$とすることで、$\tilde{\mathcal{O}}((1/ρ+ρK)\sqrt{H A T})$の切替後悔を実現する。我々のアルゴリズムは非常に効率的で、試行時間あたり$\mathcal{O}(H B)$しか取らない。

関連論文リスト

Toward Optimal Switching Regret for Multi-Armed Bandits with Oblivious Adversary [13.08870048693199]
我々は, 1 つのアルゴリズムが, 難解な敵に対して 1 ドルごとに$widetildemathcalO(sqrt(S+1)KT)$ expected regret を達成することを示す。提案アルゴリズムは,固定共有学習者と,局所的な改善を探索するダイアディック・インターバルを併用する。
論文参考訳（メタデータ） (2026-09-11T21:23:20Z)
An Efficient Near-Optimal Algorithm for Adversarial $m$-Set Bandits [13.063864592666777]
各ラウンドで学習者が$d$アイテムから$m$を選択し、選択した項目の総損失のみを観察する。結果として得られる作用集合は$K=binomdm$要素を含み、したがって指数関数的に大きい。本稿では,この構造を利用した計算効率のよいアルゴリズムを提案する。
論文参考訳（メタデータ） (2026-08-12T16:28:06Z)
Differential Privacy in the Extensive-Form Bandit Problem [6.572714770742585]
広義のバンディット問題について考察し、各トライアルにおいて、学習者が難解な相手に対して広義のゲームをする。局所微分プライバシーを$$で満たし、$tildeO(sqrtAln(S)T/)$を後悔する問題に対するアルゴリズムを提供する。各試行において、我々のアルゴリズムの複雑さの時間は、インフォセットにおけるアクションの最大回数において最大対数であり、その削減戦略をユーザに伝達するために必要な時間に等しい。
論文参考訳（メタデータ） (2026-05-06T09:19:11Z)
An Improved Algorithm for Adversarial Linear Contextual Bandits via Reduction [13.78877509090251]
逆損失とアクションセットを持つ線形文脈帯域に対する効率的なアルゴリズムを提案する。我々のアルゴリズムは、まず最初に$text(d)sqrtT$後悔を達成するが、事前のアルゴリズムが我々の知識に間に合うように$o(T)$後悔することはない。
論文参考訳（メタデータ） (2025-08-16T06:25:18Z)
Best of Both Worlds: Regret Minimization versus Minimax Play [57.68976579579758]
この結果から,悪用可能な相手からOmega(T)$を得ることができながら,少なくともO(1)$損失のリスクを保証できることが分かる。
論文参考訳（メタデータ） (2025-02-17T11:04:01Z)
Learning to Play Against Unknown Opponents [9.346742321348366]
本研究では,学習エージェントが非学習に制約されない場合に,最適な学習アルゴリズムを効率的に構築する方法を示す。これらの結果は、最近開発された機械を用いて、学習アルゴリズムの分析をメニューとして知られる幾何学的対象のクラスに変換する。
論文参考訳（メタデータ） (2024-12-24T09:05:06Z)
Corrupted Learning Dynamics in Games [62.73758165845971]
すべてのプレイヤーが楽観的な追従型リーダー(OFTRL)に従うと、平衡は$O(log T)$の速さで計算できる。本稿では,各プレイヤーが所定のアルゴリズムによって提案される戦略から逸脱する程度に依存する速度で,適応的に平衡を求める学習ダイナミクスを提案する。
論文参考訳（メタデータ） (2024-12-10T02:23:44Z)
Contextual Bandits and Imitation Learning via Preference-Based Active Queries [17.73844193143454]
本研究では,学習者が実行された行動報酬の直接的な知識を欠いている文脈的包帯と模倣学習の問題を考察する。その代わり、学習者は各ラウンドのエキスパートに積極的に問い合わせて2つのアクションを比較し、ノイズの多い好みのフィードバックを受け取ることができる。学習者の目的は、実行されたアクションに関連する後悔を最小限に抑えると同時に、専門家が行った比較クエリの数を最小化することである。
論文参考訳（メタデータ） (2023-07-24T16:36:04Z)
Near-Optimal No-Regret Learning for General Convex Games [121.50979258049135]
一般凸およびコンパクト戦略集合に対して後悔が得られることを示す。我々の力学は、適度にエンハンリフトされた空間上の楽観的な従順化バウンドのインスタンス化にある。先行結果が適用される特殊な場合であっても、我々のアルゴリズムは最先端の後悔よりも改善される。
論文参考訳（メタデータ） (2022-06-17T12:58:58Z)
Complete Policy Regret Bounds for Tallying Bandits [51.039677652803675]
政策後悔は、適応的な敵に対してオンライン学習アルゴリズムのパフォーマンスを測定するという、よく確立された概念である。我々は,不完全な政策後悔を効果的に最小化できる敵の制限について検討する。我々は、$tildemathcalO(mKsqrtT)$の完全なポリシーを後悔するアルゴリズムを提供し、$tildemathcalO$表記は対数要素だけを隠す。
論文参考訳（メタデータ） (2022-04-24T03:10:27Z)
Near-Optimal Learning of Extensive-Form Games with Imperfect Information [54.55092907312749]
本稿では,2プレイヤーゼロサムゲームにおいて,$widetildemathcalO((XA+YB)/varepsilon2)$プレイのエピソードのみを必要とするアルゴリズムの最初の行を,$varepsilon$-approximate Nash平衡を求める。これにより$widetildemathcalO((X2A+Y2B)/varepsilon2)$が$widetildemathcalO(maxX,
論文参考訳（メタデータ） (2022-02-03T18:18:28Z)
A Bayesian Learning Algorithm for Unknown Zero-sum Stochastic Games with an Arbitrary Opponent [9.094186120476174]
ゼロサムゲームのための後サンプリング強化学習(PSRL-ZSG) ゼロサムゲームのための後サンプリング強化学習(PSRL-ZSG)を提案する。
論文参考訳（メタデータ） (2021-09-08T02:05:40Z)
Impact of Representation Learning in Linear Bandits [83.17684841392754]
本研究では,表現学習が帯域幅問題の効率性を向上させる方法について検討する。我々は,$widetildeO(TsqrtkN + sqrtdkNT)$ regretを達成する新しいアルゴリズムを提案する。
論文参考訳（メタデータ） (2020-10-13T16:35:30Z)

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