論文の概要: Does 1/2-Tsallis-INF Also Work Well for Best-Arm Identification?

• arxiv url: http://arxiv.org/abs/2608.15365v1
• Date: Sat, 15 Aug 2026 18:38:36 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-08-18 19:59:03.277681
• Title: Does 1/2-Tsallis-INF Also Work Well for Best-Arm Identification?
• Title（参考訳）: 1/2-Tsallis-INFはベストアーム同定にも有効か?
• Abstract要約: 1/2$-Tsallis-INFは、標準的なFTRLアルゴリズムである。 盗賊の対数的擬似回帰を達成しつつ、敵の盗賊の最小限の後悔を保ちながら達成する。 これは自然な疑問を提起する:同じアルゴリズムは、追加の探索なしに、最高の腕を確実に特定できるのか?
• 参考スコア（独自算出の注目度）: 11.223878908981725
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Regret minimization (RM) and best-arm identification (BAI) are two fundamental objectives in multi-armed bandits. Among regret-minimizing algorithms, $1/2$-Tsallis-INF is a canonical best-of-both-worlds FTRL algorithm: it achieves logarithmic pseudo-regret in stochastic bandits while retaining minimax-optimal regret in adversarial bandits, without knowing the environment in advance. This raises a natural question: can the same algorithm, without additional exploration, also identify the best arm reliably? We study this question in stochastic bandits by analyzing the failure probability $\operatorname{Err}_t$, defined as the probability that the empirical best arm determined by the cumulative importance-weighted loss estimates of 1/2-Tsallis-INF differs from the true optimal arm. The main difficulty is that, at the logarithmic-regret scale, suboptimal arms are sampled with probability heuristically of order $1/t$. Consequently, importance weighting causes the cumulative estimator to fluctuate on the same linear scale as its mean separation. To overcome this obstacle, guided by a diffusion toy model, we construct a Lyapunov function for the gap process between the estimated cumulative loss of the optimal arm and that of the best competing arm. This leads to polynomial upper bounds on $\operatorname{Err}_t$: for learning rate $η_t=α/\sqrt t$, $\operatorname{Err}_t$ decays at rate $t^{-2+α^2μ_{i_*}/4+ρ}$ for any $ρ>0$, where $μ_{i_*}$ denotes the mean loss of the true optimal arm. We also establish a lower bound $Ω(t^{-2-\varepsilon})$ for any $\varepsilon>0$, showing that the exponent $2$ is essentially tight.
• Abstract（参考訳）: レジスト最小化(RM)とベストアーム識別(BAI)は、マルチアームバンディットの2つの基本的な目的である。 後悔の最小化アルゴリズムのうち、1/2$-Tsallis-INFは標準的なベスト・オブ・ボス・ワールドのFTRLアルゴリズムである。 これは自然な疑問を提起する:同じアルゴリズムは、追加の探索なしに、最高の腕を確実に特定できるのか? この問題は, 1/2-Tsallis-INFの累積重み付き損失推定値によって決定される経験的最適アームが, 真の最適アームと異なる確率として定義される確率 $\operatorname{Err}_t$ を解析することにより, 確率的帯域幅で検討する。 主な困難は、対数-回帰スケールでは、最適以下の腕は1/t$の確率ヒューリスティックにサンプリングされることである。 その結果、重み付けが重要となり、累積推定器はその平均分離と同じ線形スケールで変動する。 拡散玩具モデルにより導かれるこの障害を克服するため、最適アームの累積損失と最高の競合アームの差分過程のためのリアプノフ関数を構築した。 これは、$\operatorname{Err}_t$: for learning rate $η_t=α/\sqrt t$, $\operatorname{Err}_t$ decays at rate $t^{-2+α^2μ_{i_*}/4+ρ}$ for any $ρ>0$, ここで$μ_{i_*}$は真の最適腕の平均損失を表す。 また、任意の$\varepsilon>0$に対して低い有界$Ω(t^{-2-\varepsilon})$を定め、指数 2$ が本質的にタイトであることを示す。

関連論文リスト

• Bayesian Best-Arm Identification with Abstention: A Polynomial-to-Exponential Phase Transition [51.253617466579335]
  本研究では,学習者が端末の推薦を控えることができるベイジアン固定予算のベストアーム識別問題について検討する。 本研究は,非検出誤りの確率を解析し,吸収を伴わない準最適腕を推奨するリスクについて考察する。
  論文  参考訳（メタデータ） (2026-06-28T05:07:27Z)
• On The Complexity of Best-Arm Identification in Non-Stationary Linear Bandits [15.93884263655552]
  非定常線形包帯における固定予算ベストアーム識別問題について検討する。 学習者は、最大累積報酬$x_* = argmax_xを高い確率でxtopsum_t=1T _t$で識別することを目的とする。
  論文  参考訳（メタデータ） (2026-03-11T02:34:29Z)
• Multiple-play Stochastic Bandits with Prioritized Arm Capacity Sharing [52.124267908936396]
  このモデルは、$M$armと$K$playで構成されている。 各アームには複数の能力があり、各ユニットの能力は報酬関数に関連付けられている。 複数のプレーがアームキャパシティを競う場合、アームキャパシティは第1の優先重みで割り当てられる。
  論文  参考訳（メタデータ） (2025-12-25T11:19:09Z)
• Follow-the-Perturbed-Leader Approaches Best-of-Both-Worlds for the m-Set Semi-Bandit Problems [18.74680577173648]
  我々は、学習者が$m$の腕から$m$の腕を正確に選択する、$m$セット半帯域問題の一般的な場合を考える。 また, Fr'echet 摂動を持つFTPL は, 対向的な設定で, $mathcalO(sqrtnm(sqrtdlog(d)+m5/6)$ をほぼ最適に再現できることを示す。
  論文  参考訳（メタデータ） (2025-04-09T22:07:01Z)
• Nearly Optimal Algorithms for Contextual Dueling Bandits from Adversarial Feedback [58.66941279460248]
  人からのフィードバックから学ぶことは、大言語モデル(LLM)のような生成モデルを調整する上で重要な役割を果たす 本稿では,このドメイン内のモデルについて考察する。-文脈的デュエルバンディット(contextual dueling bandits)と,正の選好ラベルを相手によって反転させることができる対向フィードバック(reversarial feedback)について考察する。 本稿では,不確実性重み付き最大推定に基づく頑健なコンテキストデュエルバンドイット(RCDB)を提案する。
  論文  参考訳（メタデータ） (2024-04-16T17:59:55Z)
• Asymptotically Optimal Pure Exploration for Infinite-Armed Bandits [4.811176167998627]
  我々は、未知の分布から生じる無限に多くのバンドイットアームを用いて純粋探索を研究する。 私たちのゴールは、平均的な報酬が1-delta$の1つの高品質なアームを、最高の$eta$-fraction of armsの1つとして$varepsilon$内で効率的に選択することにあります。
  論文  参考訳（メタデータ） (2023-06-03T04:00:47Z)
• Contextual Combinatorial Bandits with Probabilistically Triggered Arms [55.9237004478033]
  確率的に誘発される腕(C$2$MAB-T)を様々な滑らかさ条件下で検討した。 トリガー変調 (TPM) 条件の下では、C$2$-UC-Tアルゴリズムを考案し、後悔すべき$tildeO(dsqrtT)$を導出する。
  論文  参考訳（メタデータ） (2023-03-30T02:51:00Z)
• Revisiting Simple Regret Minimization in Multi-Armed Bandits [33.88679679593314]
  単純な後悔は、最高の腕や$epsilon$-good腕を欠く確率よりもあまり一般的ではない。 本稿では,データ豊かさ (Tge n$) とデータ貧弱さ (T le n$) の両面において,単純な後悔の上限を改良した。 より困難なデータ・ポーア・レシエーションのために、少なくとも1回は各腕をサンプリングすることなく、同じ改善を享受できるブラッケティングSH(BSH)を提案する。
  論文  参考訳（メタデータ） (2022-10-30T18:31:03Z)
• Causal Bandits for Linear Structural Equation Models [58.2875460517691]
  本稿では,因果図形モデルにおける最適な介入順序を設計する問題について検討する。 グラフの構造は知られており、ノードは$N$である。 頻繁性(UCBベース)とベイズ的設定に2つのアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2022-08-26T16:21:31Z)
• Bandits with many optimal arms [68.17472536610859]
  最適アームの割合は$p*$、最適アームとサブ最適化アームの間の最小平均ギャップは$Delta$と書きます。 我々は,累積的後悔設定と最良腕識別設定の両方において最適な学習率を特徴付ける。
  論文  参考訳（メタデータ） (2021-03-23T11:02:31Z)
• 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 Vector Losses: Minimizing $\ell^\infty$-Norm of Relative Losses [21.085722900446257]
  マルチアームバンディットは、クリック率の最大化を目標とするレコメンデーションシステムに広く適用されている。 本稿では、この状況を複数の損失を伴って、$K$の武器付きバンディットの問題としてモデル化する。
  論文  参考訳（メタデータ） (2020-10-15T23:03:35Z)

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

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