論文の概要: Impact of Representation Learning in Linear Bandits
- arxiv url: http://arxiv.org/abs/2010.06531v2
- Date: Wed, 5 May 2021 17:01:53 GMT
- ステータス: 処理完了
- システム内更新日: 2022-10-08 00:23:40.243316
- Title: Impact of Representation Learning in Linear Bandits
- Title（参考訳）: 線形帯域における表現学習の影響
- Authors: Jiaqi Yang, Wei Hu, Jason D. Lee, Simon S. Du
- Abstract要約: 本研究では,表現学習が帯域幅問題の効率性を向上させる方法について検討する。
我々は,$widetildeO(TsqrtkN + sqrtdkNT)$ regretを達成する新しいアルゴリズムを提案する。
- 参考スコア（独自算出の注目度）: 83.17684841392754
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study how representation learning can improve the efficiency of bandit
problems. We study the setting where we play $T$ linear bandits with dimension
$d$ concurrently, and these $T$ bandit tasks share a common $k (\ll d)$
dimensional linear representation. For the finite-action setting, we present a
new algorithm which achieves $\widetilde{O}(T\sqrt{kN} + \sqrt{dkNT})$ regret,
where $N$ is the number of rounds we play for each bandit. When $T$ is
sufficiently large, our algorithm significantly outperforms the naive algorithm
(playing $T$ bandits independently) that achieves $\widetilde{O}(T\sqrt{d N})$
regret. We also provide an $\Omega(T\sqrt{kN} + \sqrt{dkNT})$ regret lower
bound, showing that our algorithm is minimax-optimal up to poly-logarithmic
factors. Furthermore, we extend our algorithm to the infinite-action setting
and obtain a corresponding regret bound which demonstrates the benefit of
representation learning in certain regimes. We also present experiments on
synthetic and real-world data to illustrate our theoretical findings and
demonstrate the effectiveness of our proposed algorithms.
- Abstract（参考訳）: 本研究では,表現学習が帯域幅問題の効率を改善する方法を検討する。
我々は、次元$d$と平行に$T$の線形バンディットをプレイする環境で、これらの$T$のバンディットタスクは共通の$k(\ll d)$次元線形表現を共有する。
有限作用設定に対しては、$\widetilde{O}(T\sqrt{kN} + \sqrt{dkNT})$ regret, ここでは、$N$は、各バンディットに対して演奏するラウンドの数である。
T$が十分に大きい場合、我々のアルゴリズムは、後悔する$\widetilde{O}(T\sqrt{d N})を達成できるナイーブアルゴリズム(独立に$T$をプレイする)を大幅に上回る。
また、$\Omega(T\sqrt{kN} + \sqrt{dkNT})$ regret lower bound も提供し、このアルゴリズムが多変数因子まで最小値であることを示す。
さらに,このアルゴリズムを無限動作設定に拡張し,特定のレジームにおける表現学習の利点を示す対応する後悔境界を得る。
また,提案手法の有効性を理論的に示すために,合成および実世界のデータについても実験を行った。
関連論文リスト
- Context-lumpable stochastic bandits [49.024050919419366]
我々は、$S$コンテキストと$K$アクションによる文脈的盗賊問題を考える。
我々は,最大$widetilde O(r (S +K )/epsilon2)$サンプルを用いて,$epsilon$-optimal Policyを出力するアルゴリズムを提案する。
後悔の設定では、T$までの累積後悔を$widetilde O(sqrtr3(S+K)T)$で束縛するアルゴリズムを与える。
論文 参考訳（メタデータ） (2023-06-22T17:20:30Z) - 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) - Nearly Minimax Algorithms for Linear Bandits with Shared Representation [86.79657561369397]
我々は、次元が$d$で、それぞれ$T$のラウンドで$M$リニアバンディットをプレイする設定を考え、これらの$M$リニアバンディットタスクは共通の$k(ll d)$次元リニア表現を共有する。
我々は$widetildeOleft(dsqrtkMT + kMsqrtTright)$ regret boundsを達成する新しいアルゴリズムを考案した。
論文 参考訳（メタデータ） (2022-03-29T15:27:13Z) - 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) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。