論文の概要: Non-Asymptotic Analysis of (Sticky) Track-and-Stop

• arxiv url: http://arxiv.org/abs/2505.22475v1
• Date: Wed, 28 May 2025 15:26:55 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-05-29 17:35:50.693193
• Title: Non-Asymptotic Analysis of (Sticky) Track-and-Stop
• Title（参考訳）: Sticky)トラック・アンド・ストップの非漸近解析
• Authors: Riccardo Poiani, Martino Bernasconi, Andrea Celli,
• Abstract要約: 純粋な探索問題では、統計学者が順次情報を収集し、いくつかの未知の環境に関する質問に答える。 Track-and-Stopアルゴリズムはこれらの問題を解決する先駆的な手法である。 両アルゴリズムに漸近的でない保証を提供する。
• 参考スコア（独自算出の注目度）: 15.79182979494432
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: In pure exploration problems, a statistician sequentially collects information to answer a question about some stochastic and unknown environment. The probability of returning a wrong answer should not exceed a maximum risk parameter $\delta$ and good algorithms make as few queries to the environment as possible. The Track-and-Stop algorithm is a pioneering method to solve these problems. Specifically, it is well-known that it enjoys asymptotic optimality sample complexity guarantees for $\delta\to 0$ whenever the map from the environment to its correct answers is single-valued (e.g., best-arm identification with a unique optimal arm). The Sticky Track-and-Stop algorithm extends these results to settings where, for each environment, there might exist multiple correct answers (e.g., $\epsilon$-optimal arm identification). Although both methods are optimal in the asymptotic regime, their non-asymptotic guarantees remain unknown. In this work, we fill this gap and provide non-asymptotic guarantees for both algorithms.
• Abstract（参考訳）: 純粋な探索問題では、統計学者が順次情報を収集し、確率的で未知の環境に関する質問に答える。 間違った答えを返す確率は、最大リスクパラメータ$\delta$を超えるべきではない。 Track-and-Stopアルゴリズムはこれらの問題を解決する先駆的な手法である。 具体的には、環境から正しい答えへの写像が単値になるたびに$\delta\to 0$の漸近的最適性サンプル複雑性が保証されることが知られている(例えば、一意の最適腕を持つベストアーム識別)。 Sticky Track-and-Stopアルゴリズムはこれらの結果を、各環境に対して複数の正しい回答(例えば$\epsilon$-optimal arm identification)が存在するような設定にまで拡張する。 どちらの方法も漸近的体制において最適であるが、その非漸近的保証は未だ不明である。 本研究では,このギャップを埋め,両アルゴリズムに漸近的でない保証を与える。

関連論文リスト

• Optimal Top-Two Method for Best Arm Identification and Fluid Analysis [15.353009236788262]
  最適な腕識別問題に対する最適トップ2型アルゴリズムを提案する。 提案アルゴリズムは$delta rightarrow 0$として最適であることを示す。
  論文  参考訳（メタデータ） (2024-03-14T06:14:07Z)
• Best Policy Identification in Linear MDPs [70.57916977441262]
  縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。 複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
  論文  参考訳（メタデータ） (2022-08-11T04:12:50Z)
• Choosing Answers in $\varepsilon$-Best-Answer Identification for Linear Bandits [0.8122270502556374]
  純粋探索問題では、情報を逐次収集して環境問題に答える。 平均値の高い解を選択すると、期待されるサンプルの複雑さの観点からアルゴリズムが最適に到達できないことを示す。 導出線形帯域における$varepsilon$-best-answer識別にベストアーム識別アルゴリズムを適用するための簡単な手法を開発した。
  論文  参考訳（メタデータ） (2022-06-09T12:27:51Z)
• 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)
• Optimal and instance-dependent guarantees for Markovian linear stochastic approximation [47.912511426974376]
  標準スキームの最後の繰り返しの2乗誤差に対して、$t_mathrmmix tfracdn$の非漸近境界を示す。 マルコフ雑音による政策評価について,これらの結果のまとめを導出する。
  論文  参考訳（メタデータ） (2021-12-23T18:47:50Z)
• Mean-based Best Arm Identification in Stochastic Bandits under Reward Contamination [80.53485617514707]
  本稿では,ギャップベースアルゴリズムと逐次除去に基づく2つのアルゴリズムを提案する。 具体的には、ギャップベースのアルゴリズムでは、サンプルの複雑さは定数要素まで最適であり、連続的な除去では対数因子まで最適である。
  論文  参考訳（メタデータ） (2021-11-14T21:49:58Z)
• Navigating to the Best Policy in Markov Decision Processes [68.8204255655161]
  マルコフ決定過程における純粋探索問題について検討する。 エージェントはアクションを逐次選択し、結果のシステム軌道から可能な限り早くベストを目標とする。
  論文  参考訳（メタデータ） (2021-06-05T09:16:28Z)
• ROOT-SGD: Sharp Nonasymptotics and Near-Optimal Asymptotics in a Single Algorithm [71.13558000599839]
  第一次アルゴリズムを用いて,厳密な凸と滑らかな非制約最適化問題の解法について検討する。 我々は,過去の勾配を平均化し,実装が容易な小説「Recursive One-Over-T SGD」を考案した。 有限サンプル, 漸近感覚, 感覚の両面において, 最先端の性能を同時に達成できることを実証する。
  論文  参考訳（メタデータ） (2020-08-28T14:46:56Z)

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

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