論文の概要: Approximation Theory Based Methods for RKHS Bandits
- arxiv url: http://arxiv.org/abs/2010.12167v5
- Date: Mon, 26 Jul 2021 02:04:09 GMT
- ステータス: 処理完了
- システム内更新日: 2022-10-03 21:50:46.474555
- Title: Approximation Theory Based Methods for RKHS Bandits
- Title(参考訳): RKHS帯域に対する近似理論に基づく手法
- Authors: Sho Takemori, Masahiro Sato
- Abstract要約: RKHSバンディット問題は、ノイズフィードバックを伴う非線形関数のオンライン最適化問題である。
逆 RKHS バンディット問題に対する一般アルゴリズムは存在しない。
本稿では, RKHSバンドイット問題に対する効率的なアルゴリズムと, RKHSバンドイット問題に対する最初の一般アルゴリズムを提案する。
- 参考スコア(独自算出の注目度): 9.391375268580806
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The RKHS bandit problem (also called kernelized multi-armed bandit problem)
is an online optimization problem of non-linear functions with noisy feedback.
Although the problem has been extensively studied, there are unsatisfactory
results for some problems compared to the well-studied linear bandit case.
Specifically, there is no general algorithm for the adversarial RKHS bandit
problem. In addition, high computational complexity of existing algorithms
hinders practical application. We address these issues by considering a novel
amalgamation of approximation theory and the misspecified linear bandit
problem. Using an approximation method, we propose efficient algorithms for the
stochastic RKHS bandit problem and the first general algorithm for the
adversarial RKHS bandit problem. Furthermore, we empirically show that one of
our proposed methods has comparable cumulative regret to IGP-UCB and its
running time is much shorter.
- Abstract(参考訳): RKHSバンディット問題(英: RKHS bandit problem)は、非線形関数の雑音フィードバックによるオンライン最適化問題である。
この問題は広範囲に研究されているが、よく研究された線形バンディットの場合と比較して、いくつかの問題には不十分な結果がある。
具体的には、逆RKHSバンディット問題に対する一般的なアルゴリズムは存在しない。
加えて、既存のアルゴリズムの計算量が高いと実用的応用が妨げられる。
近似理論と不特定の線形バンディット問題の新しい融合を考えることにより,これらの問題に対処する。
近似法を用いて,確率的RKHSバンディット問題に対する効率的なアルゴリズムと,対角的RKHSバンディット問題に対する最初の一般アルゴリズムを提案する。
さらに,提案手法の1つが IGP-UCB に匹敵する累積的後悔であり,実行時間がはるかに短いことを実証的に示す。
関連論文リスト
- 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) - Optimal Gradient-based Algorithms for Non-concave Bandit Optimization [76.57464214864756]
この研究は、未知の報酬関数が非可逆であるようなバンドイット問題の大群を考察する。
我々のアルゴリズムは、非常に一般化されたゼロ階最適化のパラダイムに基づいている。
標準的な楽観的アルゴリズムは次元因子によって準最適であることを示す。
論文 参考訳(メタデータ) (2021-07-09T16:04:24Z) - A Simple Unified Framework for High Dimensional Bandit Problems [33.139925285802825]
本稿では,アルゴリズムの上界を後悔する一般的な解析フレームワークを提案する。
本アルゴリズムは,異なる高次元バンディット問題に適用できることを示した。
論文 参考訳(メタデータ) (2021-02-18T21:35:32Z) - Upper Confidence Bounds for Combining Stochastic Bandits [52.10197476419621]
バンディットアルゴリズムを結合する簡単な手法を提案する。
私たちのアプローチは、個々のbanditアルゴリズムのそれぞれを、より高いレベルのn$-armed bandit問題のアームとして扱う"meta-ucb"手順に基づいています。
論文 参考訳(メタデータ) (2020-12-24T05:36:29Z) - An Asymptotically Optimal Primal-Dual Incremental Algorithm for
Contextual Linear Bandits [129.1029690825929]
複数の次元に沿った最先端技術を改善する新しいアルゴリズムを提案する。
非文脈線形帯域の特別な場合において、学習地平線に対して最小限の最適性を確立する。
論文 参考訳(メタデータ) (2020-10-23T09:12:47Z) - A PAC algorithm in relative precision for bandit problem with costly
sampling [0.0]
本稿ではまず,この離散最適化問題に対して,相対的精度でほぼ正解(PAC)を得るための単純帯域幅アルゴリズムを提案する。
また、同一の保証付きPACソリューションを提供する適応的帯域幅アルゴリズムを提案する。
論文 参考訳(メタデータ) (2020-07-30T09:22:25Z) - Corralling Stochastic Bandit Algorithms [54.10645564702416]
相関アルゴリズムの後悔は、最も報酬の高い腕を含む最高のアルゴリズムの後悔よりも悪くはないことを示す。
最高報酬と他の報酬の差は、最高報酬と他の報酬の差に依存することを示す。
論文 参考訳(メタデータ) (2020-06-16T15:33:12Z) - Corruption-Tolerant Gaussian Process Bandit Optimization [130.60115798580136]
未知(典型的には非生成)関数を有界ノルムで最適化する問題を考察する。
我々は「高速だが非ローバスト」と「スロー」に基づく高速スローGP-UCBに基づくアルゴリズムを提案する。
ある種の依存関係は、汚職レベルによっては要求できない、と我々は主張する。
論文 参考訳(メタデータ) (2020-03-04T09:46:58Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。