論文の概要: Second Order Bounds for Contextual Bandits with Function Approximation

• arxiv url: http://arxiv.org/abs/2409.16197v1
• Date: Tue, 24 Sep 2024 15:42:04 GMT
• ステータス: 処理完了
• システム内更新日: 2024-09-26 05:17:23.294683
• Title: Second Order Bounds for Contextual Bandits with Function Approximation
• Title（参考訳）: 関数近似を用いた文脈帯域の2次境界
• Authors: Aldo Pacchiano,
• Abstract要約: 我々は,時間軸の平方根ではなく,測定分散の総和の平方根と,スケーリングの残差を満たすアルゴリズムを開発した。 これらの境界は文脈線形問題において2階境界を導出する既存の手法を一般化する。
• 参考スコア（独自算出の注目度）: 26.066203222936124
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Many works have developed algorithms no-regret algorithms for contextual bandits with function approximation, where the mean rewards over context-action pairs belongs to a function class. Although there are many approaches to this problem, one that has gained in importance is the use of algorithms based on the optimism principle such as optimistic least squares. It can be shown the regret of this algorithm scales as square root of the product of the eluder dimension (a statistical measure of the complexity of the function class), the logarithm of the function class size and the time horizon. Unfortunately, even if the variance of the measurement noise of the rewards at each time is changing and is very small, the regret of the optimistic least squares algorithm scales with square root of the time horizon. In this work we are the first to develop algorithms that satisfy regret bounds of scaling not with the square root of the time horizon, but the square root of the sum of the measurement variances in the setting of contextual bandits with function approximation when the variances are unknown. These bounds generalize existing techniques for deriving second order bounds in contextual linear problems.
• Abstract（参考訳）: 多くの研究が、文脈-作用対に対する平均報酬が関数クラスに属する関数近似を伴う文脈的帯域幅のアルゴリズムを開発した。 この問題には多くのアプローチがあるが、楽観的な最小二乗のような楽観主義原理に基づくアルゴリズムの利用が重要になった。 このアルゴリズムの後悔は、ユーラダー次元の積の平方根(関数クラスの複雑性の統計測度)、関数クラスサイズの対数、時間地平線としてスケールすることを示している。 残念なことに、各時点における報酬の測定ノイズのばらつきが変化し、非常に小さいとしても、楽観的な最小二乗アルゴリズムの後悔は時間軸の平方根でスケールする。 この研究において、時間軸の平方根ではなく、その分散が未知のときに関数近似を伴う文脈的帯域の設定における測定分散の和の平方根のスケーリング境界を満たすアルゴリズムを最初に開発した。 これらの境界は文脈線形問題において2階境界を導出する既存の手法を一般化する。

関連論文リスト

• Learning the Positions in CountSketch [49.57951567374372]
  本稿では,まずランダムなスケッチ行列に乗じてデータを圧縮し,最適化問題を高速に解くスケッチアルゴリズムについて検討する。 本研究では,ゼロでないエントリの位置を最適化する学習ベースアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-06-11T07:28:35Z)
• Gradient-free optimization of highly smooth functions: improved analysis and a new algorithm [87.22224691317766]
  この研究は、目的関数が極めて滑らかであるという仮定の下で、ゼロ次ノイズオラクル情報による問題を研究する。 ゼロオーダー射影勾配勾配アルゴリズムを2種類検討する。
  論文  参考訳（メタデータ） (2023-06-03T17:05:13Z)
• Efficient and Optimal Algorithms for Contextual Dueling Bandits under Realizability [59.81339109121384]
  我々は,学習者が文脈情報を用いて2つの決定を下す連続的な決定設定であるK$コンテキストデュエルバンディット問題について検討するが,一方の判断が他方よりも優れていることを示唆する強調基準に基づくフィードバックのみを観察する。 提案手法は, 最善応答後悔という新たな概念に対して, 最善応答後悔に対する最適後悔率を実現するアルゴリズムである。
  論文  参考訳（メタデータ） (2021-11-24T07:14:57Z)
• Practical, Provably-Correct Interactive Learning in the Realizable Setting: The Power of True Believers [12.09273192079783]
  我々は、対話型学習を実現可能な設定で検討し、最適な腕の識別からアクティブな分類に至るまでの問題に対処する一般的な枠組みを開発する。 我々は,最小限の値と対数係数とを一致させる,計算効率のよい新しいアルゴリズムを設計する。
  論文  参考訳（メタデータ） (2021-11-09T02:33:36Z)
• An Asymptotically Optimal Primal-Dual Incremental Algorithm for Contextual Linear Bandits [129.1029690825929]
  複数の次元に沿った最先端技術を改善する新しいアルゴリズムを提案する。 非文脈線形帯域の特別な場合において、学習地平線に対して最小限の最適性を確立する。
  論文  参考訳（メタデータ） (2020-10-23T09:12:47Z)
• Exploiting Higher Order Smoothness in Derivative-free Optimization and Continuous Bandits [99.70167985955352]
  強凸関数のゼロ次最適化問題について検討する。 予測勾配降下アルゴリズムのランダム化近似を考察する。 その結果,0次アルゴリズムはサンプルの複雑性や問題パラメータの点でほぼ最適であることが示唆された。
  論文  参考訳（メタデータ） (2020-06-14T10:42:23Z)
• SONIA: A Symmetric Blockwise Truncated Optimization Algorithm [2.9923891863939938]
  本研究は, 経験的リスクに対する新しいアルゴリズムを提案する。 このアルゴリズムは、一部分空間における二階探索型更新を計算し、1階探索法と2階探索法の間のギャップを埋める。
  論文  参考訳（メタデータ） (2020-06-06T19:28:14Z)
• The estimation error of general first order methods [12.472245917779754]
  我々は,高次元回帰と低次元行列推定という2種類の推定問題を考察する。 我々は、観測数とパラメータ数の両方が分岐する高次元最適値の誤差を下界に導出する。 これらの下界は、推定誤差が下界とわずかに無視可能な項に一致するアルゴリズムが存在することを意味している。
  論文  参考訳（メタデータ） (2020-02-28T18:13:47Z)
• Lagrangian Decomposition for Neural Network Verification [148.0448557991349]
  ニューラルネットワーク検証の基本的なコンポーネントは、出力が取ることのできる値のバウンダリの計算である。 ラグランジアン分解に基づく新しい手法を提案する。 ランニングタイムのごく一部で、既成の解法に匹敵するバウンダリが得られることを示す。
  論文  参考訳（メタデータ） (2020-02-24T17:55:10Z)
• TopRank+: A Refinement of TopRank Algorithm [0.0]
  トポロジカルソートに基づく新しいオンライン学習アルゴリズムが提案された。 本研究では、ある暗黙関数の混合と拡張の手法を用いて、不等式に対してより厳密で反復的なログのような境界を与える。
  論文  参考訳（メタデータ） (2020-01-21T15:44:44Z)

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

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