論文の概要: Bandit PCA with Minimax Optimal Regret

• arxiv url: http://arxiv.org/abs/2607.10936v2
• Date: Wed, 15 Jul 2026 17:25:19 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-07-16 14:31:40.673978
• Title: Bandit PCA with Minimax Optimal Regret
• Title（参考訳）: Minimax Optimal Regret を用いたバンドPCA
• Authors: Moïse Blanchard, Dmitrii Ostrovskii, Aadirupa Saha,
• Abstract要約: オンライン主成分分析(Bandit PCA)のBandit-Feedback版について検討する。 各ラウンド $t = 1,dots,T$ において、敵は$d 倍 d$ 対称利得行列 $G_t$ を選択し、最高$r$ でランクする。 学習者は、Sd-1$の単位ベクトル$w_tを同時に選択し、報酬$w_ttop G_t w_t$を受け取る。
• 参考スコア（独自算出の注目度）: 21.155908599769763
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study the bandit-feedback version of online principal component analysis (Bandit PCA): in each round $t = 1,\dots,T$, the adversary selects a $d \times d$ symmetric gain matrix $G_t$ with spectrum in $[0,1]$ and rank at most $r$; the learner simultaneously selects a unit vector $w_t \in S^{d-1}$ and receives the reward $w_t^\top G_t w_t$. The learner receives no other feedback, and aims to minimize the regret against the best unit vector in hindsight. This problem was introduced by Kotlowski and Neu (2019), who gave an algorithm with regret $O(d\sqrt{rT \log T})$ and showed the lower bound of $Ω(r\sqrt{T/\log T})$. We improve upon both of these bounds and essentially bridge the gap between them, establishing the minimax regret of order $r\sqrt{dT}$ up to polylogarithmic factors in $d$ and $T$. The upper bound is attained by a novel algorithm, which combines online mirror descent on the spectrahedron of (real) density matrices with a multiscale exploration scheme in which the eigenspaces with different spectral magnitudes are updated at different rates. For the lower bound, we construct an adaptive adversary that refines a hidden large-reward subspace based on the learner's actions, in such a way that low regret is impossible without estimating the subspace; as a result, lower-bounding the regret reduces to studying the arising subspace estimation problem. Finally, we discuss connections of Bandit PCA with adaptive-measurement quantum tomography.
• Abstract（参考訳）: 各ラウンド$t = 1,\dots,T$ において、敵は$d \times d$ symmetric gain matrix $G_t$ を、スペクトルは$[0,1]$ で、ランクは $r$ で、学習者は同時に単位ベクトル $w_t \in S^{d-1}$ を選択し、報酬 $w_t^\top G_t w_t$ を受け取る。 学習者は、他のフィードバックを受け取らず、後ろ向きの最高の単位ベクトルに対する後悔を最小限に抑える。 この問題はKotlowskiとNeu (2019)によって導入され、Kutlowskiは後悔する$O(d\sqrt{rT \log T})$でアルゴリズムを与え、$Ω(r\sqrt{T/\log T})$の低い境界を示した。 これら2つの境界を改善し、それらのギャップを本質的に埋め、次数$r\sqrt{dT}$のミニマックス後悔を$d$と$T$のポリ対数因子まで確立する。 上界は、(実)密度行列のスペクトル上のオンラインミラー降下と、異なるスペクトル等級の固有空間を異なる速度で更新するマルチスケール探索スキームを組み合わせた、新しいアルゴリズムによって達成される。 下位境界に対して,学習者の行動に基づいて隠れた大逆部分空間を改良する適応的逆数列を構築し,その部分空間を推定することなく,低い後悔が不可能となるようにし,結果として,後悔を減らし,増大する部分空間推定問題の研究に還元する。 最後に、適応計測量子トモグラフィーによるBandit PCAの接続について述べる。

関連論文リスト

• Linear bandits with polylogarithmic minimax regret [8.97780713904412]
  本研究では,未知ベクトルに近づいた単位球上での動作を選択すると,サブガウス雑音パラメータが線形に消滅する線形帯域の雑音モデルについて検討する。 我々は,この問題に対するアルゴリズムを導入し,この最小限の後悔のスケーリングを,時間軸で$log3(T)$,時間軸で$T$として示す。
  論文  参考訳（メタデータ） (2024-02-19T10:56:47Z)
• Horizon-Free and Variance-Dependent Reinforcement Learning for Latent Markov Decision Processes [62.90204655228324]
  我々は,後期マルコフ決定過程(LMDP)における強化学習(RL)の文脈を考慮した後悔の最小化について検討した。 我々は,モデル最適化と値最適化の両手法でインスタンス化できる,新しいモデルベースアルゴリズムフレームワークを設計する。
  論文  参考訳（メタデータ） (2022-10-20T21:32:01Z)
• Regret Lower Bound and Optimal Algorithm for High-Dimensional Contextual Linear Bandit [10.604939762790517]
  我々は、累積後悔に対して、$mathcalObig((log d)fracalpha+12Tfrac1-alpha2+log Tbig)$をミニマックス下界として証明する。 第2に,汎用的なアッパー信頼境界(UCB)戦略に着想を得た,シンプルで効率的なアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-09-23T19:35:38Z)
• Near-Optimal Regret Bounds for Contextual Combinatorial Semi-Bandits with Linear Payoff Functions [53.77572276969548]
  我々は、C$2$UCBアルゴリズムが分割マトロイド制約に対して最適な後悔結合$tildeO(dsqrtkT + dk)$を有することを示した。 一般的な制約に対して,C$2$UCBアルゴリズムで腕の報酬推定値を変更するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-01-20T04:29:18Z)
• Stochastic Bandits with Linear Constraints [69.757694218456]
  制約付き文脈線形帯域設定について検討し、エージェントの目標は一連のポリシーを作成することである。 楽観的悲観的線形帯域(OPLB)と呼ばれる,この問題に対する高信頼束縛アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-06-17T22:32:19Z)
• Naive Exploration is Optimal for Online LQR [49.681825576239355]
  最適後悔尺度は$widetildeTheta(sqrtd_mathbfu2 d_mathbfx T)$で、$T$は時間ステップの数、$d_mathbfu$は入力空間の次元、$d_mathbfx$はシステム状態の次元である。 我々の下界は、かつての$mathrmpoly(logT)$-regretアルゴリズムの可能性を排除する。
  論文  参考訳（メタデータ） (2020-01-27T03:44:54Z)

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

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