論文の概要: Bidding Games on Markov Decision Processes with Quantitative Reachability Objectives

• arxiv url: http://arxiv.org/abs/2412.19609v1
• Date: Fri, 27 Dec 2024 12:10:00 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-12-30 17:25:15.781177
• Title: Bidding Games on Markov Decision Processes with Quantitative Reachability Objectives
• Title（参考訳）: 定量的到達目標を持つマルコフ決定過程のバイディングゲーム
• Authors: Guy Avni, Martin Kurečka, Kaushik Mallik, Petr Novotný, Suman Sadhukhan,
• Abstract要約: 本研究では,環境不確かさとエージェント間のオークションベースの相互作用を組み合わせた新しいグラフゲーム群について検討する。 我々は、一般のMDPに対して、しきい値と最適なポリシーを近似するバリューイットアルゴリズムを考案する。 しきい値の発見は、単純な確率的なゲームを解くのと同じくらい難しいことを示します。
• 参考スコア（独自算出の注目度）: 3.4486432774139355
• License:
• Abstract: Graph games are fundamental in strategic reasoning of multi-agent systems and their environments. We study a new family of graph games which combine stochastic environmental uncertainties and auction-based interactions among the agents, formalized as bidding games on (finite) Markov decision processes (MDP). Normally, on MDPs, a single decision-maker chooses a sequence of actions, producing a probability distribution over infinite paths. In bidding games on MDPs, two players -- called the reachability and safety players -- bid for the privilege of choosing the next action at each step. The reachability player's goal is to maximize the probability of reaching a target vertex, whereas the safety player's goal is to minimize it. These games generalize traditional bidding games on graphs, and the existing analysis techniques do not extend. For instance, the central property of traditional bidding games is the existence of a threshold budget, which is a necessary and sufficient budget to guarantee winning for the reachability player. For MDPs, the threshold becomes a relation between the budgets and probabilities of reaching the target. We devise value-iteration algorithms that approximate thresholds and optimal policies for general MDPs, and compute the exact solutions for acyclic MDPs, and show that finding thresholds is at least as hard as solving simple-stochastic games.
• Abstract（参考訳）: グラフゲームは、マルチエージェントシステムとその環境の戦略的推論において基本的なものである。 我々は,マルコフ決定過程(MDP)上での入札ゲームとして形式化された,確率的環境不確実性とエージェント間のオークションベースの相互作用を組み合わせた新しいグラフゲーム群について検討した。 通常、MDPでは、単一の意思決定者が一連の行動を選択し、無限経路上の確率分布を生成する。 MDPの入札ゲームでは、リーチビリティとセーフティプレーヤーと呼ばれる2人のプレーヤーが、各ステップで次のアクションを選択する特権を競う。 リーチビリティプレイヤーのゴールは目標頂点に達する確率を最大化することであり、セーフティプレイヤーのゴールは最小化することである。 これらのゲームはグラフ上の従来の入札ゲームを一般化し、既存の分析手法は拡張しない。 例えば、伝統的な入札ゲームの中心的な性質は、リーチビリティプレーヤーの勝利を保証するために必要な十分な予算である閾値予算の存在である。 MDPの場合、閾値は予算と目標に到達する確率の間の関係となる。 我々は、一般のMDPに対して近似しきい値と最適ポリシーを考案し、非巡回MDPの正確な解を計算し、そのしきい値の発見は、単純な確率的なゲームを解くのと同じくらい難しいことを示す。

関連論文リスト

• Optimistic Policy Gradient in Multi-Player Markov Games with a Single Controller: Convergence Beyond the Minty Property [89.96815099996132]
  単一コントローラを用いたマルチプレイヤーゲームにおいて,楽観的なポリシー勾配手法を特徴付ける新しいフレームワークを開発した。 我々のアプローチは、我々が導入する古典的なミニティの自然一般化に依存しており、マルコフゲームを超えてさらなる応用が期待できる。
  論文  参考訳（メタデータ） (2023-12-19T11:34:10Z)
• Cooperation or Competition: Avoiding Player Domination for Multi-Target Robustness via Adaptive Budgets [76.20705291443208]
  我々は、敵攻撃を、異なるプレイヤーがパラメータ更新の合同方向で合意に達するために交渉する交渉ゲームであると見なしている。 我々は、プレイヤーの優位性を避けるために、異なる敵の予算を調整する新しいフレームワークを設計する。 標準ベンチマークの実験では、提案したフレームワークを既存のアプローチに適用することで、マルチターゲットロバスト性が大幅に向上することが示された。
  論文  参考訳（メタデータ） (2023-06-27T14:02:10Z)
• Multi-Target Multiplicity: Flexibility and Fairness in Target Specification under Resource Constraints [76.84999501420938]
  対象の選択が個人の結果にどのように影響するかを評価するための概念的および計算的枠組みを導入する。 目的変数選択から生じる多重度は, 1つのターゲットのほぼ最適モデルから生じるものよりも大きいことが示される。
  論文  参考訳（メタデータ） (2023-06-23T18:57:14Z)
• Efficiently Computing Nash Equilibria in Adversarial Team Markov Games [19.717850955051837]
  我々は,同じプレイヤーが対戦相手と競合するゲームのクラスを紹介する。 この設定により、ゼロサムマルコフゲームの可能性ゲームの統一処理が可能になる。 我々の主な貢献は、対戦チームマルコフゲームにおける固定的な$epsilon$-approximate Nash平衡を計算するための最初のアルゴリズムである。
  論文  参考訳（メタデータ） (2022-08-03T16:41:01Z)
• Provably Efficient Fictitious Play Policy Optimization for Zero-Sum Markov Games with Structured Transitions [145.54544979467872]
  本研究では,ゼロサムマルコフゲームに対して,構造的だが未知の遷移を伴う架空のプレイポリシー最適化アルゴリズムを提案し,解析する。 我々は、2年制の競争ゲームシナリオで、$K$のエピソードに続き、$widetildemathcalO(sqrtK)$ regret boundsを証明した。 提案アルゴリズムは,アッパー信頼境界(UCB)型最適化と,同時政策最適化の範囲内での架空のプレイの組み合わせを特徴とする。
  論文  参考訳（メタデータ） (2022-07-25T18:29:16Z)
• A unified stochastic approximation framework for learning in games [82.74514886461257]
  ゲームにおける学習の長期的挙動(連続的・有限的)を解析するためのフレキシブルな近似フレームワークを開発する。 提案する分析テンプレートには,勾配に基づく手法,有限ゲームでの学習のための指数的/乗算的重み付け,楽観的および帯域的変異など,幅広い一般的な学習アルゴリズムが組み込まれている。
  論文  参考訳（メタデータ） (2022-06-08T14:30:38Z)
• Improving Bidding and Playing Strategies in the Trick-Taking game Wizard using Deep Q-Networks [0.0]
  別々の入札・プレイフェーズを持つトリックテイクゲームWizardは、2つのインターリーブされた部分的に観測可能なマルコフ決定プロセス(POMDP)によってモデル化される。 ディープQネットワークワークス(DQN)は、非定常環境の課題に対処できる自己改善エージェントの強化に使用される。 訓練されたDQNエージェントは、ランダムなベースラインと規則に基づく非対称性の両方を残して、自己プレイの66%から87%の精度を達成する。
  論文  参考訳（メタデータ） (2022-05-27T08:59:42Z)
• Solving Graph-based Public Good Games with Tree Search and Imitation Learning [4.499055111059408]
  我々は,自己関心エージェントのネットワークをグローバルに捉えた中心的プランナーの視点と,ベストショットの公共商品ゲームにおける所望の資産の最大化を目標とする。 この既知のNP完全問題に対する既存のアルゴリズムは、社会福祉以外の基準に最適化できない準最適解を見つける。 提案手法は,グラフの平衡と最大独立集合(mIS)構造特性の対応性を直接活用する。
  論文  参考訳（メタデータ） (2021-06-12T12:46:44Z)
• 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)
• Equilibria for Games with Combined Qualitative and Quantitative Objectives [15.590197778287616]
  我々は,各プレイヤーが独立して戦略的に行動することが想定されるプロセスである並行ゲームについて研究する。 我々の主な結果は、そのようなゲームにおける厳密なエプシロン・ナッシュ均衡の存在を決定することは2ExpTime完全であるということである。
  論文  参考訳（メタデータ） (2020-08-13T01:56:24Z)
• Learning Zero-Sum Simultaneous-Move Markov Games Using Function Approximation and Correlated Equilibrium [116.56359444619441]
  両プレイヤーのゼロサム有限ホライゾンマルコフゲームに対する効率の良い強化学習アルゴリズムを開発した。 オフライン環境では、両プレイヤーを制御し、双対性ギャップを最小化してナッシュ平衡を求める。 オンライン環境では、任意の相手と対戦する1人のプレイヤーを制御し、後悔を最小限に抑える。
  論文  参考訳（メタデータ） (2020-02-17T17:04:16Z)

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

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