論文の概要: Optimal Best Arm Identification with Post-Action Context

• arxiv url: http://arxiv.org/abs/2502.03061v1
• Date: Wed, 05 Feb 2025 10:47:05 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-02-06 14:26:59.131233
• Title: Optimal Best Arm Identification with Post-Action Context
• Title（参考訳）: 行動後文脈を用いた最適な腕の同定
• Authors: Mohammad Shahverdikondori, Amir Mohammad Abouei, Alireza Rezaeimoghadam, Negar Kiyavash,
• Abstract要約: 動作後コンテキストを用いたベストアーム識別の問題を紹介する。 動作後コンテキストの2つの異なるタイプを解析する。 非セパレータ設定では、トラック・アンド・ストップのアルゴリズムをこの設定に拡張できることを実証する。 セパレータ設定では,コンテキスト空間の幾何学を用いてアクションではなくコンテキストを直接追跡する「textitG-tracking$」という新しいサンプリングルールを提案する。
• 参考スコア（独自算出の注目度）: 15.613350380708798
• License:
• Abstract: We introduce the problem of best arm identification (BAI) with post-action context, a new BAI problem in a stochastic multi-armed bandit environment and the fixed-confidence setting. The problem addresses the scenarios in which the learner receives a $\textit{post-action context}$ in addition to the reward after playing each action. This post-action context provides additional information that can significantly facilitate the decision process. We analyze two different types of the post-action context: (i) $\textit{non-separator}$, where the reward depends on both the action and the context, and (ii) $\textit{separator}$, where the reward depends solely on the context. For both cases, we derive instance-dependent lower bounds on the sample complexity and propose algorithms that asymptotically achieve the optimal sample complexity. For the non-separator setting, we do so by demonstrating that the Track-and-Stop algorithm can be extended to this setting. For the separator setting, we propose a novel sampling rule called $\textit{G-tracking}$, which uses the geometry of the context space to directly track the contexts rather than the actions. Finally, our empirical results showcase the advantage of our approaches compared to the state of the art.
• Abstract（参考訳）: 本稿では, 動作後状況を考慮したベストアーム識別(BAI)問題, 確率的マルチアームバンディット環境における新しいBAI問題, 固定信頼設定を導入する。 問題は、学習者が各アクションを再生した後の報酬に加えて、$\textit{post-action context}$を受け取るシナリオに対処する。 このポストアクションコンテキストは、決定プロセスを大幅に促進できる追加情報を提供する。 我々は、ポストアクションコンテキストの2つの異なるタイプを分析する。 i) $\textit{non-separator}$ ここでは、報酬はアクションとコンテキストの両方に依存します。 (ii) $\textit{separator}$ ここでは、報酬はコンテキストのみに依存する。 どちらの場合も、サンプルの複雑さに対するインスタンス依存の低い境界を導出し、漸近的に最適なサンプルの複雑さを達成するアルゴリズムを提案する。 非セパレータ設定では、トラック・アンド・ストップのアルゴリズムをこの設定に拡張できることを実証する。 セパレータ設定では,コンテキスト空間の幾何学を用いてアクションではなくコンテキストを直接追跡する,$\textit{G-tracking}$という新しいサンプリングルールを提案する。 最後に、私たちの経験的な結果は、最先端技術と比較して、私たちのアプローチの利点を示しています。

関連論文リスト

• Breaking the $\log(1/Δ_2)$ Barrier: Better Batched Best Arm Identification with Adaptive Grids [28.547030766096956]
  ほぼ最適なサンプル複雑性を実現するアルゴリズムを導入し、インスタンスに敏感なバッチ複雑性を特徴とする。 我々は、この枠組みを線形包帯におけるバッチ化されたベストアーム識別の問題に拡張し、同様の改善を実現する。
  論文  参考訳（メタデータ） (2025-01-29T01:40:36Z)
• Combinatorial Stochastic-Greedy Bandit [79.1700188160944]
  我々は,選択した$n$のアームセットのジョイント報酬以外の余分な情報が観測されない場合に,マルチアームのバンディット問題に対する新規グリーディ・バンディット(SGB)アルゴリズムを提案する。 SGBは最適化された拡張型コミットアプローチを採用しており、ベースアームの大きなセットを持つシナリオ用に特別に設計されている。
  論文  参考訳（メタデータ） (2023-12-13T11:08:25Z)
• Variance-Aware Regret Bounds for Stochastic Contextual Dueling Bandits [53.281230333364505]
  本稿では, 一般化線形モデル(GLM)から, デュエルアームのバイナリ比較を生成するコンテキストデュエルバンド問題について検討する。 本稿では,SupLinUCB型アルゴリズムを提案する。このアルゴリズムは,計算効率と分散を意識したリセットバウンド$tilde Obig(dsqrtsum_t=1Tsigma_t2 + dbig)$を提案する。 我々の後悔は、比較が決定論的である場合の直感的な期待と自然に一致し、アルゴリズムは$tilde O(d)$ regretにのみ悩まされる。
  論文  参考訳（メタデータ） (2023-10-02T08:15:52Z)
• Context-lumpable stochastic bandits [49.024050919419366]
  我々は、$S$コンテキストと$K$アクションによる文脈的盗賊問題を考える。 我々は,最大$widetilde O(r (S +K )/epsilon2)$サンプルを用いて,$epsilon$-optimal Policyを出力するアルゴリズムを提案する。 後悔の設定では、T$までの累積後悔を$widetilde O(sqrtr3(S+K)T)$で束縛するアルゴリズムを与える。
  論文  参考訳（メタデータ） (2023-06-22T17:20:30Z)
• Tractable Optimality in Episodic Latent MABs [75.17357040707347]
  我々は、エージェントが時間ステップ$H$のエピソードのために環境と対話する、M$遅延コンテキストを持つマルチアームバンディット問題を考える。 エピソードの長さによっては、学習者は遅れた文脈を正確に見積もることができないかもしれない。 我々は、$O(textttpoly(A) + textttpoly(M,H)min(M,H))$インタラクションを用いて、ほぼ最適なポリシーを確実に学習する手順を設計する。
  論文  参考訳（メタデータ） (2022-10-05T22:53:46Z)
• Instance-optimal PAC Algorithms for Contextual Bandits [20.176752818200438]
  この作業では、$(epsilon,delta)$-$textitPAC$設定における帯域幅の問題に焦点を当てます。 最良腕識別のための最小限の後悔最小化とインスタンス依存のPACを同時に行うアルゴリズムは存在しないことを示す。
  論文  参考訳（メタデータ） (2022-07-05T23:19:43Z)
• Stochastic Contextual Dueling Bandits under Linear Stochastic Transitivity Models [25.336599480692122]
  我々は,コンテキスト情報を用いた決闘バンディット問題における後悔の最小化タスクについて検討する。 本稿では,フィードバックプロセスの模倣に基づく計算効率のよいアルゴリズムである$texttCoLSTIM$を提案する。 本実験は,CoLSTモデルの特殊事例に対する最先端アルゴリズムよりも優れていることを示す。
  論文  参考訳（メタデータ） (2022-02-09T17:44:19Z)
• Nearly Dimension-Independent Sparse Linear Bandit over Small Action Spaces via Best Subset Selection [71.9765117768556]
  本研究では,高次元線形モデルの下での文脈的帯域問題について考察する。 この設定は、パーソナライズされたレコメンデーション、オンライン広告、パーソナライズされた医療など、不可欠な応用を見出す。 本稿では,最適部分集合選択法を用いて2重成長エポックを推定する手法を提案する。
  論文  参考訳（メタデータ） (2020-09-04T04:10:39Z)
• Regret Minimization in Stochastic Contextual Dueling Bandits [40.17224226373741]
  我々は、コンテキスト設定において、$K$武装デュエルバンディットの問題を考察する。 提案手法は, それぞれ, 後悔の保証を施した2つのアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-02-20T06:36:19Z)
• The Simulator: Understanding Adaptive Sampling in the Moderate-Confidence Regime [52.38455827779212]
  エミュレータと呼ばれる適応サンプリングを解析するための新しい手法を提案する。 適切なログファクタを組み込んだトップk問題の最初のインスタンスベースの下位境界を証明します。 我々の新しい分析は、後者の問題に対するこの種の最初のエミュレータであるベストアームとトップkの識別に、シンプルでほぼ最適であることを示した。
  論文  参考訳（メタデータ） (2017-02-16T23:42:02Z)

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

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