論文の概要: Best-of-Three-Worlds Linear Bandit Algorithm with Variance-Adaptive
Regret Bounds
- arxiv url: http://arxiv.org/abs/2302.12370v1
- Date: Fri, 24 Feb 2023 00:02:24 GMT
- ステータス: 処理完了
- システム内更新日: 2023-02-27 15:00:17.985746
- Title: Best-of-Three-Worlds Linear Bandit Algorithm with Variance-Adaptive
Regret Bounds
- Title（参考訳）: 分散適応的後悔境界を持つ3世界リニアバンディットアルゴリズム
- Authors: Shinji Ito, Kei Takemura
- Abstract要約: 本稿では,2つの階層の環境に適応する線形帯域幅アルゴリズムを提案する。
高いレベルでは、提案アルゴリズムは様々な種類の環境に適応する。
提案アルゴリズムは、最適動作に対する累積損失のすべてに依存する、データ依存の後悔境界を有する。
- 参考スコア（独自算出の注目度）: 27.92755687977196
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: This paper proposes a linear bandit algorithm that is adaptive to
environments at two different levels of hierarchy. At the higher level, the
proposed algorithm adapts to a variety of types of environments. More
precisely, it achieves best-of-three-worlds regret bounds, i.e., of
${O}(\sqrt{T \log T})$ for adversarial environments and of $O(\frac{\log
T}{\Delta_{\min}} + \sqrt{\frac{C \log T}{\Delta_{\min}}})$ for stochastic
environments with adversarial corruptions, where $T$, $\Delta_{\min}$, and $C$
denote, respectively, the time horizon, the minimum sub-optimality gap, and the
total amount of the corruption. Note that polynomial factors in the
dimensionality are omitted here. At the lower level, in each of the adversarial
and stochastic regimes, the proposed algorithm adapts to certain environmental
characteristics, thereby performing better. The proposed algorithm has
data-dependent regret bounds that depend on all of the cumulative loss for the
optimal action, the total quadratic variation, and the path-length of the loss
vector sequence. In addition, for stochastic environments, the proposed
algorithm has a variance-adaptive regret bound of $O(\frac{\sigma^2 \log
T}{\Delta_{\min}})$ as well, where $\sigma^2$ denotes the maximum variance of
the feedback loss. The proposed algorithm is based on the SCRiBLe algorithm. By
incorporating into this a new technique we call scaled-up sampling, we obtain
high-level adaptability, and by incorporating the technique of optimistic
online learning, we obtain low-level adaptability.
- Abstract（参考訳）: 本稿では,2つの階層レベルの環境に適応した線形バンディットアルゴリズムを提案する。
高いレベルでは、提案されたアルゴリズムは様々な種類の環境に適応する。
より正確には、これは3つの世界の最良な後悔境界、すなわち、敵の環境に対して${O}(\sqrt{T \log T})$と$O(\frac{\log T}{\Delta_{\min}} + \sqrt {\frac{C \log T}{\Delta_{\min}}})$に対して$T$、$\Delta_{\min}$および$C$が達成される。
ここでは次元の多項式因子を省略する。
低レベルでは、各対向的および確率的体制において、提案アルゴリズムは特定の環境特性に適応し、より良い性能を発揮する。
提案アルゴリズムは, 最適動作に対する累積損失, 総二次変動, 損失ベクトル列の経路長に依存するデータ依存的残差を持つ。
さらに,確率環境において,提案手法は分散適応的後悔値が$o(\frac{\sigma^2 \log t}{\delta_{\min}})であるのに対し,$\sigma^2$ はフィードバック損失の最大分散を表す。
提案アルゴリズムはscribleアルゴリズムに基づいている。
我々は,この手法をスケールアップサンプリングと呼ぶ新しい手法を取り入れ,高いレベルの適応性を得るとともに,楽観的なオンライン学習手法を取り入れることで,低レベルの適応性を得る。
関連論文リスト
- Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic
Shortest Path [80.60592344361073]
線形混合遷移カーネルを用いた最短経路(SSP)問題について検討する。
エージェントは繰り返し環境と対話し、累積コストを最小化しながら特定の目標状態に到達する。
既存の作業は、イテレーションコスト関数の厳密な下限や、最適ポリシーに対する期待長の上限を仮定することが多い。
論文 参考訳（メタデータ） (2024-02-14T07:52:00Z) - Best-of-Both-Worlds Algorithms for Linear Contextual Bandits [11.94312915280916]
両世界のベスト・オブ・ワールドズ・アルゴリズムを$K$武器付き線形文脈包帯に対して検討する。
我々のアルゴリズムは、敵対的体制と敵対的体制の両方において、ほぼ最適の後悔の限界を提供する。
論文 参考訳（メタデータ） (2023-12-24T08:27:30Z) - Universal Online Learning with Gradient Variations: A Multi-layer Online Ensemble Approach [57.92727189589498]
本稿では,2段階の適応性を持つオンライン凸最適化手法を提案する。
我々は$mathcalO(log V_T)$, $mathcalO(d log V_T)$, $hatmathcalO(sqrtV_T)$ regret bounds for strong convex, exp-concave and convex loss function。
論文 参考訳（メタデータ） (2023-07-17T09:55:35Z) - 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) - Best Policy Identification in Linear MDPs [70.57916977441262]
縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。
複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
論文 参考訳（メタデータ） (2022-08-11T04:12:50Z) - Optimal and Efficient Dynamic Regret Algorithms for Non-Stationary
Dueling Bandits [27.279654173896372]
我々は,非定常的あるいは時間的に異なる選好の下で,$K$のDueling Banditsにおける空力的後悔の最小化問題について検討した。
これは、エージェントが各ラウンドで一対のアイテムを選択し、このペアに対する相対的な二項のウィンロスフィードバックのみを観察するオンライン学習設定である。
論文 参考訳（メタデータ） (2021-11-06T16:46:55Z) - Conservative Stochastic Optimization with Expectation Constraints [11.393603788068777]
本稿では,データ指標や環境変数に関して,目的関数と制約関数が期待する凸最適化問題を考察する。
このような問題を解決するためのオンラインおよび効率的なアプローチは、広く研究されていない。
本稿では、制約違反をゼロとし、$Oleft(T-frac12right)$Optimity gapを実現する新しい保守的最適化アルゴリズム(CSOA)を提案する。
論文 参考訳（メタデータ） (2020-08-13T08:56:24Z) - A Two-Timescale Framework for Bilevel Optimization: Complexity Analysis
and Application to Actor-Critic [142.1492359556374]
双レベル最適化は、2レベル構造を示す問題のクラスである。
このような二段階問題に対処するための2段階近似(TTSA)アルゴリズムを提案する。
本稿では,TTSAフレームワークの特殊な事例として,2段階の自然なアクター・クリティカルポリシー最適化アルゴリズムが有用であることを示す。
論文 参考訳（メタデータ） (2020-07-10T05:20:02Z) - Robust estimation via generalized quasi-gradients [28.292300073453877]
最近提案されたロバスト推定問題の多くが効率的に解ける理由を示す。
我々は「一般化された準次数」の存在を識別する
一般化された準勾配が存在することを示し、効率的なアルゴリズムを構築する。
論文 参考訳（メタデータ） (2020-05-28T15:14:33Z) - Towards Better Understanding of Adaptive Gradient Algorithms in
Generative Adversarial Nets [71.05306664267832]
適応アルゴリズムは勾配の歴史を用いて勾配を更新し、深層ニューラルネットワークのトレーニングにおいてユビキタスである。
本稿では,非コンケーブ最小値問題に対するOptimisticOAアルゴリズムの変種を解析する。
実験の結果,適応型GAN非適応勾配アルゴリズムは経験的に観測可能であることがわかった。
論文 参考訳（メタデータ） (2019-12-26T22:10:10Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。