論文の概要: Nested bandits

• arxiv url: http://arxiv.org/abs/2206.09348v1
• Date: Sun, 19 Jun 2022 08:08:38 GMT
• ステータス: 処理完了
• システム内更新日: 2022-06-22 19:59:33.864148
• Title: Nested bandits
• Title（参考訳）: ネスト・バンディット
• Authors: Matthieu Martin and Panayotis Mertikopoulos and Thibaud Rahier and Houssam Zenati
• Abstract要約: 多くのオンライン意思決定プロセスにおいて、最適化エージェントは、多くの固有の類似性を持つ多くの選択肢を選択するために呼ばれる。 本研究では,学習者の代替手段の階層的探索を行うネスト指数重み付けアルゴリズムを提案する。 そこで我々は,学習者の後悔に対して,選択肢間の類似度の高いオンライン学習問題を効率的に解決できることを示す一連の厳密な境界点を得る。
• 参考スコア（独自算出の注目度）: 34.793913964978486
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In many online decision processes, the optimizing agent is called to choose between large numbers of alternatives with many inherent similarities; in turn, these similarities imply closely correlated losses that may confound standard discrete choice models and bandit algorithms. We study this question in the context of nested bandits, a class of adversarial multi-armed bandit problems where the learner seeks to minimize their regret in the presence of a large number of distinct alternatives with a hierarchy of embedded (non-combinatorial) similarities. In this setting, optimal algorithms based on the exponential weights blueprint (like Hedge, EXP3, and their variants) may incur significant regret because they tend to spend excessive amounts of time exploring irrelevant alternatives with similar, suboptimal costs. To account for this, we propose a nested exponential weights (NEW) algorithm that performs a layered exploration of the learner's set of alternatives based on a nested, step-by-step selection method. In so doing, we obtain a series of tight bounds for the learner's regret showing that online learning problems with a high degree of similarity between alternatives can be resolved efficiently, without a red bus / blue bus paradox occurring.
• Abstract（参考訳）: 多くのオンライン意思決定プロセスにおいて、最適化エージェントは、多くの固有の類似性を持つ多くの選択肢を選択するために呼ばれる。 本研究では, 組込み型(非組合せ型)類似性の階層を持つ多数の異なる代替品の存在下で, 学習者が後悔を最小限に抑えようとする, 対向型多武装型盗賊問題のクラスであるネスト型盗賊の文脈において, この問題を考察する。 この設定では、指数重みの青写真(ヘッジ、exp3、それらの変種など)に基づく最適アルゴリズムは、類似の非最適コストで無関係な選択肢を探索するのに過度に時間を費やす傾向があるため、重大な後悔をもたらす可能性がある。 そこで本研究では,ネスト化指数重み (nested exponential weights, new) アルゴリズムを提案する。 そこで我々は,選択肢間の類似度が高いオンライン学習問題を,レッドバス/ブルーバスパラドックスを発生させずに効率的に解決できることを示す,学習者の後悔に対する一連の厳密な境界を得る。

関連論文リスト

• 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)
• Discrete Choice Multi-Armed Bandits [0.0]
  本稿では,個別選択モデルのカテゴリとオンライン学習とマルチアームバンディットアルゴリズムの領域の関連性を確立する。 我々は、Exp3アルゴリズムを特定のケースとして包含して、包括的アルゴリズム群に対するサブ線形後悔境界を提供する。 一般化されたネストロジットモデルからインスピレーションを得た,対向多重武装バンディットアルゴリズムの新たなファミリーを導入する。
  論文  参考訳（メタデータ） (2023-10-01T03:41:04Z)
• An Optimal Algorithm for the Real-Valued Combinatorial Pure Exploration of Multi-Armed Bandit [65.268245109828]
  多武装バンディット(R-CPE-MAB)の真価純探査問題について検討する。 既存のR-CPE-MABの手法は、いわゆるトランスダクティブ線形帯域の特殊な場合と見なすことができる。 本稿では,差分探索アルゴリズム (CombGapE) を提案する。
  論文  参考訳（メタデータ） (2023-06-15T15:37:31Z)
• Variance-Dependent Regret Bounds for Linear Bandits and Reinforcement Learning: Adaptivity and Computational Efficiency [90.40062452292091]
  本稿では,不整合雑音を持つ線形帯域に対する計算効率のよい最初のアルゴリズムを提案する。 我々のアルゴリズムは未知のノイズの分散に適応し、$tildeO(d sqrtsum_k = 1K sigma_k2 + d)$ regretを達成する。 また、強化学習において、線形混合マルコフ決定過程(MDP)に対する分散適応アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-02-21T00:17:24Z)
• Stochastic Rising Bandits [40.32303434592863]
  本研究は、腕が単調に非減少している、安静時および安静時バンディットの特定の症例について検討する。 この特性により、ペイオフの規則性を利用して、厳密な後悔の限界を提供する、特別に構築されたアルゴリズムを設計することができる。 我々は,本アルゴリズムを実世界のデータセットに対するオンラインモデル選択問題や,複数の合成されたタスクに対する非定常MABの最先端手法と経験的に比較した。
  論文  参考訳（メタデータ） (2022-12-07T17:30:45Z)
• Upper Confidence Bounds for Combining Stochastic Bandits [52.10197476419621]
  バンディットアルゴリズムを結合する簡単な手法を提案する。 私たちのアプローチは、個々のbanditアルゴリズムのそれぞれを、より高いレベルのn$-armed bandit問題のアームとして扱う"meta-ucb"手順に基づいています。
  論文  参考訳（メタデータ） (2020-12-24T05:36:29Z)
• Regret Bound Balancing and Elimination for Model Selection in Bandits and RL [34.15978290083909]
  バンディットおよび強化学習問題におけるアルゴリズムの簡易モデル選択手法を提案する。 我々は、このアプローチの総後悔は、最も有効な候補者の後悔の回数が乗算的要因であることを証明します。 線形バンディットのモデル選択における最近の取り組みとは違って,我々のアプローチは,敵の環境によってコンテキスト情報が生成されるケースをカバーできるほど多用途である。
  論文  参考訳（メタデータ） (2020-12-24T00:53:42Z)
• Model Selection in Contextual Stochastic Bandit Problems [51.94632035240787]
  基本アルゴリズムを選択できるメタアルゴリズムを開発した。 基本アルゴリズムの1つが$O(sqrtT)$後悔している場合でも、一般的には$Omega(sqrtT)$後悔よりも良いものを得ることはできません。
  論文  参考訳（メタデータ） (2020-03-03T18:46:34Z)

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

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