論文の概要: Approximate Top-$m$ Arm Identification with Heterogeneous Reward Variances

• arxiv url: http://arxiv.org/abs/2204.05245v1
• Date: Mon, 11 Apr 2022 16:41:33 GMT
• ステータス: 処理完了
• システム内更新日: 2022-04-12 19:00:08.601248
• Title: Approximate Top-$m$ Arm Identification with Heterogeneous Reward Variances
• Title（参考訳）: 不均一な逆行性障害を伴う近似Top-m$アーム同定
• Authors: Ruida Zhou, Chao Tian
• Abstract要約: この問題の最悪のサンプルの複雑さは$Thetaleft(sum_i = 1n fracsigma_i2epsilon2 lnfrac1delta + sum_i in Gm fracsigma_j2epsilon2 textEnt(sigma2_Gr) right)$$$$$Gm, Gl, Grである。
• 参考スコア（独自算出の注目度）: 11.555138461092177
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study the effect of reward variance heterogeneity in the approximate top-$m$ arm identification setting. In this setting, the reward for the $i$-th arm follows a $\sigma^2_i$-sub-Gaussian distribution, and the agent needs to incorporate this knowledge to minimize the expected number of arm pulls to identify $m$ arms with the largest means within error $\epsilon$ out of the $n$ arms, with probability at least $1-\delta$. We show that the worst-case sample complexity of this problem is $$\Theta\left( \sum_{i =1}^n \frac{\sigma_i^2}{\epsilon^2} \ln\frac{1}{\delta} + \sum_{i \in G^{m}} \frac{\sigma_i^2}{\epsilon^2} \ln(m) + \sum_{j \in G^{l}} \frac{\sigma_j^2}{\epsilon^2} \text{Ent}(\sigma^2_{G^{r}}) \right),$$ where $G^{m}, G^{l}, G^{r}$ are certain specific subsets of the overall arm set $\{1, 2, \ldots, n\}$, and $\text{Ent}(\cdot)$ is an entropy-like function which measures the heterogeneity of the variance proxies. The upper bound of the complexity is obtained using a divide-and-conquer style algorithm, while the matching lower bound relies on the study of a dual formulation.
• Abstract（参考訳）: 本研究は,腕の識別設定における報酬分散の不均一性の影響について検討する。 この設定では、$i$-th腕の報酬は$\sigma^2_i$-sub-Gaussian分布に従っており、エージェントはこの知識を組み込んで、予想されるアームプル数を最小化し、エラーの最大の手段である$m$腕を特定する必要がある。 We show that the worst-case sample complexity of this problem is $$\Theta\left( \sum_{i =1}^n \frac{\sigma_i^2}{\epsilon^2} \ln\frac{1}{\delta} + \sum_{i \in G^{m}} \frac{\sigma_i^2}{\epsilon^2} \ln(m) + \sum_{j \in G^{l}} \frac{\sigma_j^2}{\epsilon^2} \text{Ent}(\sigma^2_{G^{r}}) \right),$$ where $G^{m}, G^{l}, G^{r}$ are certain specific subsets of the overall arm set $\{1, 2, \ldots, n\}$, and $\text{Ent}(\cdot)$ is an entropy-like function which measures the heterogeneity of the variance proxies. 複雑性の上界は分割・対数型アルゴリズムを用いて得られるが、一致する下界は二重定式化の研究に依存する。

関連論文リスト

• Dimension-free Private Mean Estimation for Anisotropic Distributions [55.86374912608193]
  以前の$mathRd上の分布に関する民間推定者は、次元性の呪いに苦しむ。 本稿では,サンプルの複雑さが次元依存性を改善したアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-11-01T17:59:53Z)
• Measuring quantum relative entropy with finite-size effect [53.64687146666141]
  相対エントロピー$D(rho|sigma)$を$sigma$が知られているときに推定する。 我々の推定器は次元$d$が固定されたときにCram'er-Rao型境界に達する。
  論文  参考訳（メタデータ） (2024-06-25T06:07:20Z)
• A Unified Framework for Uniform Signal Recovery in Nonlinear Generative Compressed Sensing [68.80803866919123]
  非線形測定では、ほとんどの先行結果は一様ではない、すなわち、すべての$mathbfx*$に対してではなく、固定された$mathbfx*$に対して高い確率で保持される。 本フレームワークはGCSに1ビット/一様量子化観測と単一インデックスモデルを標準例として適用する。 また、指標集合が計量エントロピーが低い製品プロセスに対して、より厳密な境界を生み出す濃度不等式も開発する。
  論文  参考訳（メタデータ） (2023-09-25T17:54:19Z)
• Thompson Sampling for Real-Valued Combinatorial Pure Exploration of Multi-Armed Bandit [65.268245109828]
  本稿では,マルチアームバンディット(R-CPE-MAB)問題の実測値について検討する。 一般トンプソンサンプリング探索法(GenTS-Explore)と呼ばれるアルゴリズムを導入する。これは,アクションセットのサイズが指数関数的に$d$で大きい場合でも動作可能な,最初のアルゴリズムである。
  論文  参考訳（メタデータ） (2023-08-20T11:56:02Z)
• A/B Testing and Best-arm Identification for Linear Bandits with Robustness to Non-stationarity [28.068960555415014]
  非定常環境下での線形包帯の固定予算ベストアーム識別問題について検討する。 アルゴリズムは、可能な限り高い確率で最適な腕 $x* := argmax_xinmathcalXxtopsum_t=1Ttheta_t$ を正しく識別することを目的としている。
  論文  参考訳（メタデータ） (2023-07-27T19:03:36Z)
• Statistically Optimal Robust Mean and Covariance Estimation for Anisotropic Gaussians [3.5788754401889014]
  強い$varepsilon$-contaminationモデルでは、元のガウスサンプルのベクトルの$varepsilon$分を他のベクトルに置き換えたと仮定する。 我々は、少なくとも1-デルタの確率で満足するコフラ行列 $Sigma の推定器 $widehat Sigma を構築する。
  論文  参考訳（メタデータ） (2023-01-21T23:28:55Z)
• Nonasymptotic one-and two-sample tests in high dimension with unknown covariance structure [0.0]
  テストの問題は、$mu が 0 に対して $eta-閉である場合、すなわち $|mu| geq (eta + delta)$ に対して $|mu| leq eta である。 本研究の目的は,I型とII型の両方の誤差を所定のレベルで制御できるように,最小分離距離$の漸近的上下境界を求めることである。
  論文  参考訳（メタデータ） (2021-09-01T06:22:53Z)
• Variance-Dependent Best Arm Identification [12.058652922228918]
  マルチアームバンディットゲームにおける最適な腕を特定する問題について検討する。 武器の報酬のギャップと分散を探索する適応アルゴリズムを提案する。 このアルゴリズムは2つの対数項に最適であることを示す。
  論文  参考訳（メタデータ） (2021-06-19T04:13:54Z)
• 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)
• Curse of Dimensionality on Randomized Smoothing for Certifiable Robustness [151.67113334248464]
  我々は、他の攻撃モデルに対してスムースな手法を拡張することは困難であることを示す。 我々はCIFARに関する実験結果を示し,その理論を検証した。
  論文  参考訳（メタデータ） (2020-02-08T22:02:14Z)

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

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