論文の概要: Smooth Bandit Optimization: Generalization to H\"older Space

• arxiv url: http://arxiv.org/abs/2012.06076v1
• Date: Fri, 11 Dec 2020 01:43:25 GMT
• ステータス: 処理完了
• システム内更新日: 2021-05-11 03:10:32.977527
• Title: Smooth Bandit Optimization: Generalization to H\"older Space
• Title（参考訳）: Smooth Bandit Optimization: H\"古い空間への一般化
• Authors: Yusha Liu, Yining Wang, Aarti Singh
• Abstract要約: 我々は、目標が累積後悔である滑らかな報酬関数のバンディット最適化を考える。 私たちの主な結果は、指数 $alpha>1$ を持つ H"older space への報酬関数の一般化です。 私たちは、$alphaleq 1$サブセット内で、既存の下限に適合する後悔率を達成することを示します。
• 参考スコア（独自算出の注目度）: 37.15553727896912
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We consider bandit optimization of a smooth reward function, where the goal is cumulative regret minimization. This problem has been studied for $\alpha$-H\"older continuous (including Lipschitz) functions with $0<\alpha\leq 1$. Our main result is in generalization of the reward function to H\"older space with exponent $\alpha>1$ to bridge the gap between Lipschitz bandits and infinitely-differentiable models such as linear bandits. For H\"older continuous functions, approaches based on random sampling in bins of a discretized domain suffices as optimal. In contrast, we propose a class of two-layer algorithms that deploy misspecified linear/polynomial bandit algorithms in bins. We demonstrate that the proposed algorithm can exploit higher-order smoothness of the function by deriving a regret upper bound of $\tilde{O}(T^\frac{d+\alpha}{d+2\alpha})$ for when $\alpha>1$, which matches existing lower bound. We also study adaptation to unknown function smoothness over a continuous scale of H\"older spaces indexed by $\alpha$, with a bandit model selection approach applied with our proposed two-layer algorithms. We show that it achieves regret rate that matches the existing lower bound for adaptation within the $\alpha\leq 1$ subset.
• Abstract（参考訳）: 目的が累積後悔最小化である円滑な報酬関数の帯域最適化を考える。 この問題は、$0<\alpha\leq 1$のリプシッツを含む$\alpha$-h\"older連続函数に対して研究されている。 我々の主な結果は、リプシッツバンドイットとリニアバンドイットのような無限微分可能なモデルの間のギャップを埋めるために、指数$\alpha>1$のh\"older空間への報酬関数の一般化である。 h\"older連続関数に対しては、離散化領域のビンのランダムサンプリングに基づくアプローチが最適である。 対照的に、不特定線形/ポリノミアル帯域幅アルゴリズムをビンに展開する2層アルゴリズムのクラスを提案する。 提案アルゴリズムは, 既存の下界に一致するような$\alpha>1$に対して, $\tilde{O}(T^\frac{d+\alpha}{d+2\alpha})$ の残差上限を導出することにより, 関数の高次滑らか性を利用することができることを示す。 また,提案した2層アルゴリズムを用いた帯域モデル選択手法を用いて,H\"古い空間の連続スケールにおける未知関数の滑らか性への適応性についても検討した。 我々は、$\alpha\leq 1$ のサブセット内で、既存の下限に適合する後悔率を達成することを示す。

関連論文リスト

• Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic Shortest Path [80.60592344361073]
  線形混合遷移カーネルを用いた最短経路(SSP)問題について検討する。 エージェントは繰り返し環境と対話し、累積コストを最小化しながら特定の目標状態に到達する。 既存の作業は、イテレーションコスト関数の厳密な下限や、最適ポリシーに対する期待長の上限を仮定することが多い。
  論文  参考訳（メタデータ） (2024-02-14T07:52:00Z)
• Fast UCB-type algorithms for stochastic bandits with heavy and super heavy symmetric noise [45.60098988395789]
  マルチアームバンディットのためのUCB型アルゴリズムを構築するための新しいアルゴリズムを提案する。 報酬の対称雑音の場合、$O(log TsqrtKTlog T)$ regret bound を $Oleft の代わりに達成できることを示す。
  論文  参考訳（メタデータ） (2024-02-10T22:38:21Z)
• Efficient Frameworks for Generalized Low-Rank Matrix Bandit Problems [61.85150061213987]
  一般化線形モデル (GLM) フレームワークを用いて, citelu2021low で提案した一般化低ランク行列帯域問題について検討する。 既存のアルゴリズムの計算不可能性と理論的制約を克服するため,まずG-ESTTフレームワークを提案する。 G-ESTT は $tildeO(sqrt(d_1+d_2)3/2Mr3/2T)$ bound of regret を達成でき、G-ESTS は $tildeO を達成できることを示す。
  論文  参考訳（メタデータ） (2024-01-14T14:14:19Z)
• Gradient-free optimization of highly smooth functions: improved analysis and a new algorithm [87.22224691317766]
  この研究は、目的関数が極めて滑らかであるという仮定の下で、ゼロ次ノイズオラクル情報による問題を研究する。 ゼロオーダー射影勾配勾配アルゴリズムを2種類検討する。
  論文  参考訳（メタデータ） (2023-06-03T17:05:13Z)
• On the Interplay Between Misspecification and Sub-optimality Gap in Linear Contextual Bandits [76.2262680277608]
  本研究では,線形関数クラスによって期待される報酬関数を近似できるような,不特定条件下での線形文脈帯域について検討する。 このアルゴリズムは, 対数的因子に比例した設定において, ギャップ依存の残差が$tilde O (d2/Delta)$と同じであることを示す。
  論文  参考訳（メタデータ） (2023-03-16T15:24:29Z)
• Best Policy Identification in Linear MDPs [70.57916977441262]
  縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。 複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
  論文  参考訳（メタデータ） (2022-08-11T04:12:50Z)
• Nearly Optimal Algorithms for Level Set Estimation [21.83736847203543]
  線形包帯に対する最近の適応的実験設計手法と関連づけることで, レベルセット推定問題に対する新しいアプローチを提案する。 我々は、我々の境界がほぼ最適であることを示す。すなわち、我々の上限は、しきい値線形帯域に対して既存の下限と一致する。
  論文  参考訳（メタデータ） (2021-11-02T17:45:02Z)
• Gaussian Process Bandit Optimization with Few Batches [49.896920704012395]
  有限腕バンディットアルゴリズムにインスパイアされたバッチアルゴリズムを導入する。 O(log T)$ batches in time horizon $T$.sqrtTgamma_T)$ using $O(log T)$ batches in time horizon。 さらに,アルゴリズムの修正版を提案し,バッチ数によって後悔がどう影響するかを特徴付ける。
  論文  参考訳（メタデータ） (2021-10-15T00:54:04Z)
• Regret Lower Bound and Optimal Algorithm for High-Dimensional Contextual Linear Bandit [10.604939762790517]
  我々は、累積後悔に対して、$mathcalObig((log d)fracalpha+12Tfrac1-alpha2+log Tbig)$をミニマックス下界として証明する。 第2に,汎用的なアッパー信頼境界(UCB)戦略に着想を得た,シンプルで効率的なアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-09-23T19:35:38Z)
• Low-Rank Generalized Linear Bandit Problems [19.052901817304743]
  低ランク線型バンドイット問題において、作用の報酬は、作用と未知の低ランク行列$Theta*$の間の内部積である。 低ランク行列の被覆によって構築される指数重み付き平均予測器と、オンラインから信頼度セットへの変換パバシ2012onlineの新たな組み合わせに基づくアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-06-04T15:30:14Z)

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

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