論文の概要: Bandit Phase Retrieval

• arxiv url: http://arxiv.org/abs/2106.01660v2
• Date: Fri, 4 Jun 2021 15:52:52 GMT
• ステータス: 処理完了
• システム内更新日: 2021-06-07 11:26:11.234993
• Title: Bandit Phase Retrieval
• Title（参考訳）: Bandit Phase Retrieval
• Authors: Tor Lattimore, Botao Hao
• Abstract要約: この問題におけるminimax累積後悔は$smashtilde Theta(d sqrtn)$であることを証明する。 また、minimax の単純な後悔は $smashtilde Theta(d / sqrtn)$ であり、これは適応アルゴリズムによってのみ達成可能であることを示す。
• 参考スコア（独自算出の注目度）: 45.12888201134656
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study a bandit version of phase retrieval where the learner chooses actions $(A_t)_{t=1}^n$ in the $d$-dimensional unit ball and the expected reward is $\langle A_t, \theta_\star\rangle^2$ where $\theta_\star \in \mathbb R^d$ is an unknown parameter vector. We prove that the minimax cumulative regret in this problem is $\smash{\tilde \Theta(d \sqrt{n})}$, which improves on the best known bounds by a factor of $\smash{\sqrt{d}}$. We also show that the minimax simple regret is $\smash{\tilde \Theta(d / \sqrt{n})}$ and that this is only achievable by an adaptive algorithm. Our analysis shows that an apparently convincing heuristic for guessing lower bounds can be misleading and that uniform bounds on the information ratio for information-directed sampling are not sufficient for optimal regret.
• Abstract（参考訳）: そこで、学習者が$d$次元単位球において$(a_t)_{t=1}^n$を選択し、期待される報酬が$\langle a_t, \theta_\star\rangle^2$であり、ここで$\theta_\star \in \mathbb r^d$は未知のパラメータベクトルである。 この問題のminimax累積後悔は$\smash{\tilde \theta(d \sqrt{n})}$であることが証明され、これは$\smash{\sqrt{d}}$の係数によって最もよく知られた境界で改善される。 また、minimaxの単純な後悔は$\smash{\tilde \Theta(d / \sqrt{n})}$であり、適応アルゴリズムによってのみ達成可能であることを示す。 分析の結果,下限を推測するための説得力のあるヒューリスティックは誤解を招く可能性があり,情報指向サンプリングにおける情報比の均一な境界は,最適な後悔には不十分であることが示唆された。

関連論文リスト

• How Does Variance Shape the Regret in Contextual Bandits? [59.8472760881411]
  一般関数近似を用いた文脈的包帯について考察する。 共振器次元 $d_textelu$-$play が分散依存境界において重要な役割を果たすことを示す。
  論文  参考訳（メタデータ） (2024-10-16T16:20:07Z)
• Low-rank Matrix Bandits with Heavy-tailed Rewards [55.03293214439741]
  アンダーライン重み付きアンダーラインリワード(LowHTR)を用いたアンダーラインローランク行列バンディットの問題点について検討する。 観測されたペイオフに対するトランケーションと動的探索を利用して,LOTUSと呼ばれる新しいアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-04-26T21:54:31Z)
• 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)
• Sparse Recovery with Shuffled Labels: Statistical Limits and Practical Estimators [23.313461266708877]
  置換行列 $bPitrue$ とスパース信号 $bbetatrue$ をシャッフルラベルから再構成する。 提案した推定器は, 穏やかな条件下で, 基本トラス$(bPitrue, supp(bbetatrue))$が得られることを示す。
  論文  参考訳（メタデータ） (2023-03-20T16:14:58Z)
• 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)
• Sparse Signal Detection in Heteroscedastic Gaussian Sequence Models: Sharp Minimax Rates [1.0309387309011746]
  スパースな代替品に対する信号検出問題を、既知のスパシティ$s$に対して検討する。 ミニマックス分離半径$epsilon*$の上の上限と下限を見つけ、それらが常に一致することを証明する。 以上の結果から,epsilon*$の挙動に関する新たな位相遷移が,Sigma$の疎度レベル,$Lt$メトリック,およびヘテロスセダサシティプロファイル(herescedasticity profile)に現れる。
  論文  参考訳（メタデータ） (2022-11-15T23:53:39Z)
• Explicit Best Arm Identification in Linear Bandits Using No-Regret Learners [17.224805430291177]
  線形パラメータ化マルチアームバンドにおけるベストアーム識別の問題について検討する。 そこで本研究では,この問題を解決するために,明示的に実装可能かつ証明可能な順序-最適サンプル-複雑度アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-06-13T05:00:01Z)
• Problem-Complexity Adaptive Model Selection for Stochastic Linear Bandits [20.207989166682832]
  2つの一般的な線形バンディット設定におけるモデル選択の問題について考察する。 まず、[K]$におけるarm $iの平均的な報酬は、$mu_i+ langle alpha_i,t,theta*|$である。 我々は、ALBが$O(|theta*|sqrtT)$の後悔のスケーリングを達成することを示す。
  論文  参考訳（メタデータ） (2020-06-04T02:19:00Z)
• Near-optimal Regret Bounds for Stochastic Shortest Path [63.029132134792555]
  最短経路 (SSP) は計画と制御においてよく知られた問題であり、エージェントは最小の総コストで目標状態に到達する必要がある。 任意の学習アルゴリズムは、最悪の場合、少なくとも$Omega(B_star sqrt|S| |A|K)$後悔しなければならない。
  論文  参考訳（メタデータ） (2020-02-23T09:10:14Z)

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

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