論文の概要: Decentralized Randomly Distributed Multi-agent Multi-armed Bandit with
Heterogeneous Rewards
- arxiv url: http://arxiv.org/abs/2306.05579v1
- Date: Thu, 8 Jun 2023 22:37:24 GMT
- ステータス: 処理完了
- システム内更新日: 2023-06-12 15:28:06.219553
- Title: Decentralized Randomly Distributed Multi-agent Multi-armed Bandit with
Heterogeneous Rewards
- Title（参考訳）: 不均一リワードを有する分散ランダム分散マルチエージェントマルチアームバンド
- Authors: Mengfan Xu and Diego Klabjan
- Abstract要約: 環境によって提供される時間依存ランダムグラフによって複数のクライアントが接続される分散マルチエージェントマルチアームバンディット問題について検討する。
目標は、コラボレーションを通じてシステム全体の後悔を最小化することです。
- 参考スコア（独自算出の注目度）: 22.17126026244685
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study a decentralized multi-agent multi-armed bandit problem in which
multiple clients are connected by time dependent random graphs provided by an
environment. The reward distributions of each arm vary across clients and
rewards are generated independently over time by an environment based on
distributions that include both sub-exponential and sub-gaussian distributions.
Each client pulls an arm and communicates with neighbors based on the graph
provided by the environment. The goal is to minimize the overall regret of the
entire system through collaborations. To this end, we introduce a novel
algorithmic framework, which first provides robust simulation methods for
generating random graphs using rapidly mixing Markov chains or the random graph
model, and then combines an averaging-based consensus approach with a newly
proposed weighting technique and the upper confidence bound to deliver a
UCB-type solution. Our algorithms account for the randomness in the graphs,
removing the conventional doubly stochasticity assumption, and only require the
knowledge of the number of clients at initialization. We derive optimal
instance-dependent regret upper bounds of order $\log{T}$ in both sub-gaussian
and sub-exponential environments, and a nearly optimal mean-gap independent
regret upper bound of order $\sqrt{T}\log T$ up to a $\log T$ factor.
Importantly, our regret bounds hold with high probability and capture graph
randomness, whereas prior works consider expected regret under assumptions and
require more stringent reward distributions.
- Abstract（参考訳）: 環境によって提供される時間依存ランダムグラフによって複数のクライアントが接続される分散マルチエージェントマルチアームバンディット問題について検討する。
各アームの報酬分布はクライアント間で異なり、報酬はサブ指数分布とサブゲージ分布の両方を含む分布に基づく環境によって時間とともに独立に生成される。
各クライアントはarmをプルし、環境が提供するグラフに基づいて隣人と通信する。
目標は、コラボレーションを通じてシステム全体の後悔を最小化することです。
そこで,本研究では,マルコフ連鎖あるいはランダムグラフモデルを用いて,ランダムグラフを生成するためのロバストなシミュレーション手法を提供し,平均値に基づくコンセンサスアプローチと,新たに提案する重み付け手法と,ucb型ソリューションを提供するための上位信頼度を組み合わせたアルゴリズムフレームワークを提案する。
我々のアルゴリズムはグラフのランダム性を考慮し、従来の2倍確率性仮定を取り除き、初期化時のクライアント数の知識のみを必要とする。
我々は、サブゲージ環境とサブ指数環境の両方において、最適なインスタンス依存の後悔の上限である$\log{t}$を導出し、ほぼ最適な平均ギャップ独立な後悔の上限である$\sqrt{t}\log t$を$\log t$ファクターまで導出する。
重要なのは、私たちの後悔の境界は高い確率とグラフのランダム性を持ち、先行研究は想定された後悔を考慮し、より厳密な報酬分布を必要とする。
関連論文リスト
- DASA: Delay-Adaptive Multi-Agent Stochastic Approximation [64.32538247395627]
我々は,N$エージェントが並列に動作し,中央サーバと通信することで,一般的な近似問題を高速化することを目的とした設定を考える。
遅延とストラグラーの効果を軽減するために,マルチエージェント近似のための遅延適応アルゴリズムである textttDASA を提案する。
論文 参考訳（メタデータ） (2024-03-25T22:49:56Z) - Order-Optimal Regret in Distributed Kernel Bandits using Uniform
Sampling with Shared Randomness [9.731329071569018]
我々はN$エージェントが未知の報酬関数を協調的に最大化する分散カーネルの帯域を考える。
我々は,通信コストが$N$と$T$に比例する,最適な後悔順序を達成するアルゴリズムを開発した。
論文 参考訳（メタデータ） (2024-02-20T17:49:10Z) - Stochastic Approximation Approaches to Group Distributionally Robust Optimization and Beyond [89.72693227960274]
本稿では,グループ分散ロバスト最適化 (GDRO) を,$m$以上の異なる分布をうまく処理するモデルを学習する目的で検討する。
各ラウンドのサンプル数を$m$から1に抑えるため、GDROを2人でプレイするゲームとして、一方のプレイヤーが実行し、他方のプレイヤーが非公開のマルチアームバンディットのオンラインアルゴリズムを実行する。
第2のシナリオでは、最大リスクではなく、平均的最上位k$リスクを最適化し、分散の影響を軽減することを提案する。
論文 参考訳（メタデータ） (2023-02-18T09:24:15Z) - Complexity Analysis of a Countable-armed Bandit Problem [9.163501953373068]
遊びの地平線上で期待される累積的後悔を最小限に抑えるという古典的問題を考察する。
我々は、$K=2$のとき、$mathcalOleft(log n right)$の率最適有限時間インスタンス依存後悔を実現するアルゴリズムを提案する。
問題に対する後悔の順序と複雑さは、古典的MAB問題と非常に類似していることを示しているが、アルゴリズム設計における性能境界の特性と健全な側面は、後者とはかなり異なる。
論文 参考訳（メタデータ） (2023-01-18T00:53:46Z) - Beyond the Best: Estimating Distribution Functionals in Infinite-Armed
Bandits [40.71199236098642]
無限武装バンディット問題では、各アームの平均報酬は未知の分布からサンプリングされる。
我々は、最大以上の分布関数の一般的なクラスを検討し、オフラインとオンラインの両方で統一されたメタアルゴリズムを提案する。
論文 参考訳（メタデータ） (2022-11-01T18:20:10Z) - Finite-Time Regret of Thompson Sampling Algorithms for Exponential
Family Multi-Armed Bandits [88.21288104408556]
本研究では,指数関数族バンドイットに対するトンプソンサンプリング (TS) アルゴリズムの遺残について検討する。
最適な腕の過小評価を避けるために,新しいサンプリング分布を用いたトンプソンサンプリング(Expulli)を提案する。
論文 参考訳（メタデータ） (2022-06-07T18:08:21Z) - Rate-Distortion Theoretic Bounds on Generalization Error for Distributed
Learning [9.00236182523638]
本稿では,統計的分散学習アルゴリズムの一般化誤差の新しい上限を確立するために,レート歪み理論のツールを用いる。
境界は各クライアントのアルゴリズムの圧縮性に依存し、他のクライアントのアルゴリズムは圧縮されない。
論文 参考訳（メタデータ） (2022-06-06T13:21:52Z) - DQMIX: A Distributional Perspective on Multi-Agent Reinforcement
Learning [122.47938710284784]
協調的マルチエージェントタスクでは、エージェントのチームがアクションを取り、報酬を受け取り、次の状態を観察し、環境と共同で対話する。
既存の価値に基づく多エージェント強化学習手法のほとんどは、個々のQ値とグローバルQ値の期待をモデル化するのみである。
論文 参考訳（メタデータ） (2022-02-21T11:28:00Z) - Optimal Clustering with Bandit Feedback [57.672609011609886]
本稿では,バンディットフィードバックを用いたオンラインクラスタリングの問題点について考察する。
これは、NPハード重み付きクラスタリング問題をサブルーチンとして解決する必要性を回避するための、シーケンシャルなテストのための新しい停止規則を含む。
合成および実世界のデータセットの広範なシミュレーションを通して、BOCの性能は下界と一致し、非適応的ベースラインアルゴリズムよりも大幅に優れることを示す。
論文 参考訳（メタデータ） (2022-02-09T06:05:05Z) - Robust Learning of Optimal Auctions [84.13356290199603]
本研究では、入札者の評価値のサンプルを逆向きに破損させたり、逆向きに歪んだ分布から引き出すことができる場合に、サンプルから収益-最適マルチバイダオークションを学習する問題について検討する。
我々は,コルモゴロフ-スミルノフ距離における元の分布に対して$alpha$-closeの「全ての真の分布」に対して,収入がほぼ同時に最適であるメカニズムを学習できる新しいアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-07-13T17:37:21Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。