論文の概要: Asymptotically Optimal Pure Exploration for Infinite-Armed Bandits

• arxiv url: http://arxiv.org/abs/2306.01995v1
• Date: Sat, 3 Jun 2023 04:00:47 GMT
• ステータス: 処理完了
• システム内更新日: 2023-06-06 20:54:18.855475
• Title: Asymptotically Optimal Pure Exploration for Infinite-Armed Bandits
• Title（参考訳）: 無限腕バンディットの漸近的最適純粋探査
• Authors: Xiao-Yue Gong, Mark Sellke
• Abstract要約: 我々は、未知の分布から生じる無限に多くのバンドイットアームを用いて純粋探索を研究する。 私たちのゴールは、平均的な報酬が1-delta$の1つの高品質なアームを、最高の$eta$-fraction of armsの1つとして$varepsilon$内で効率的に選択することにあります。
• 参考スコア（独自算出の注目度）: 4.811176167998627
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study pure exploration with infinitely many bandit arms generated i.i.d. from an unknown distribution. Our goal is to efficiently select a single high quality arm whose average reward is, with probability $1-\delta$, within $\varepsilon$ of being among the top $\eta$-fraction of arms; this is a natural adaptation of the classical PAC guarantee for infinite action sets. We consider both the fixed confidence and fixed budget settings, aiming respectively for minimal expected and fixed sample complexity. For fixed confidence, we give an algorithm with expected sample complexity $O\left(\frac{\log (1/\eta)\log (1/\delta)}{\eta\varepsilon^2}\right)$. This is optimal except for the $\log (1/\eta)$ factor, and the $\delta$-dependence closes a quadratic gap in the literature. For fixed budget, we show the asymptotically optimal sample complexity as $\delta\to 0$ is $c^{-1}\log(1/\delta)\big(\log\log(1/\delta)\big)^2$ to leading order. Equivalently, the optimal failure probability given exactly $N$ samples decays as $\exp\big(-cN/\log^2 N\big)$, up to a factor $1\pm o_N(1)$ inside the exponent. The constant $c$ depends explicitly on the problem parameters (including the unknown arm distribution) through a certain Fisher information distance. Even the strictly super-linear dependence on $\log(1/\delta)$ was not known and resolves a question of Grossman and Moshkovitz (FOCS 2016, SIAM Journal on Computing 2020).
• Abstract（参考訳）: 我々は、未知の分布から生じる無限に多くのバンドイットアームを用いて純粋探索を研究する。 我々のゴールは、平均的な報酬が1-\delta$の1つの高品質なアームを、上位の$\eta$-fraction of armsの1つとして$\varepsilon$で効率的に選択することである。 固定的な信頼度と固定的な予算の設定の両方を考え、それぞれ最小限の期待値と固定されたサンプルの複雑さを目指しています。 一定の信頼のために、サンプル複雑性が期待できるアルゴリズムに$o\left(\frac{\log (1/\eta)\log (1/\delta)}{\eta\varepsilon^2}\right)$を与える。 これは$\log (1/\eta)$ factorを除いて最適であり、$\delta$-dependenceは文学における二次的なギャップを閉じる。 固定予算の場合、漸近的に最適なサンプル複雑性は$\delta\to 0$ is $c^{-1}\log(1/\delta)\big(\log\log(1/\delta)\big)^2$ である。 同様に、n$ のサンプルが与えられた最適故障確率は、指数の内部で 1\pm o_n(1)$ まで、$\exp\big(-cn/\log^2 n\big)$ で崩壊する。 定数 $c$ は、一定のフィッシャー情報距離を通じて問題パラメータ(未知のアーム分布を含む)に明示的に依存する。 $\log(1/\delta)$に対する厳密な超線形依存でさえも分かっておらず、GrossmanとMoshkovitz(FOCS 2016 SIAM Journal on Computing 2020)の疑問を解決している。

関連論文リスト

• Optimal Streaming Algorithms for Multi-Armed Bandits [28.579280943038555]
  ストリーミングBAI問題では,最大報酬が1-delta$の確率でアームを識別することが目的である。 我々は,O(log Delta-1)$パス内で,ほぼインスタンス依存の最適なサンプル複雑性を実現するシングルアームメモリアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-10-23T12:54:04Z)
• Fast Rates for Bandit PAC Multiclass Classification [73.17969992976501]
  我々は,帯域幅フィードバックを用いたマルチクラスPAC学習について検討し,入力を$K$ラベルの1つに分類し,予測されたラベルが正しいか否かに制限する。 我々の主な貢献は、問題の無知な$(varepsilon,delta)$PACバージョンのための新しい学習アルゴリズムを設計することである。
  論文  参考訳（メタデータ） (2024-06-18T08:54:04Z)
• Near-Optimal Non-Convex Stochastic Optimization under Generalized Smoothness [21.865728815935665]
  2つの最近の研究は、$O(epsilon-3)$サンプル複雑性を確立し、$O(epsilon)$-定常点を得る。 しかし、どちらも$mathrmploy(epsilon-1)$という大きなバッチサイズを必要とする。 本研究では,STORMアルゴリズムの単純な変種を再検討することにより,従来の2つの問題を同時に解決する。
  論文  参考訳（メタデータ） (2023-02-13T00:22:28Z)
• Fast, Sample-Efficient, Affine-Invariant Private Mean and Covariance Estimation for Subgaussian Distributions [8.40077201352607]
  我々は,高次元共分散認識平均推定のための高速,微分プライベートなアルゴリズムを提案する。 我々のアルゴリズムは$tildemu$を生成し、$|mu|_Sigma leq alpha$が$n gtrsim tfrac d alpha2 + tfracd sqrtlog 1/deltaalpha varepsilon+fracdlog 1/deltavarepsilon$である。
  論文  参考訳（メタデータ） (2023-01-28T16:57:46Z)
• On the complexity of All $\varepsilon$-Best Arms Identification [2.1485350418225244]
  ガウスの報酬を持つ有限の多腕バンディットにおいて、$varepsilon$-optimal armsを全て識別する問題を考える。 我々は,$varepsilon$-good arms w.h.p の集合を同定し,期待されるサンプルの複雑さの観点から最適性($delta$が 0 になるとき)を享受するトラック・アンド・ストップアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2022-02-13T10:54:52Z)
• Faster Rates of Differentially Private Stochastic Convex Optimization [7.93728520583825]
  人口リスク関数がTysbakovノイズ条件(TNC)をパラメータ$theta>1$で満たす場合について検討した。 第2部では,人口リスク関数が強く凸する特殊な事例に着目した。
  論文  参考訳（メタデータ） (2021-07-31T22:23:39Z)
• Bandits with many optimal arms [68.17472536610859]
  最適アームの割合は$p*$、最適アームとサブ最適化アームの間の最小平均ギャップは$Delta$と書きます。 我々は,累積的後悔設定と最良腕識別設定の両方において最適な学習率を特徴付ける。
  論文  参考訳（メタデータ） (2021-03-23T11:02:31Z)
• An Optimal Separation of Randomized and Quantum Query Complexity [67.19751155411075]
  すべての決定木に対して、与えられた順序 $ellsqrtbinomdell (1+log n)ell-1,$ sum to at least $cellsqrtbinomdell (1+log n)ell-1,$ where $n$ is the number of variables, $d$ is the tree depth, $c>0$ is a absolute constant。
  論文  参考訳（メタデータ） (2020-08-24T06:50:57Z)
• Model-Free Reinforcement Learning: from Clipped Pseudo-Regret to Sample Complexity [59.34067736545355]
  S$状態、$A$アクション、割引係数$gamma in (0,1)$、近似しきい値$epsilon > 0$の MDP が与えられた場合、$epsilon$-Optimal Policy を学ぶためのモデルなしアルゴリズムを提供する。 十分小さな$epsilon$の場合、サンプルの複雑さで改良されたアルゴリズムを示す。
  論文  参考訳（メタデータ） (2020-06-06T13:34:41Z)
• Locally Private Hypothesis Selection [96.06118559817057]
  我々は、$mathcalQ$から$p$までの総変動距離が最良の分布に匹敵する分布を出力する。 局所的な差分プライバシーの制約は、コストの急激な増加を引き起こすことを示す。 提案アルゴリズムは,従来手法のラウンド複雑性を指数関数的に改善する。
  論文  参考訳（メタデータ） (2020-02-21T18:30:48Z)
• Curse of Dimensionality on Randomized Smoothing for Certifiable Robustness [151.67113334248464]
  我々は、他の攻撃モデルに対してスムースな手法を拡張することは困難であることを示す。 我々はCIFARに関する実験結果を示し,その理論を検証した。
  論文  参考訳（メタデータ） (2020-02-08T22:02:14Z)

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

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