論文の概要: Cooperative Thresholded Lasso for Sparse Linear Bandit
- arxiv url: http://arxiv.org/abs/2305.19161v1
- Date: Tue, 30 May 2023 16:05:44 GMT
- ステータス: 処理完了
- システム内更新日: 2023-05-31 15:15:27.853090
- Title: Cooperative Thresholded Lasso for Sparse Linear Bandit
- Title（参考訳）: Sparse Linear Bandit に対するLasso 留置術
- Authors: Haniyeh Barghi, Xiaotong Cheng, Setareh Maghsudi
- Abstract要約: 本稿では,マルチエージェント・スパース文脈線形帯域問題に対処する新しい手法を提案する。
疎線形帯域における行単位の分散データに対処する最初のアルゴリズムである。
後悔を最小限に抑えるために効率的な特徴抽出が重要となる高次元マルチエージェント問題に適用可能である。
- 参考スコア（独自算出の注目度）: 6.52540785559241
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We present a novel approach to address the multi-agent sparse contextual
linear bandit problem, in which the feature vectors have a high dimension $d$
whereas the reward function depends on only a limited set of features -
precisely $s_0 \ll d$. Furthermore, the learning follows under
information-sharing constraints. The proposed method employs Lasso regression
for dimension reduction, allowing each agent to independently estimate an
approximate set of main dimensions and share that information with others
depending on the network's structure. The information is then aggregated
through a specific process and shared with all agents. Each agent then resolves
the problem with ridge regression focusing solely on the extracted dimensions.
We represent algorithms for both a star-shaped network and a peer-to-peer
network. The approaches effectively reduce communication costs while ensuring
minimal cumulative regret per agent. Theoretically, we show that our proposed
methods have a regret bound of order $\mathcal{O}(s_0 \log d + s_0 \sqrt{T})$
with high probability, where $T$ is the time horizon. To our best knowledge, it
is the first algorithm that tackles row-wise distributed data in sparse linear
bandits, achieving comparable performance compared to the state-of-the-art
single and multi-agent methods. Besides, it is widely applicable to
high-dimensional multi-agent problems where efficient feature extraction is
critical for minimizing regret. To validate the effectiveness of our approach,
we present experimental results on both synthetic and real-world datasets.
- Abstract（参考訳）: 本稿では,特徴ベクトルが高次元$d$を持つマルチエージェントな文脈線形バンディット問題に対処するための新しい手法を提案する。
さらに、学習は情報共有の制約に従う。
提案手法では,主次元の近似集合を各エージェントが独立に推定し,その情報をネットワーク構造に応じて他のエージェントと共有できるラッソ回帰を用いた。
情報は特定のプロセスを通じて集約され、すべてのエージェントと共有される。
それぞれのエージェントは、抽出された次元にのみ焦点をあてたリッジ回帰で問題を解く。
我々は星型ネットワークとピアツーピアネットワークの両方のアルゴリズムを表現する。
このアプローチは、エージェントごとの累積後悔を最小限に抑えつつ、通信コストを効果的に削減する。
理論的には、提案手法は高い確率で$t$ が時間軸であるような順序 $\mathcal{o}(s_0 \log d + s_0 \sqrt{t})$ を持つ。
私たちの知る限りでは、sparse linear banditsで行毎の分散データを扱う最初のアルゴリズムで、最先端のシングルエージェントとマルチエージェントメソッドと同等のパフォーマンスを実現しています。
さらに, 効率的な特徴抽出が重要となる高次元マルチエージェント問題にも適用可能である。
本手法の有効性を検証するために,合成データと実世界データの両方について実験結果を示す。
関連論文リスト
- Cooperative Multi-Agent Constrained Stochastic Linear Bandits [2.099922236065961]
N$エージェントのネットワークがローカルに通信し、期待されるコストを所定の閾値$tau$で保持しながら、全体的な後悔を最小限に抑える。
我々は、textitMA-OPLBと呼ばれる安全な分散上信頼度有界アルゴリズムを提案し、そのT$ラウンドの後悔に基づく高い確率を確立する。
我々の後悔の限界は次数$ MathcalOleft(fracdtau-c_0fraclog(NT)2sqrtNsqrtTlog (1/|lambda|)であることを示す。
論文 参考訳（メタデータ） (2024-10-22T19:34:53Z) - Minimax and Communication-Efficient Distributed Best Subset Selection with Oracle Property [0.358439716487063]
大規模データの爆発はシングルマシンシステムの処理能力を上回っている。
分散推論への伝統的なアプローチは、高次元データセットにおいて真の疎性を達成するのにしばしば苦労する。
そこで本稿では,これらの問題に対処する2段階分散ベストサブセット選択アルゴリズムを提案する。
論文 参考訳（メタデータ） (2024-08-30T13:22:08Z) - Federated Combinatorial Multi-Agent Multi-Armed Bandits [79.1700188160944]
本稿では,Banditを用いたオンライン最適化に適したフェデレーション学習フレームワークを提案する。
この設定では、エージェントのアームサブセットは、個々のアーム情報にアクセスせずにこれらのサブセットに対するノイズの多い報酬を観察し、特定の間隔で協力して情報を共有することができる。
論文 参考訳（メタデータ） (2024-05-09T17:40:09Z) - Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic
Shortest Path [80.60592344361073]
線形混合遷移カーネルを用いた最短経路(SSP)問題について検討する。
エージェントは繰り返し環境と対話し、累積コストを最小化しながら特定の目標状態に到達する。
既存の作業は、イテレーションコスト関数の厳密な下限や、最適ポリシーに対する期待長の上限を仮定することが多い。
論文 参考訳（メタデータ） (2024-02-14T07:52:00Z) - Scalable Primal-Dual Actor-Critic Method for Safe Multi-Agent RL with
General Utilities [12.104551746465932]
安全マルチエージェント強化学習について検討し、エージェントはそれぞれの安全制約を満たしつつ、局所的な目的の総和をまとめて最大化しようとする。
我々のアルゴリズムは、$mathcalOleft(T-2/3right)$のレートで1次定常点(FOSP)に収束する。
サンプルベースの設定では、高い確率で、我々のアルゴリズムは、$epsilon$-FOSPを達成するために$widetildemathcalOleft(epsilon-3.5right)$サンプルが必要です。
論文 参考訳（メタデータ） (2023-05-27T20:08:35Z) - Communication-Efficient Adam-Type Algorithms for Distributed Data Mining [93.50424502011626]
我々はスケッチを利用した新しい分散Adam型アルゴリズムのクラス(例:SketchedAMSGrad)を提案する。
我々の新しいアルゴリズムは、反復毎に$O(frac1sqrtnT + frac1(k/d)2 T)$の高速収束率を$O(k log(d))$の通信コストで達成する。
論文 参考訳（メタデータ） (2022-10-14T01:42:05Z) - On Reward-Free RL with Kernel and Neural Function Approximations:
Single-Agent MDP and Markov Game [140.19656665344917]
エージェントが事前に特定された報酬関数を使わずに環境を徹底的に探索することを目的とした報酬のないRL問題について検討する。
関数近似の文脈でこの問題に取り組み、強力な関数近似器を活用する。
我々は、カーネルとニューラルファンクション近似器を用いた、証明可能な効率の良い報酬なしRLアルゴリズムを確立した。
論文 参考訳（メタデータ） (2021-10-19T07:26:33Z) - Breaking the Sample Complexity Barrier to Regret-Optimal Model-Free
Reinforcement Learning [52.76230802067506]
漸進的強化学習における後悔を最小限に抑えるために,新しいモデルフリーアルゴリズムを提案する。
提案アルゴリズムは、2つのQ-ラーニングシーケンスの助けを借りて、初期設定された参照更新ルールを用いる。
初期の分散還元法の設計原理は、他のRL設定とは独立した関心を持つかもしれない。
論文 参考訳（メタデータ） (2021-10-09T21:13:48Z) - Online Sub-Sampling for Reinforcement Learning with General Function
Approximation [111.01990889581243]
本稿では,RLアルゴリズムによって収集されたデータポイントの情報取得量を測定する,効率的なオンラインサブサンプリングフレームワークを確立する。
複雑性バウンド関数クラスを持つ値ベースのメソッドの場合、$proptooperatornamepolylog(K)$ timesに対してのみポリシーを更新する必要がある。
少なくとも$Omega(K)$倍のポリシーを更新する既存のアプローチとは対照的に、当社のアプローチはポリシーの解決における最適化コールの数を劇的に削減します。
論文 参考訳（メタデータ） (2021-06-14T07:36:25Z) - Decentralized Multi-Agent Linear Bandits with Safety Constraints [31.67685495996986]
本研究では,N$エージェントのネットワークが協調して線形帯域最適化問題を解く分散線形帯域幅について検討する。
ネットワーク全体の累積的後悔を最小限に抑える完全分散アルゴリズム DLUCB を提案する。
私たちのアイデアは、より困難な、安全な盗賊の設定にもかかわらず、自然界に広まっています。
論文 参考訳（メタデータ） (2020-12-01T07:33:00Z) - An Efficient Algorithm for Cooperative Semi-Bandits [0.0]
本稿では,有名なFollow The Perturbed Leaderアルゴリズムの協調バージョンであるCoop-FTPLを紹介する。
T 時間ステップ後のアルゴリズムの期待された後悔は QT log(k)(k$alpha$ 1 /Q + m) であり、Q は総アクティベーション確率質量である。
論文 参考訳（メタデータ） (2020-10-05T07:08:26Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。