論文の概要: Nearly Minimax Algorithms for Linear Bandits with Shared Representation
- arxiv url: http://arxiv.org/abs/2203.15664v1
- Date: Tue, 29 Mar 2022 15:27:13 GMT
- ステータス: 処理完了
- システム内更新日: 2022-03-30 12:53:47.409448
- Title: Nearly Minimax Algorithms for Linear Bandits with Shared Representation
- Title（参考訳）: 共有表現を持つ線形バンディットの近似最小アルゴリズム
- Authors: Jiaqi Yang, Qi Lei, Jason D. Lee, Simon S. Du
- Abstract要約: 我々は、次元が$d$で、それぞれ$T$のラウンドで$M$リニアバンディットをプレイする設定を考え、これらの$M$リニアバンディットタスクは共通の$k(ll d)$次元リニア表現を共有する。
我々は$widetildeOleft(dsqrtkMT + kMsqrtTright)$ regret boundsを達成する新しいアルゴリズムを考案した。
- 参考スコア（独自算出の注目度）: 86.79657561369397
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We give novel algorithms for multi-task and lifelong linear bandits with
shared representation. Specifically, we consider the setting where we play $M$
linear bandits with dimension $d$, each for $T$ rounds, and these $M$ bandit
tasks share a common $k(\ll d)$ dimensional linear representation. For both the
multi-task setting where we play the tasks concurrently, and the lifelong
setting where we play tasks sequentially, we come up with novel algorithms that
achieve $\widetilde{O}\left(d\sqrt{kMT} + kM\sqrt{T}\right)$ regret bounds,
which matches the known minimax regret lower bound up to logarithmic factors
and closes the gap in existing results [Yang et al., 2021]. Our main technique
include a more efficient estimator for the low-rank linear feature extractor
and an accompanied novel analysis for this estimator.
- Abstract（参考訳）: 共有表現を持つマルチタスクおよび生涯線形バンディットのための新しいアルゴリズムを提案する。
具体的には、次元$d$で$M$の線形バンディットをそれぞれ$T$のラウンドで演奏し、これらの$M$のバンディットタスクは共通の$k(\ll d)$の次元線形表現を共有する。
タスクを同時に実行するマルチタスク設定と、タスクをシーケンシャルに実行するライフサイクル設定の両方に対して、既知のミニマックスの後悔と一致し、対数的要因に縛られ、既存の結果のギャップを埋める、$\widetilde{O}\left(d\sqrt{kMT} + kM\sqrt{T}\right)$ regret boundsという新しいアルゴリズムを考案する(Yang et al., 2021]。
提案手法は,低ランク線形特徴抽出器のためのより効率的な推定器と,この推定器の新たな解析手法を含む。
関連論文リスト
- Near-Minimax-Optimal Risk-Sensitive Reinforcement Learning with CVaR [58.40575099910538]
本研究は,リスク許容度が$tau$のCVaR(Conditional Value at Risk)の目的に着目し,リスクに敏感な強化学習(RL)について検討する。
ミニマックスCVaRの後悔率は$Omega(sqrttau-1AK)$で、$A$はアクションの数、$K$はエピソード数である。
我々は,このアルゴリズムが連続性仮定の下で$widetilde O(tau-1sqrtSAK)$の最適後悔を達成し,一般に近似することを示す。
論文 参考訳（メタデータ） (2023-02-07T02:22:31Z) - Exploration in Linear Bandits with Rich Action Sets and its Implications
for Inference [23.364534479492715]
期待行列の最小固有値は、アルゴリズムの累積後悔が$sqrtn)$であるときに、$Omega(sqrtn)として増加することを示す。
本研究は, 線形帯域におけるEmphmodel selectionとEmphclusteringの2つの実践シナリオに適用する。
論文 参考訳（メタデータ） (2022-07-23T20:25:07Z) - Corralling a Larger Band of Bandits: A Case Study on Switching Regret
for Linear Bandits [99.86860277006318]
本稿では,一組の逆アルゴリズムを組み合わせ,学習することの問題点について考察する。
Agarwal et al. の CORRAL はこの目標を、$widetildeO(sqrtd S T)$ の残酷なオーバーヘッドで達成している。
この問題に触発されて、後悔のオーバーヘッドが百万ドルにしか依存しない大規模バンディットアルゴリズムのバンドを囲む新しいレシピを提案する。
論文 参考訳（メタデータ） (2022-02-12T21:55:44Z) - Near-optimal Representation Learning for Linear Bandits and Linear RL [41.33483293243257]
私たちはまず、次元が$d$の線形バンディットを同時に$M$で演奏する設定を考えます。
これらの包帯は、$k$-次元線型表現を共有するので、$kll d$ と $k ll M$ が成り立つ。
我々は、共有表現を利用して$tildeO(MsqrtdkT + dsqrtkMT )を後悔するサンプル効率のアルゴリズムMTLR-OFULを提案する。
論文 参考訳（メタデータ） (2021-02-08T11:11:53Z) - Nearly Minimax Optimal Reinforcement Learning for Linear Mixture Markov
Decision Processes [91.38793800392108]
本稿では,マルコフ決定過程(MDP)の遷移確率核が線形混合モデルである線形関数近似による強化学習について検討する。
上記の線形混合 MDP に対して$textUCRL-VTR+$ という線形関数近似を用いた計算効率の良い新しいアルゴリズムを提案する。
我々の知る限り、これらは線形関数近似を持つRLのための計算効率が良く、ほぼ最小のアルゴリズムである。
論文 参考訳（メタデータ） (2020-12-15T18:56:46Z) - Impact of Representation Learning in Linear Bandits [83.17684841392754]
本研究では,表現学習が帯域幅問題の効率性を向上させる方法について検討する。
我々は,$widetildeO(TsqrtkN + sqrtdkNT)$ regretを達成する新しいアルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-10-13T16:35:30Z) - Stochastic Bandits with Linear Constraints [69.757694218456]
制約付き文脈線形帯域設定について検討し、エージェントの目標は一連のポリシーを作成することである。
楽観的悲観的線形帯域(OPLB)と呼ばれる,この問題に対する高信頼束縛アルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-06-17T22:32:19Z) - Low-Rank Generalized Linear Bandit Problems [19.052901817304743]
低ランク線型バンドイット問題において、作用の報酬は、作用と未知の低ランク行列$Theta*$の間の内部積である。
低ランク行列の被覆によって構築される指数重み付き平均予測器と、オンラインから信頼度セットへの変換パバシ2012onlineの新たな組み合わせに基づくアルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-06-04T15:30:14Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。