論文の概要: Learning the Expected Core of Strictly Convex Stochastic Cooperative
Games
- arxiv url: http://arxiv.org/abs/2402.07067v1
- Date: Sat, 10 Feb 2024 23:49:49 GMT
- ステータス: 処理完了
- システム内更新日: 2024-02-13 17:43:17.517857
- Title: Learning the Expected Core of Strictly Convex Stochastic Cooperative
Games
- Title(参考訳): 厳密な凸確率協調ゲームにおける期待コアの学習
- Authors: Nam Phuong Tran, The Anh Ta, Shuqing Shi, Debmalya Mandal, Yali Du,
Long Tran-Thanh
- Abstract要約: 信用割当問題としても知られるリワード割当は、経済学、工学、機械学習において重要なトピックである。
本稿では,報酬関数を未知の分布を持つランダム変数として特徴付ける協調ゲームにおける安定なアロケーション学習問題を考察する。
- 参考スコア(独自算出の注目度): 18.746089166690144
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Reward allocation, also known as the credit assignment problem, has been an
important topic in economics, engineering, and machine learning. An important
concept in credit assignment is the core, which is the set of stable
allocations where no agent has the motivation to deviate from the grand
coalition. In this paper, we consider the stable allocation learning problem of
stochastic cooperative games, where the reward function is characterised as a
random variable with an unknown distribution. Given an oracle that returns a
stochastic reward for an enquired coalition each round, our goal is to learn
the expected core, that is, the set of allocations that are stable in
expectation. Within the class of strictly convex games, we present an algorithm
named \texttt{Common-Points-Picking} that returns a stable allocation given a
polynomial number of samples, with high probability. The analysis of our
algorithm involves the development of several new results in convex geometry,
including an extension of the separation hyperplane theorem for multiple convex
sets, and may be of independent interest.
- Abstract(参考訳): 報酬の割り当ては、クレジット割り当て問題としても知られ、経済学、工学、機械学習において重要なトピックとなっている。
信用割当における重要な概念は中核であり、大連立から逸脱する動機を持つエージェントがいない安定した割当の集合である。
本稿では,確率的協調ゲームにおいて,報酬関数を未知の分布を持つランダム変数として特徴付ける安定なアロケーション学習問題を考察する。
要求された連立に対する確率的な報酬を各ラウンド毎に返すオラクルを考えると、私たちの目標は期待されたコア、すなわち期待どおりの割り当てのセットを学ぶことです。
厳密な凸ゲームのクラス内では、高確率で多項式数の標本が与えられたときの安定なアロケーションを返す「texttt{Common-Points-Picking}」というアルゴリズムを提案する。
このアルゴリズムの解析は、複数の凸集合に対する分離超平面定理の拡張を含む凸幾何学におけるいくつかの新しい結果の開発を伴い、独立した興味を持つかもしれない。
関連論文リスト
- Shapley Value Based Multi-Agent Reinforcement Learning: Theory, Method
and Its Application to Energy Network [7.50196317304035]
本論は,協調ゲーム理論によるマルチエージェント強化学習における信用割当の基礎を考察する。
まず,コラボレーティブゲーム理論において,コンベックスゲーム(convex game)と呼ばれるゲームモデルと,Shapley値と呼ばれるペイオフ分配スキームを拡張した。
Markov Shapley値に基づいて,SHAQ,SQDDPG,SPOという3つのマルチエージェント強化学習アルゴリズムを提案する。
論文 参考訳(メタデータ) (2024-02-23T13:43:15Z) - Approximation algorithms for noncommutative constraint satisfaction
problems [0.0]
我々は制約満足度問題(CSP)の作用素、あるいは非可換変量について研究する。
非可換なCSPに対する近似アルゴリズムを設計するためのフレームワークを提案する。
この研究は、より広い非可換 CSP のクラスに対する近似比を確立する最初のものである。
論文 参考訳(メタデータ) (2023-12-28T01:22:27Z) - Value-Distributional Model-Based Reinforcement Learning [63.32053223422317]
政策の長期的業績に関する不確実性の定量化は、シーケンシャルな意思決定タスクを解決するために重要である。
モデルに基づくベイズ強化学習の観点から問題を考察する。
本稿では,値分布関数を学習するモデルに基づくアルゴリズムであるEpicemic Quantile-Regression(EQR)を提案する。
論文 参考訳(メタデータ) (2023-08-12T14:59:19Z) - Stochastic Saddle Point Problems with Decision-Dependent Distributions [0.6091702876917279]
本稿では,静的設定と時間変化設定の両方において決定に依存するサドル点問題に焦点をあてる。
定常ミニマックス問題に対するサドル点である平衡点の概念を導入する。
原始双対アルゴリズムは、同様の方法でサドル点に収束することを示す。
論文 参考訳(メタデータ) (2022-01-07T03:36:41Z) - Lattice-Based Methods Surpass Sum-of-Squares in Clustering [98.46302040220395]
クラスタリングは教師なし学習における基本的なプリミティブである。
最近の研究は、低次手法のクラスに対する低い境界を確立している。
意外なことに、この特定のクラスタリングモデルのtextitdoesは、統計的-計算的ギャップを示さない。
論文 参考訳(メタデータ) (2021-12-07T18:50:17Z) - Private Robust Estimation by Stabilizing Convex Relaxations [22.513117502159922]
$(epsilon, delta)$-differentially private (DP)
$(epsilon, delta)$-differentially private (DP)
$(epsilon, delta)$-differentially private (DP)
論文 参考訳(メタデータ) (2021-12-07T07:47:37Z) - Anti-Concentrated Confidence Bonuses for Scalable Exploration [57.91943847134011]
固有の報酬は、探検と探検のトレードオフを扱う上で中心的な役割を果たす。
楕円ボーナスを効率的に近似するためのエンファンティ集中型信頼境界を導入する。
我々は,Atariベンチマーク上での現代固有の報酬と競合する,深層強化学習のための実用的な変種を開発する。
論文 参考訳(メタデータ) (2021-10-21T15:25:15Z) - Gradient play in stochastic games: stationary points, convergence, and
sample complexity [6.97785632069611]
ゲーム用グラデーションプレイアルゴリズム(SG)の性能について検討する。
この設定では、ナッシュ均衡(NE)と1次定常ポリシーが等価であることを示す。
マルコフポテンシャルゲームと呼ばれるSGのサブクラスに対して、サンプルベース強化学習アルゴリズムを設計する。
論文 参考訳(メタデータ) (2021-06-01T03:03:45Z) - Learning while Respecting Privacy and Robustness to Distributional
Uncertainties and Adversarial Data [66.78671826743884]
分散ロバストな最適化フレームワークはパラメトリックモデルのトレーニングのために検討されている。
目的は、逆操作された入力データに対して頑健なトレーニングモデルを提供することである。
提案されたアルゴリズムは、オーバーヘッドがほとんどない堅牢性を提供する。
論文 参考訳(メタデータ) (2020-07-07T18:25:25Z) - Stochastic Saddle-Point Optimization for Wasserstein Barycenters [69.68068088508505]
オンラインデータストリームによって生成される有限個の点からなるランダムな確率測度に対する人口推定バリセンタ問題を考察する。
本稿では,この問題の構造を用いて,凸凹型サドル点再構成を行う。
ランダム確率測度の分布が離散的な場合、最適化アルゴリズムを提案し、その複雑性を推定する。
論文 参考訳(メタデータ) (2020-06-11T19:40:38Z) - Best Arm Identification for Cascading Bandits in the Fixed Confidence
Setting [81.70513857417106]
CascadeBAIを設計し、分析する。これは、$K$アイテムのベストセットを見つけるアルゴリズムである。
CascadeBAIの時間的複雑さの上限は、決定的な分析課題を克服することによって導かれる。
その結果,カスケードBAIの性能は,時間的複雑性の低い境界の導出により,いくつかの実践的状況において最適であることが示唆された。
論文 参考訳(メタデータ) (2020-01-23T16:47:52Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。