論文の概要: Low-Rank Bandits via Tight Two-to-Infinity Singular Subspace Recovery

• arxiv url: http://arxiv.org/abs/2402.15739v2
• Date: Thu, 4 Jul 2024 11:17:38 GMT
• ステータス: 処理完了
• システム内更新日: 2024-07-08 23:43:31.014411
• Title: Low-Rank Bandits via Tight Two-to-Infinity Singular Subspace Recovery
• Title（参考訳）: 2-infinity Singular Subspaceリカバリによる低域帯域化
• Authors: Yassir Jedra, William Réveillard, Stefan Stojanovic, Alexandre Proutiere,
• Abstract要約: 本稿では,政策評価,最良政策識別,後悔の最小化のための効率的なアルゴリズムを提案する。 政策評価と最良の政策識別のために,我々のアルゴリズムは最小限に最適であることを示す。 提案アルゴリズムは、まずスペクトル法を利用して、低ランク報酬行列の左特異部分空間と右特異部分空間を推定する。
• 参考スコア（独自算出の注目度）: 45.601316850669406
• 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 ${r(m+n)\over \varepsilon^2}\log(1/\delta)$. Our regret minimization algorithm enjoys minimax guarantees typically 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（参考訳）: 各ラウンドにおいて、(コンテキスト、アーム)ペア$(i,j)\in [m]\times [n]$を選択すると、学習者は未知の低ランク報酬行列の$(i,j)$-thエントリのノイズの多いサンプルを観察する。 逐次的文脈は、i.d.方法でランダムに生成され、学習者に開示される。 そこで我々は, 政策評価, 最良政策識別, 後悔の最小化のための効率的なアルゴリズムを提案する。 政策評価と最良の政策識別のために,我々のアルゴリズムは最小限に最適であることを示す。 例えば、$\varepsilon$-optimal policyを少なくとも1-\delta$の確率で返すために必要なサンプルの数は、通常${r(m+n)\over \varepsilon^2}\log(1/\delta)$としてスケールする。 我々の後悔の最小化アルゴリズムは、通常$r^{7/4}(m+n)^{3/4}\sqrt{T}$としてスケールし、既存のアルゴリズムよりも改善されている。 提案アルゴリズムは、まずスペクトル法を利用して、低ランク報酬行列の左特異部分空間と右特異部分空間を推定する。 これらの推定は、2-infinityノルムにおいて厳密なエラー保証を享受していることが示される。 これにより、約$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)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。