論文の概要: MESHA: Mechanism-Enforced Sequential Halving for Strategic Linear Bandits
- arxiv url: http://arxiv.org/abs/2607.14706v1
- Date: Thu, 16 Jul 2026 08:08:58 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-07-17 17:01:33.039297
- Title: MESHA: Mechanism-Enforced Sequential Halving for Strategic Linear Bandits
- Title（参考訳）: MESHA: 戦略線形帯域のためのメカニズム強化シーケンスHalving
- Authors: Xin Li, Zixin Zhong,
- Abstract要約: 戦略線形包帯におけるBest Arm Identification(BAI)のアルゴリズムであるMESHAの設計と解析を行う。
任意のナッシュ平衡を考えると、任意のアームがその特定確率を最大化するためにGCCチェックをパスしようとすることが証明される。
また,現在最先端の線形BAIアルゴリズムが$G$-optimal設計で,このような戦略的環境では失敗することを示した。
- 参考スコア（独自算出の注目度）: 12.674114341828776
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We design and analyze \underline{M}echanism-\underline{E}nforced \underline{S}equential \underline{HA}lving (MESHA), an algorithm for Best Arm Identification (BAI) in strategic linear bandits. In this setting, each arm may strategically misreport its feature vector to maximize the probability of being identified as the best arm, when rewards are generated from the arms' true but unobservable features. The design of MESHA applies the naïve uniform sampling rule and an epoch-wise Grim Trigger Condition (GTC): the former reduces the impact of arms' strategic behaviours and the latter eliminates arms whose reported features severely deviate from the ground truth. Considering an arbitrary Nash Equilibrium, we prove that any arm would attempt to pass the GTC check to maximize its identified probability and derive an upper bound on the failure probability of MESHA within a fixed budget $T$. We also show that state-of-the-art linear BAI algorithms with $G$-optimal design would fail in such strategic environment, as the optimal design (OD)-based sampling rule based on strategically reported features may {\it starve} the optimal arm of any sampling budget. Finally, extensive numerical experiments indicate that MESHA outperforms baselines that rely on OD-based sampling rules as well as the feature-agnostic baselines, corroborating the efficacy of MESHA.
- Abstract（参考訳）: 我々は,戦略的線形包帯におけるBAI(Best Arm Identification)のアルゴリズムである,Shaunderline{M}echanism-\underline{E}nforced \underline{S}equential \underline{HA}lving (MESHA)を設計・解析する。
この設定では、各腕は、その特徴ベクトルを戦略的に誤レポートし、腕の真だが観測不能な特徴から報酬が生成されるとき、最も良い腕と同一視される確率を最大にすることができる。
MESHAの設計はナイーブ一様サンプリング規則とエポックワイズグリムトリガー条件(GTC)を適用し、前者は武器の戦略行動の影響を減らし、後者は報告された特徴が地上の真実から著しく逸脱した武器を除去する。
任意のナッシュ平衡を考えると、任意のアームがその特定確率を最大化するためにGCCチェックを通過させようとし、固定予算$T$でMESHAの故障確率の上限を導出することを証明する。
また, 戦略的に報告された特徴に基づく最適設計(OD)に基づくサンプリングルールは, 任意のサンプリング予算の最適アームを飢えさせる可能性があるため, 最適設計による最先端の線形BAIアルゴリズムがこのような戦略的環境で失敗することを示した。
最後に、広範囲にわたる数値実験により、MESHAはODに基づくサンプリング規則や特徴に依存しないベースラインよりも優れた性能を示し、MESHAの有効性を裏付けている。
関連論文リスト
- Bayesian Best-Arm Identification with Abstention: A Polynomial-to-Exponential Phase Transition [51.253617466579335]
本研究では,学習者が端末の推薦を控えることができるベイジアン固定予算のベストアーム識別問題について検討する。
本研究は,非検出誤りの確率を解析し,吸収を伴わない準最適腕を推奨するリスクについて考察する。
論文 参考訳（メタデータ） (2026-06-28T05:07:27Z) - Fixed-Budget Constrained Best Arm Identification in Grouped Bandits [1.360738859820932]
我々は,各腕が複数の独立した属性と報酬から構成されるグループバンドにおける固定予算制約付きベストアーム識別について検討した。
実現可能性を確保しつつ、最適な腕を識別する新しいアルゴリズムであるFCSRを提案する。
論文 参考訳（メタデータ） (2026-03-04T12:49:56Z) - Best Arm Identification with Fixed Budget: A Large Deviation Perspective [54.305323903582845]
我々は、様々な武器の報酬間の経験的ギャップに基づいて、あらゆるラウンドで腕を拒絶できる真に適応的なアルゴリズムであるsredを提示する。
特に、様々な武器の報酬の間の経験的ギャップに基づいて、あらゆるラウンドで腕を拒絶できる真に適応的なアルゴリズムであるsredを提示する。
論文 参考訳（メタデータ） (2023-12-19T13:17:43Z) - Worst-Case Optimal Multi-Armed Gaussian Best Arm Identification with a
Fixed Budget [10.470114319701576]
本研究は、腕を最も期待できる結果に識別する実験的な設計問題について検討する。
分散が知られているという仮定のもと、一般化ネマン割当(GNA)-経験的ベストアーム(EBA)戦略を提案する。
GNA-EBA戦略は、誤同定の確率が下界と一致するという意味で無限に最適であることを示す。
論文 参考訳（メタデータ） (2023-10-30T17:52:46Z) - 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) - Semiparametric Best Arm Identification with Contextual Information [10.915684166086026]
バンディット問題において,固定予算と文脈情報を用いたベストアーム識別について検討した。
本研究では,ターゲットアロケーション比とレコメンデーションルールを追跡するランダムサンプリングルールとからなる「コンテキストRS-AIPW戦略」を開発する。
提案手法は,予算が無限に進むと,誤識別確率の上限が半下限と一致するため,最適である。
論文 参考訳（メタデータ） (2022-09-15T14:38:47Z) - Fixed-Budget Best-Arm Identification in Structured Bandits [33.27743152847947]
固定予算設定におけるベストアーム識別(BAI)は、学習エージェントが一定の回数の観測後に最適な(ベスト)腕を特定する確率を最大化する盗賊問題である。
結合一般化モデルから平均報酬推定値に基づいて最適アームを除去し,構造を組み込んだ一般トラクタブルアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-06-09T01:32:43Z) - Towards Minimax Optimal Best Arm Identification in Linear Bandits [95.22854522340938]
固定予算設定における線形包帯における最適な腕識別の問題について検討する。
G-最適設計の特性を活用し、アーム割り当て規則に組み込むことにより、パラメータフリーなアルゴリズムを設計する。
OD-LinBAIの故障確率に関する理論的解析を行った。
論文 参考訳（メタデータ） (2021-05-27T09:19:10Z) - Optimal Best-arm Identification in Linear Bandits [79.3239137440876]
サンプルの複雑さが既知のインスタンス固有の下界と一致する単純なアルゴリズムを考案する。
既存のベストアーム識別戦略とは異なり、我々のアルゴリズムは武器の数に依存しない停止規則を用いる。
論文 参考訳（メタデータ） (2020-06-29T14:25:51Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。