論文の概要: Bandit Learning for Dynamic Colonel Blotto Game with a Budget Constraint

• arxiv url: http://arxiv.org/abs/2103.12833v1
• Date: Tue, 23 Mar 2021 20:52:56 GMT
• ステータス: 処理完了
• システム内更新日: 2021-03-25 13:44:29.845727
• Title: Bandit Learning for Dynamic Colonel Blotto Game with a Budget Constraint
• Title（参考訳）: 予算制約付き動的ブロットーゲームのためのバンディット学習
• Authors: Vincent Leon, S. Rasoul Etesami
• Abstract要約: 私たちは、プレイヤーの1人が学習者であり、有限の時間の地平線に割り当てる部隊(予算)が限られているダイナミックなBlottoゲーム(CBG)を検討します。 各段階で、学習者は過去の観測に基づいて戦場に割り当てる予算とその配分を戦略的に決定します。 学習者の目的は後悔を最小限に抑えることであり、これは最良の動的政策の観点で最適報酬の差として定義される。
• 参考スコア（独自算出の注目度）: 0.913755431537592
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We consider a dynamic Colonel Blotto game (CBG) in which one of the players is the learner and has limited troops (budget) to allocate over a finite time horizon. At each stage, the learner strategically determines the budget and its distribution to allocate among the battlefields based on past observations. The other player is the adversary, who chooses its budget allocation strategies randomly from some fixed but unknown distribution. The learner's objective is to minimize the regret, which is defined as the difference between the optimal payoff in terms of the best dynamic policy and the realized payoff by following a learning algorithm. The dynamic CBG is analyzed under the framework of combinatorial bandit and bandit with knapsacks. We first convert the dynamic CBG with the budget constraint to a path planning problem on a graph. We then devise an efficient dynamic policy for the learner that uses a combinatorial bandit algorithm Edge on the path planning graph as a subroutine for another algorithm LagrangeBwK. A high-probability regret bound is derived, and it is shown that under the proposed policy, the learner's regret in the budget-constrained dynamic CBG matches (up to a logarithmic factor) that of the repeated CBG without budget constraints.
• Abstract（参考訳）: プレイヤーの1人が学習者であり、有限時間地平線上で割り当てる限られた兵力(予算)を有する動的大佐ブロットーゲーム(CBG)を考える。 各段階において、学習者は、過去の観測に基づいて戦場間で割り当てる予算とその配分を戦略的に決定する。 他のプレイヤーは敵であり、一定のが未知の分布からランダムに予算配分戦略を選択する。 学習者の目的は後悔を最小限に抑えることであり、これは学習アルゴリズムに従えば、最良のダイナミックポリシーの観点で最適のペイオフと実現されたペイオフとの差として定義される。 動的CBGは,クナプサックと組み合わせバンドイットおよびバンドイットの枠組みの下で解析される。 まず,動的cbgを予算制約付きでグラフ上の経路計画問題に変換する。 次に、経路計画グラフ上のEdgeを別のアルゴリズムであるLagrangeBwKのサブルーチンとして使用する学習者に対して効率的な動的ポリシーを考案する。 提案方針の下では,予算制約のない繰り返しCBGの動的CBGとの一致(対数係数まで)に対する学習者の後悔が,予算制約を伴わないことを示す。

関連論文リスト

• Optimal cross-learning for contextual bandits with unknown context distributions [28.087360479901978]
  本稿では,バルセイロ等のクロスラーニング環境において,文脈的包括的アルゴリズムを設計する際の問題点について考察する。 コンテクスト数によらずに$widetildeO(sqrtTK)$というほぼ厳密な(対数的要因まで)後悔境界を持つ効率的なアルゴリズムを提供する。 アルゴリズムのコアとなるのは,複数のエポックにまたがるアルゴリズムの実行をコーディネートする新しい手法である。
  論文  参考訳（メタデータ） (2024-01-03T18:02:13Z)
• A unified stochastic approximation framework for learning in games [82.74514886461257]
  ゲームにおける学習の長期的挙動(連続的・有限的)を解析するためのフレキシブルな近似フレームワークを開発する。 提案する分析テンプレートには,勾配に基づく手法,有限ゲームでの学習のための指数的/乗算的重み付け,楽観的および帯域的変異など,幅広い一般的な学習アルゴリズムが組み込まれている。
  論文  参考訳（メタデータ） (2022-06-08T14:30:38Z)
• Distributed Task Management in Fog Computing: A Socially Concave Bandit Game [7.708904950194129]
  Fogコンピューティングは、ネットワークエッジでのタスクオフロード機能を活用して、効率を改善し、アプリケーション要求に対する迅速な応答を可能にする。 分散タスク割り当て問題を,帯域幅フィードバックによるソーシャルコンケーブゲームとして定式化する。 我々は2つのオンライン意思決定戦略を策定する。
  論文  参考訳（メタデータ） (2022-03-28T08:26:14Z)
• No-Regret Learning in Time-Varying Zero-Sum Games [99.86860277006318]
  固定ゼロサムゲームにおける繰り返しプレイからの学習は、ゲーム理論とオンライン学習における古典的な問題である。 提案手法は,3つの性能基準の下で,良好な保証を同時に享受できる1つのパラメータフリーアルゴリズムである。 本アルゴリズムは,ある特性を満たすブラックボックスベースラーナー群に対するメタアルゴリズムを用いた2層構造に基づく。
  論文  参考訳（メタデータ） (2022-01-30T06:10:04Z)
• Method for making multi-attribute decisions in wargames by combining intuitionistic fuzzy numbers with reinforcement learning [18.04026817707759]
  本稿では,多属性管理と強化学習を組み合わせたアルゴリズムを提案する。 エージェントの特定のルールに対する勝利率の低さと、インテリジェントなウォーゲームトレーニング中にすぐに収束できない問題を解決します。 この分野では、知的ウォーガミングのためのアルゴリズム設計が多属性意思決定と強化学習を組み合わせたのは初めてである。
  論文  参考訳（メタデータ） (2021-09-06T10:45:52Z)
• Online Multiobjective Minimax Optimization and Applications [14.699969822572308]
  本稿では,適応的な対戦相手が新しいゲームを導入する,シンプルだが汎用的なオンライン学習フレームワークを提案する。 学習者のゴールは、累積ベクトル値損失の最大座標を最小化することである。 対戦相手がまず行動を発表しなければならない設定と競合する簡単なアルゴリズムを提供する。 最適なアルゴリズムと境界を回復して、外部の後悔、内部の後悔、適応的な後悔、多集団の後悔、その後の後悔、睡眠専門家の設定における後悔の概念を最小化できます。
  論文  参考訳（メタデータ） (2021-08-09T06:52:08Z)
• Online Markov Decision Processes with Aggregate Bandit Feedback [74.85532145498742]
  本稿では,オンライン有限水平マルコフ決定過程の新たな変種について検討する。 各エピソードにおいて、学習者は、エピソードの選択した方針によって実現された軌道に沿って蓄積された損失を被り、総括的盗聴フィードバックを観察する。 我々の主な結果は計算効率のよいアルゴリズムで、$O(sqrtK)$ regret for this set, where $K$ is the number of episodes。
  論文  参考訳（メタデータ） (2021-01-31T16:49:07Z)
• Upper Confidence Bounds for Combining Stochastic Bandits [52.10197476419621]
  バンディットアルゴリズムを結合する簡単な手法を提案する。 私たちのアプローチは、個々のbanditアルゴリズムのそれぞれを、より高いレベルのn$-armed bandit問題のアームとして扱う"meta-ucb"手順に基づいています。
  論文  参考訳（メタデータ） (2020-12-24T05:36:29Z)
• Learning to Play Sequential Games versus Unknown Opponents [93.8672371143881]
  学習者が最初にプレーするゲームと、選択した行動に反応する相手との連続的なゲームについて考察する。 対戦相手の対戦相手列と対戦する際,学習者に対して新しいアルゴリズムを提案する。 我々の結果には、相手の反応の正則性に依存するアルゴリズムの後悔の保証が含まれている。
  論文  参考訳（メタデータ） (2020-07-10T09:33:05Z)
• Efficient exploration of zero-sum stochastic games [83.28949556413717]
  ゲームプレイを通じて,ゲームの記述を明示せず,託宣のみにアクセス可能な,重要で一般的なゲーム解決環境について検討する。 限られたデュレーション学習フェーズにおいて、アルゴリズムは両方のプレイヤーのアクションを制御し、ゲームを学習し、それをうまくプレイする方法を学習する。 私たちのモチベーションは、クエリされた戦略プロファイルの支払いを評価するのにコストがかかる状況において、利用可能性の低い戦略を迅速に学習することにあります。
  論文  参考訳（メタデータ） (2020-02-24T20:30:38Z)

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

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。