論文の概要: A conversion theorem and minimax optimality for continuum contextual bandits

• arxiv url: http://arxiv.org/abs/2406.05714v5
• Date: Wed, 12 Mar 2025 01:15:47 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-03-13 12:13:53.084769
• Title: A conversion theorem and minimax optimality for continuum contextual bandits
• Title（参考訳）: 連続的文脈的包帯に対する変換定理とミニマックス最適性
• Authors: Arya Akhavan, Karim Lounici, Massimiliano Pontil, Alexandre B. Tsybakov,
• Abstract要約: 本研究では,学習者が側情報ベクトルを逐次受信し,凸集合内の行動を選択する,文脈連続帯域幅問題について検討する。 目標は、受信したコンテキストのすべての基盤関数を最小化することです。 サブ線形の静的な後悔を達成するアルゴリズムを拡張して、サブ線形の文脈的後悔を実現することができることを示す。
• 参考スコア（独自算出の注目度）: 70.71582850199871
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study the contextual continuum bandits problem, where the learner sequentially receives a side information vector and has to choose an action in a convex set, minimizing a function associated with the context. The goal is to minimize all the underlying functions for the received contexts, leading to the contextual notion of regret, which is stronger than the standard static regret. Assuming that the objective functions are $\gamma$-H\"older with respect to the contexts, $0<\gamma\le 1,$ we demonstrate that any algorithm achieving a sub-linear static regret can be extended to achieve a sub-linear contextual regret. We prove a static-to-contextual regret conversion theorem that provides an upper bound for the contextual regret of the output algorithm as a function of the static regret of the input algorithm. We further study the implications of this general result for three fundamental cases of dependency of the objective function on the action variable: (a) Lipschitz bandits, (b) convex bandits, (c) strongly convex and smooth bandits. For Lipschitz bandits and $\gamma=1,$ combining our results with the lower bound of Slivkins (2014), we prove that the minimax optimal contextual regret for the noise-free adversarial setting is achieved. Then, we prove that in the presence of noise, the contextual regret rate as a function of the number of queries is the same for convex bandits as it is for strongly convex and smooth bandits. Lastly, we present a minimax lower bound, implying two key facts. First, obtaining a sub-linear contextual regret may be impossible over functions that are not continuous with respect to the context. Second, for convex bandits and strongly convex and smooth bandits, the algorithms that we propose achieve, up to a logarithmic factor, the minimax optimal rate of contextual regret as a function of the number of queries.
• Abstract（参考訳）: 本研究では,学習者が側情報ベクトルを逐次受信し,コンベックスセットのアクションを選択する場合のコンテキスト連続帯域幅問題について検討し,そのコンテキストに関連する関数を最小化する。 目標は、受信したコンテキストの根底にあるすべての関数を最小化することであり、標準的な静的な後悔よりも強い、後悔という文脈的な概念に繋がる。 目的関数が文脈に関して $\gamma$-H\er であると仮定すると、$0<\gamma\le 1,$ は、サブ線形な静的な後悔を達成するアルゴリズムが、サブ線形な文脈的後悔を達成するために拡張可能であることを示す。 我々は,入力アルゴリズムの静的な後悔の関数として,出力アルゴリズムの文脈的後悔の上限を与える静的から文脈的後悔の変換定理を証明した。 目的関数の動作変数への依存性の基本的な3つのケースについて、この一般的な結果の意味をさらに研究する。 (a)リプシッツの盗賊。 (b)凸帯 (c)強い凸と滑らかな包帯。 Lipschitz bandits と $\gamma=1,$ と Slivkins (2014) の下位境界を組み合わせれば、雑音のない対向的な設定に対する最小限の文脈的後悔が達成できることが証明できる。 そして,ノイズの存在下では,問合せ回数の関数としての文脈的後悔率は,凸包帯と強い凸包帯と滑らかな包帯の場合と同じであることを示す。 最後に、2つの重要な事実を暗示するミニマックス下界を示す。 まず、文脈に関して連続でない関数に対して、サブ線形の文脈的後悔を得ることは不可能である。 第二に、凸包帯と強凸および滑らかな包帯に対して、我々の提案するアルゴリズムは対数係数まで、クエリ数の関数としての文脈的後悔の最小値である。

関連論文リスト

• Sparse Nonparametric Contextual Bandits [2.0072624123275533]
  本稿では,関連する特徴を同時に学習し,文脈的盗賊問題における後悔を最小限に抑えることの課題について検討する。 我々は、スパース非パラメトリックな文脈的包帯問題(sparse nonparametric contextual bandit)と呼ばれる新しい文脈的包帯問題を紹介し、分析する。 スパシティとアクションの数に対して地平線が十分に大きい限り、スパシティは常により良い後悔境界を可能にする。
  論文  参考訳（メタデータ） (2025-03-20T17:44:56Z)
• Stochastic Zeroth-Order Optimization under Strongly Convexity and Lipschitz Hessian: Minimax Sample Complexity [59.75300530380427]
  本稿では,アルゴリズムが検索対象関数の雑音評価にのみアクセス可能な2次スムーズかつ強い凸関数を最適化する問題を考察する。 本研究は, ミニマックス単純後悔率について, 一致した上界と下界を発達させることにより, 初めて厳密な評価を行ったものである。
  論文  参考訳（メタデータ） (2024-06-28T02:56:22Z)
• Nearly Optimal Algorithms for Contextual Dueling Bandits from Adversarial Feedback [58.66941279460248]
  人からのフィードバックから学ぶことは、大言語モデル(LLM)のような生成モデルを調整する上で重要な役割を果たす 本稿では,このドメイン内のモデルについて考察する。-文脈的デュエルバンディット(contextual dueling bandits)と,正の選好ラベルを相手によって反転させることができる対向フィードバック(reversarial feedback)について考察する。 本稿では,不確実性重み付き最大推定に基づく頑健なコンテキストデュエルバンドイット(RCDB)を提案する。
  論文  参考訳（メタデータ） (2024-04-16T17:59:55Z)
• On the Optimal Regret of Locally Private Linear Contextual Bandit [18.300225068036642]
  局所的なプライベートな文脈的帯域に対して,$tilde O(sqrtT)$ regret upper bound を達成可能であることを示す。 我々の解決策は、いくつかの新しいアルゴリズム的および分析的アイデアに依存している。
  論文  参考訳（メタデータ） (2024-04-15T02:00:24Z)
• Proportional Response: Contextual Bandits for Simple and Cumulative Regret Minimization [29.579719765255927]
  本稿では,文脈的帯域幅設定のための効率的な帯域幅アルゴリズムのファミリーを提案する。 我々のアルゴリズムは任意の関数クラスで動作し、不特定性をモデル化するのに堅牢で、連続したアーム設定で使用できます。
  論文  参考訳（メタデータ） (2023-07-05T08:34:54Z)
• High dimensional stochastic linear contextual bandit with missing covariates [19.989315104929354]
  バンドイット問題における最近の研究は、逐次決定設定においてラッソ収束理論を採用した。 1) 条件付き準ガウス雑音下での制限された固有値条件を証明すること、2) 文脈変数と選択された行動の間の依存を考慮に入れること。
  論文  参考訳（メタデータ） (2022-07-22T16:06:22Z)
• On Kernelized Multi-Armed Bandits with Constraints [16.102401271318012]
  一般に未知の報酬関数と一般未知の制約関数を併用した帯域幅問題について検討する。 本稿では,アルゴリズムの性能解析のための一般的なフレームワークを提案する。 本稿では,数値実験により提案アルゴリズムの優れた性能を示す。
  論文  参考訳（メタデータ） (2022-03-29T14:02:03Z)
• Dynamic Regret of Online Mirror Descent for Relatively Smooth Convex Cost Functions [30.412826613009518]
  リプシッツ連続性も均一な滑らか性も存在しない場合でも、動的後悔を束縛することは可能であることを示す。 次に、相対的に強い凸性の付加条件により、動的後悔は経路長と勾配変化によって境界付けられることを示す。
  論文  参考訳（メタデータ） (2022-02-25T17:35:07Z)
• Adaptivity and Non-stationarity: Problem-dependent Dynamic Regret for Online Convex Optimization [70.4342220499858]
  本稿では,スムーズさを生かし,問題依存量による動的後悔のT$への依存を補う新しいオンラインアルゴリズムを提案する。 この結果が本質的な難易度に適応しているのは, 既往の結果よりも厳密であり, 最悪の場合, 同一レートの保護が可能であるからである。
  論文  参考訳（メタデータ） (2021-12-29T02:42:59Z)
• Efficient and Optimal Algorithms for Contextual Dueling Bandits under Realizability [59.81339109121384]
  我々は,学習者が文脈情報を用いて2つの決定を下す連続的な決定設定であるK$コンテキストデュエルバンディット問題について検討するが,一方の判断が他方よりも優れていることを示唆する強調基準に基づくフィードバックのみを観察する。 提案手法は, 最善応答後悔という新たな概念に対して, 最善応答後悔に対する最適後悔率を実現するアルゴリズムである。
  論文  参考訳（メタデータ） (2021-11-24T07:14:57Z)
• Minimax Optimization: The Case of Convex-Submodular [50.03984152441271]
  ミニマックス問題は連続領域を超えて連続離散領域や完全離散領域にまで拡張される。 連続変数に関して目的が凸であり、離散変数に関して部分モジュラーであるような凸-部分モジュラーミニマックス問題のクラスを導入する。 提案アルゴリズムは反復的であり、離散最適化と連続最適化の両方のツールを組み合わせる。
  論文  参考訳（メタデータ） (2021-11-01T21:06:35Z)
• Exact Asymptotics for Linear Quadratic Adaptive Control [6.287145010885044]
  最も単純な非帯域強化学習問題である線形二次制御(LQAC)について検討する。 ステップワイズ更新LQACアルゴリズムの残差,推定誤差,予測誤差の式を導出する。 安定系と不安定系のシミュレーションにおいて、我々の理論はアルゴリズムの有限サンプル挙動を著しくよく記述している。
  論文  参考訳（メタデータ） (2020-11-02T22:43:30Z)
• On Lower Bounds for Standard and Robust Gaussian Process Bandit Optimization [55.937424268654645]
  有界ノルムを持つ関数のブラックボックス最適化問題に対するアルゴリズム非依存な下界を考える。 本稿では, 単純さ, 汎用性, エラー確率への依存性の向上など, 後悔の下位境界を導出するための新しい証明手法を提案する。
  論文  参考訳（メタデータ） (2020-08-20T03:48:14Z)
• Dynamic Regret of Convex and Smooth Functions [93.71361250701075]
  非定常環境におけるオンライン凸最適化について検討する。 パフォーマンス指標として動的後悔を選択します。 本研究では, 滑らかさを活かして, 動的後悔をさらに高めることが可能であることを示す。
  論文  参考訳（メタデータ） (2020-07-07T14:10:57Z)
• Stochastic Bandits with Linear Constraints [69.757694218456]
  制約付き文脈線形帯域設定について検討し、エージェントの目標は一連のポリシーを作成することである。 楽観的悲観的線形帯域(OPLB)と呼ばれる,この問題に対する高信頼束縛アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-06-17T22:32:19Z)
• Exploiting Higher Order Smoothness in Derivative-free Optimization and Continuous Bandits [99.70167985955352]
  強凸関数のゼロ次最適化問題について検討する。 予測勾配降下アルゴリズムのランダム化近似を考察する。 その結果,0次アルゴリズムはサンプルの複雑性や問題パラメータの点でほぼ最適であることが示唆された。
  論文  参考訳（メタデータ） (2020-06-14T10:42:23Z)

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

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