論文の概要: Online Learning in Budget-Constrained Dynamic Colonel Blotto Games

• arxiv url: http://arxiv.org/abs/2103.12833v4
• Date: Mon, 8 May 2023 19:45:41 GMT
• ステータス: 処理完了
• システム内更新日: 2023-05-10 20:56:51.243339
• Title: Online Learning in Budget-Constrained Dynamic Colonel Blotto Games
• Title（参考訳）: 予算制約付き動的大佐ブロットゲームにおけるオンライン学習
• Authors: Vincent Leon, S. Rasoul Etesami
• Abstract要約: ブロット大佐ゲーム (CBG) を用いて, 動的環境下での限られた資源の戦略的割り当てについて検討する。 我々は,経路計画問題に対する特別な帯域幅アルゴリズムと,予算制約に対処するknapsackアルゴリズムを組み合わせた効率的なアルゴリズムを考案した。
• 参考スコア（独自算出の注目度）: 2.132096006921048
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In this paper, we study the strategic allocation of limited resources using a Colonel Blotto game (CBG) under a dynamic setting and analyze the problem using an online learning approach. In this model, one of the players is a learner who has limited troops to allocate over a finite time horizon, and the other player is an adversary. In each round, the learner plays a one-shot Colonel Blotto game with the adversary and strategically determines the allocation of troops among battlefields based on past observations. The adversary chooses its allocation action randomly from some fixed distribution that is unknown to the learner. The learner's objective is to minimize its regret, which is the difference between the cumulative reward of the best mixed strategy and the realized cumulative reward by following a learning algorithm while not violating the budget constraint. The learning in dynamic CBG is analyzed under the framework of combinatorial bandits and bandits with knapsacks. We first convert the budget-constrained dynamic CBG to a path planning problem on a directed graph. We then devise an efficient algorithm that combines a special combinatorial bandit algorithm for path planning problem and a bandits with knapsack algorithm to cope with the budget constraint. The theoretical analysis shows that the learner's regret is bounded by a term sublinear in time horizon and polynomial in other parameters. Finally, we justify our theoretical results by carrying out simulations for various scenarios.
• Abstract（参考訳）: 本稿では,Blotto大佐のゲーム(CBG)を用いて,限られた資源の戦略的割り当てを動的に検討し,オンライン学習手法を用いて問題を解析する。 このモデルでは、プレイヤーの1人は有限時間地平線上に配置する限られた兵力を持つ学習者であり、もう1人のプレイヤーは敵である。 各ラウンドで、学習者は敵と一発のブロット大佐の試合を行い、過去の観測に基づいて戦場における部隊の配置を戦略的に決定する。 敵は、学習者に未知の固定分布からランダムにその割当動作を選択する。 学習者の目的はその後悔を最小限に抑えることであり、これは最高の混合戦略の累積報酬と、予算制約に違反することなく学習アルゴリズムに従うことによって実現された累積報酬との違いである。 動的CBGの学習は、knapsacksと組み合わせたバンドイットとバンドイットの枠組みの下で解析される。 まず、予算制約付き動的CBGを有向グラフ上の経路計画問題に変換する。 そこで我々は,経路計画問題に対する特別な組合せ帯域幅アルゴリズムと,予算制約に対処するknapsackアルゴリズムを組み合わせた効率的なアルゴリズムを考案した。 理論的解析により、学習者の後悔は時間軸のサブ線形項と他のパラメータの多項式によって境界づけられていることが示された。 最後に,様々なシナリオのシミュレーションを行うことで理論的結果を正当化する。

関連論文リスト

• 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)

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

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