論文の概要: Multi-User Reinforcement Learning with Low Rank Rewards
- arxiv url: http://arxiv.org/abs/2210.05355v1
- Date: Tue, 11 Oct 2022 11:36:21 GMT
- ステータス: 処理完了
- システム内更新日: 2022-10-12 17:40:43.656398
- Title: Multi-User Reinforcement Learning with Low Rank Rewards
- Title(参考訳): 低ランク報酬によるマルチユーザ強化学習
- Authors: Naman Agarwal, Prateek Jain, Suhas Kowshik, Dheeraj Nagaraj and
Praneeth Netrapalli
- Abstract要約: 我々の主な貢献は、N$ユーザ固有のMDPと協調して報酬を探索するアルゴリズムである。
N$が大きめでランクが一定であれば、MDPあたりのサンプルの複雑さは状態空間のサイズに対数的に依存する。
- 参考スコア(独自算出の注目度): 41.15103860230677
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: In this work, we consider the problem of collaborative multi-user
reinforcement learning. In this setting there are multiple users with the same
state-action space and transition probabilities but with different rewards.
Under the assumption that the reward matrix of the $N$ users has a low-rank
structure -- a standard and practically successful assumption in the offline
collaborative filtering setting -- the question is can we design algorithms
with significantly lower sample complexity compared to the ones that learn the
MDP individually for each user. Our main contribution is an algorithm which
explores rewards collaboratively with $N$ user-specific MDPs and can learn
rewards efficiently in two key settings: tabular MDPs and linear MDPs. When $N$
is large and the rank is constant, the sample complexity per MDP depends
logarithmically over the size of the state-space, which represents an
exponential reduction (in the state-space size) when compared to the standard
``non-collaborative'' algorithms.
- Abstract(参考訳): 本稿では,協調型マルチユーザ強化学習の課題について考察する。
この設定では、複数のユーザが同じ状態アクションスペースと遷移確率を持っているが、報酬が異なる。
N$ユーザの報酬行列がローランク構造 -- オフラインの協調フィルタリング設定における標準的かつ実用的な仮定 -- を持っているという仮定の下で、疑問は、各ユーザについてMDPを個別に学習するよりも、サンプルの複雑さが著しく低いアルゴリズムを設計できるかどうかである。
我々の主な貢献は、N$のユーザ固有のMDPと協調して報酬を探索し、2つの主要な設定で報酬を効率的に学習するアルゴリズムである。
N$が大きすぎてランクが一定である場合、MDPあたりのサンプルの複雑さは、標準の「非協調的」アルゴリズムと比較して指数関数的な減少(状態空間サイズ)を表す状態空間のサイズに対数的に依存する。
関連論文リスト
- Provable Benefits of Multi-task RL under Non-Markovian Decision Making
Processes [56.714690083118406]
マルコフ決定過程 (MDP) 下でのマルチタスク強化学習 (RL) において, 共有潜在構造の存在は, シングルタスクRLと比較して, サンプル効率に有意な利益をもたらすことが示されている。
このような利点が、部分的に観測可能なMDP(POMDP)やより一般的な予測状態表現(PSR)といった、より一般的なシーケンシャルな意思決定問題にまで拡張できるかどうかを検討する。
提案手法は,全てのPSRに対してほぼ最適ポリシーを求めるための,証明可能なアルゴリズム UMT-PSR を提案し,PSR の合同モデルクラスが有するマルチタスク学習の利点が示されることを示す。
論文 参考訳(メタデータ) (2023-10-20T14:50:28Z) - User-Level Differential Privacy With Few Examples Per User [73.81862394073308]
サンプルスカース方式では,各ユーザが少数のサンプルしか持たないため,以下の結果が得られる。
近似DPについては,任意の項目レベルDPアルゴリズムをユーザレベルDPアルゴリズムに汎用変換する。
ユーザレベル設定に指数的機構(McSherry, Talwar FOCS 2007)を適用するための簡単な手法を提案する。
論文 参考訳(メタデータ) (2023-09-21T21:51:55Z) - Improved Sample Complexity for Reward-free Reinforcement Learning under
Low-rank MDPs [43.53286390357673]
本稿では,低ランクMDPモデルによる報酬なし強化学習に焦点を当てた。
我々はまず、低ランクのMDPの下での任意のアルゴリズムに対して、最初の既知のサンプル複雑性の低い境界を提供する。
次に、RAFFLEと呼ばれる新しいモデルベースアルゴリズムを提案し、$epsilon$-optimal Policyを見つけ、$epsilon$-accurate system IDを実現できることを示す。
論文 参考訳(メタデータ) (2023-03-20T04:39:39Z) - (Private) Kernelized Bandits with Distributed Biased Feedback [13.312928989951505]
分散バイアスフィードバックを用いたカーネル化された帯域幅について検討する。
Emphdistributed phase-then-batch-based elimination (textttDPBE)アルゴリズムを提案する。
textttDPBE は $tildeO(T1-alpha/2+sqrtgamma_TT)$ のサブ線形後悔を実現する。
論文 参考訳(メタデータ) (2023-01-28T02:30:15Z) - The Minority Matters: A Diversity-Promoting Collaborative Metric
Learning Algorithm [154.47590401735323]
CML(Collaborative Metric Learning)は、リコメンデーションシステムにおいて人気のある手法として最近登場した。
本稿では,ユーザが複数のカテゴリの関心を持つ,困難なシナリオに焦点をあてる。
textitDiversity-Promoting Collaborative Metric Learning (DPCML) と呼ばれる新しい手法を提案する。
論文 参考訳(メタデータ) (2022-09-30T08:02:18Z) - Reward-Free RL is No Harder Than Reward-Aware RL in Linear Markov
Decision Processes [61.11090361892306]
Reward-free reinforcement learning (RL) は、エージェントが探索中に報酬関数にアクセスできないような環境を考える。
この分離は線形MDPの設定には存在しないことを示す。
我々は$d$次元線形 MDP における報酬のない RL に対する計算効率の良いアルゴリズムを開発した。
論文 参考訳(メタデータ) (2022-01-26T22:09:59Z) - New Tight Relaxations of Rank Minimization for Multi-Task Learning [161.23314844751556]
2つの正規化項に基づく2つの新しいマルチタスク学習定式化を提案する。
本手法は,タスク間で共有される低ランク構造を正確に復元し,関連するマルチタスク学習方法より優れていることを示す。
論文 参考訳(メタデータ) (2021-12-09T07:29:57Z) - Combinatorial Pure Exploration with Full-Bandit or Partial Linear
Feedback [18.29738891417779]
フルバンドフィードバック(CPE-BL)による純粋探索の問題点を最初に研究する。
CPE-BLでは、アクションのプル$x$は、$M_xtheta $を期待してランダムフィードバックベクトルを報告し、mathbbRd$の$M_xは、$x$の変換行列であり、$x$に関連するランダム(おそらく非線形)報酬を得る。
CPE-PLでは,限られたフィードバック,一般報酬関数,行動空間を同時に扱う最初のエムタイムアルゴリズムを開発した。
論文 参考訳(メタデータ) (2020-06-14T13:59:59Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。