論文の概要: Low-Rank Bandits via Tight Two-to-Infinity Singular Subspace Recovery
- arxiv url: http://arxiv.org/abs/2402.15739v1
- Date: Sat, 24 Feb 2024 06:36:08 GMT
- ステータス: 処理完了
- システム内更新日: 2024-02-27 17:11:04.249835
- Title: Low-Rank Bandits via Tight Two-to-Infinity Singular Subspace Recovery
- Title（参考訳）: 2-infinity Singular Subspaceリカバリによる低域帯域化
- Authors: Yassir Jedra, William R\'eveillard, Stefan Stojanovic, Alexandre
Proutiere
- Abstract要約: 本稿では,政策評価,最良政策識別,後悔の最小化のための効率的なアルゴリズムを提案する。
政策評価と最良の政策識別のために,我々のアルゴリズムは最小限に最適であることを示す。
提案アルゴリズムは、まずスペクトル法を利用して、低ランク報酬行列の左特異部分空間と右特異部分空間を推定する。
- 参考スコア（独自算出の注目度）: 48.92318828548911
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study contextual bandits with low-rank structure where, in each round, if
the (context, arm) pair $(i,j)\in [m]\times [n]$ is selected, the learner
observes a noisy sample of the $(i,j)$-th entry of an unknown low-rank reward
matrix. Successive contexts are generated randomly in an i.i.d. manner and are
revealed to the learner. For such bandits, we present efficient algorithms for
policy evaluation, best policy identification and regret minimization. For
policy evaluation and best policy identification, we show that our algorithms
are nearly minimax optimal. For instance, the number of samples required to
return an $\varepsilon$-optimal policy with probability at least $1-\delta$
typically scales as ${m+n\over \varepsilon^2}\log(1/\delta)$. Our regret
minimization algorithm enjoys minimax guarantees scaling as
$r^{7/4}(m+n)^{3/4}\sqrt{T}$, which improves over existing algorithms. All the
proposed algorithms consist of two phases: they first leverage spectral methods
to estimate the left and right singular subspaces of the low-rank reward
matrix. We show that these estimates enjoy tight error guarantees in the
two-to-infinity norm. This in turn allows us to reformulate our problems as a
misspecified linear bandit problem with dimension roughly $r(m+n)$ and
misspecification controlled by the subspace recovery error, as well as to
design the second phase of our algorithms efficiently.
- Abstract（参考訳）: 各ラウンドにおいて(コンテキスト,arm)ペア$(i,j)\in [m]\times [n]$が選択された場合、学習者は未知の低ランク報酬行列の$(i,j)$-thのノイズのサンプルを観察する。
逐次的文脈はi.d.方法でランダムに生成され、学習者に開示される。
そこで我々は,政策評価,最良政策識別,後悔の最小化のための効率的なアルゴリズムを提案する。
政策評価と最良の政策識別のために,我々のアルゴリズムは最小限に最適であることを示す。
例えば、少なくとも1-\delta$の確率で$\varepsilon$-optimalポリシーを返すために必要なサンプルの数は、通常${m+n\over \varepsilon^2}\log(1/\delta)$となる。
我々の後悔の最小化アルゴリズムは、r^{7/4}(m+n)^{3/4}\sqrt{T}$のスケーリングを保証し、既存のアルゴリズムよりも改善する。
提案されたすべてのアルゴリズムは2つのフェーズから構成されており、まずスペクトル法を利用して低ランクの報酬行列の左右の特異部分空間を推定する。
これらの推定値が2対無限ノルムにおいて厳密な誤差保証を享受していることを示す。
これにより、約$r(m+n)$の誤特定された線形バンディット問題とサブスペースリカバリエラーによって制御される誤特定問題と、アルゴリズムの第2フェーズを効率的に設計できるようになりました。
関連論文リスト
- Model-free Low-Rank Reinforcement Learning via Leveraged Entry-wise Matrix Estimation [48.92318828548911]
政策改善と政策評価の段階を交互に行うモデルフリー学習アルゴリズムであるLoRa-PI(Low-Rank Policy Iteration)を提案する。
LoRa-PIは$widetildeO(S+Aover mathrmpoly (1-gamma)varepsilon2)$サンプルを使用して$varepsilon$-optimal Policyを学習する。
論文 参考訳（メタデータ） (2024-10-30T20:22:17Z) - Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic
Shortest Path [80.60592344361073]
線形混合遷移カーネルを用いた最短経路(SSP)問題について検討する。
エージェントは繰り返し環境と対話し、累積コストを最小化しながら特定の目標状態に到達する。
既存の作業は、イテレーションコスト関数の厳密な下限や、最適ポリシーに対する期待長の上限を仮定することが多い。
論文 参考訳（メタデータ） (2024-02-14T07:52:00Z) - Best-of-Both-Worlds Algorithms for Linear Contextual Bandits [11.94312915280916]
両世界のベスト・オブ・ワールドズ・アルゴリズムを$K$武器付き線形文脈包帯に対して検討する。
我々のアルゴリズムは、敵対的体制と敵対的体制の両方において、ほぼ最適の後悔の限界を提供する。
論文 参考訳（メタデータ） (2023-12-24T08:27:30Z) - Efficient Algorithms for Generalized Linear Bandits with Heavy-tailed
Rewards [40.99322897009357]
トランケーションと平均中央値に基づく2つの新しいアルゴリズムを提案する。
我々のトラニケーションベースのアルゴリズムは、既存のトラニケーションベースのアプローチと区別して、オンライン学習をサポートする。
我々のアルゴリズムは,$epsilon=1$の既存アルゴリズムと比較して,対数係数による後悔境界を改善する。
論文 参考訳（メタデータ） (2023-10-28T13:01:10Z) - 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) - Best Policy Identification in Linear MDPs [70.57916977441262]
縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。
複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
論文 参考訳（メタデータ） (2022-08-11T04:12:50Z) - Variance-Aware Sparse Linear Bandits [64.70681598741417]
余分な線形包帯に対する最悪のミニマックスは$widetildeThetaleft(sqrtdTright)$である。
ノイズがなく、アクションセットが単位球面である良性設定では、ディビジョン・アンド・コンカーを使用して、$widetildemathcal O(1)$ regretを達成することができる。
我々は,任意の分散対応線形帯域幅アルゴリズムを分散対応線形帯域幅アルゴリズムに変換する汎用フレームワークを開発した。
論文 参考訳（メタデータ） (2022-05-26T15:55:44Z) - Sketching Algorithms and Lower Bounds for Ridge Regression [65.0720777731368]
リッジ回帰問題に対する1+varepsilon$近似解を計算するスケッチベース反復アルゴリズムを提案する。
また,このアルゴリズムがカーネルリッジ回帰の高速化に有効であることを示す。
論文 参考訳（メタデータ） (2022-04-13T22:18:47Z) - Low-Rank Generalized Linear Bandit Problems [19.052901817304743]
低ランク線型バンドイット問題において、作用の報酬は、作用と未知の低ランク行列$Theta*$の間の内部積である。
低ランク行列の被覆によって構築される指数重み付き平均予測器と、オンラインから信頼度セットへの変換パバシ2012onlineの新たな組み合わせに基づくアルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-06-04T15:30:14Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。