論文の概要: Best-of-three-worlds Analysis for Linear Bandits with
Follow-the-regularized-leader Algorithm
- arxiv url: http://arxiv.org/abs/2303.06825v2
- Date: Tue, 18 Jul 2023 06:50:43 GMT
- ステータス: 処理完了
- システム内更新日: 2023-07-19 19:07:28.716948
- Title: Best-of-three-worlds Analysis for Linear Bandits with
Follow-the-regularized-leader Algorithm
- Title（参考訳）: Follow-the-regularized-Leadアルゴリズムによる線形帯域の3次元最適解析
- Authors: Fang Kong, Canzhe Zhao, Shuai Li
- Abstract要約: 線形バンディット問題は、双方の相反する環境で長年研究されてきた。
citetLeeLWZ021は、損失タイプを積極的に検出し、特定の設定のために特別に設計された異なるアルゴリズムを切り替えるアルゴリズムを提案する。
FTRL(Follow-the-regularized-leader)は、異なる環境に適応可能な人気アルゴリズムの一種である。
- 参考スコア（独自算出の注目度）: 11.80907528239756
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The linear bandit problem has been studied for many years in both stochastic
and adversarial settings. Designing an algorithm that can optimize the
environment without knowing the loss type attracts lots of interest.
\citet{LeeLWZ021} propose an algorithm that actively detects the loss type and
then switches between different algorithms specially designed for specific
settings. However, such an approach requires meticulous designs to perform well
in all environments. Follow-the-regularized-leader (FTRL) is another type of
popular algorithm that can adapt to different environments. This algorithm is
of simple design and the regret bounds are shown to be optimal in traditional
multi-armed bandit problems compared with the detect-switch type. Designing an
FTRL-type algorithm for linear bandits is an important question that has been
open for a long time. In this paper, we prove that the FTRL algorithm with a
negative entropy regularizer can achieve the best-of-three-world results for
the linear bandit problem. Our regret bounds achieve the same or nearly the
same order as the previous detect-switch type algorithm but with a much simpler
algorithmic design.
- Abstract（参考訳）: 線形バンディット問題は、確率的および対角的設定の両方において長年研究されてきた。
損失タイプを知らずに環境を最適化できるアルゴリズムを設計することは、多くの関心を集めている。
\citet{LeeLWZ021} は、損失タイプを積極的に検出し、特定の設定のために特別に設計された異なるアルゴリズムを切り替えるアルゴリズムを提案する。
しかし、このようなアプローチはあらゆる環境でうまく機能するために精巧な設計を必要とする。
FTRL(Follow-the-regularized-leader)は、異なる環境に適応可能な人気アルゴリズムの一種である。
このアルゴリズムは単純な設計であり, 従来のマルチアームバンディット問題において, 検出スウィッチ型と比較して, 後悔境界が最適であることが示されている。
線形バンディットのためのFTRL型アルゴリズムの設計は、長い間開かれてきた重要な問題である。
本稿では, 負エントロピー正規化器を用いたFTRLアルゴリズムが線形バンディット問題に対して最適3次元結果が得られることを示す。
我々の後悔の限界は、以前の検出スイッチ型アルゴリズムと同じかほぼ同じ順序で達成されるが、アルゴリズム設計はずっと単純である。
関連論文リスト
- Optimism in the Face of Ambiguity Principle for Multi-Armed Bandits [6.7310264583128445]
FTRL (Follow-The-Regularized-Leader) アルゴリズムは、しばしば敵対的問題や盗賊問題に対して最適な後悔を味わう。
本稿では,逆方向と多重方向の両方の帯域に対して最適なポリシを生成する新しいFTPLアルゴリズムを提案する。
論文 参考訳（メタデータ） (2024-09-30T16:00:23Z) - Indexed Minimum Empirical Divergence-Based Algorithms for Linear Bandits [55.938644481736446]
Indexed Minimum Empirical Divergence (IMED)は、マルチアームバンディット問題に対する非常に効果的なアプローチである。
UCBベースのアルゴリズムとトンプソンサンプリングを実証的に上回ることが観察されている。
我々は、LinIMEDアルゴリズムのファミリーと呼ぶIMEDアルゴリズムの新しい線形バージョンを提案する。
論文 参考訳（メタデータ） (2024-05-24T04:11:58Z) - Making RL with Preference-based Feedback Efficient via Randomization [11.019088464664696]
人間のフィードバックから学習する強化学習アルゴリズムは、統計複雑性、計算複雑性、クエリ複雑性の点で効率的である必要がある。
提案するアルゴリズムは, サンプル効率のよいアルゴリズム(すなわち, ほぼ最適ケースの後悔境界)と実行時間(すなわち, 関連するパラメータに関して計算複雑性が最悪の場合)を提案する。
結果をより一般的な非線形関数近似に拡張するために、トンプソンサンプリングのアイデアに触発されたモデルベースランダム化アルゴリズムを設計する。
論文 参考訳（メタデータ） (2023-10-23T04:19:35Z) - Stability-penalty-adaptive follow-the-regularized-leader: Sparsity,
game-dependency, and best-of-both-worlds [46.30750729936261]
FTRL(Follow-the-regularized-leader)は近年,バンドイット問題における適応性獲得の最も有望なアプローチの1つである。
我々は3種類の適応性を持ついくつかのアルゴリズムを確立する:空間性、ゲーム依存性、およびベスト・オブ・ボス・ワールド(BOBW)である。
論文 参考訳（メタデータ） (2023-05-26T23:20:48Z) - Best-of-Three-Worlds Linear Bandit Algorithm with Variance-Adaptive
Regret Bounds [27.92755687977196]
本稿では,2つの階層の環境に適応する線形帯域幅アルゴリズムを提案する。
高いレベルでは、提案アルゴリズムは様々な種類の環境に適応する。
提案アルゴリズムは、最適動作に対する累積損失のすべてに依存する、データ依存の後悔境界を有する。
論文 参考訳（メタデータ） (2023-02-24T00:02:24Z) - Machine Learning for Online Algorithm Selection under Censored Feedback [71.6879432974126]
オンラインアルゴリズム選択(OAS)では、アルゴリズム問題クラスのインスタンスがエージェントに次々に提示され、エージェントは、固定された候補アルゴリズムセットから、おそらく最高のアルゴリズムを迅速に選択する必要がある。
SAT(Satisfiability)のような決定問題に対して、品質は一般的にアルゴリズムのランタイムを指す。
本研究では,OASのマルチアームバンディットアルゴリズムを再検討し,この問題に対処する能力について議論する。
ランタイム指向の損失に適応し、時間的地平線に依存しない空間的・時間的複雑さを維持しながら、部分的に検閲されたデータを可能にする。
論文 参考訳（メタデータ） (2021-09-13T18:10:52Z) - Optimal Gradient-based Algorithms for Non-concave Bandit Optimization [76.57464214864756]
この研究は、未知の報酬関数が非可逆であるようなバンドイット問題の大群を考察する。
我々のアルゴリズムは、非常に一般化されたゼロ階最適化のパラダイムに基づいている。
標準的な楽観的アルゴリズムは次元因子によって準最適であることを示す。
論文 参考訳（メタデータ） (2021-07-09T16:04:24Z) - Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
本稿では,線形モデルから信号整数を推定する古典整数最小二乗問題について検討する。
問題はNPハードであり、信号処理、バイオインフォマティクス、通信、機械学習といった様々な応用でしばしば発生する。
本稿では, 深いニューラルネットワークを用いて, 単純化されたメモリバウンドA*アルゴリズムの最適推定を推定し, HATSアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-01-07T08:00:02Z) - Gamification of Pure Exploration for Linear Bandits [34.16123941778227]
線形バンディットの文脈において、ベストアーム識別を含む活発な純粋探索環境について検討する。
標準的なマルチアームバンディットには最適アルゴリズムが存在するが、リニアバンディットにおけるベストアーム識別のためのアルゴリズムの存在は明白である。
線形帯域における固定信頼純粋探索のための第一の洞察的最適アルゴリズムを設計する。
論文 参考訳（メタデータ） (2020-07-02T08:20:35Z) - Accelerated Message Passing for Entropy-Regularized MAP Inference [89.15658822319928]
離散値のランダムフィールドにおけるMAP推論の最大化は、機械学習の基本的な問題である。
この問題の難しさから、特殊メッセージパッシングアルゴリズムの導出には線形プログラミング(LP)緩和が一般的である。
古典的加速勾配の根底にある手法を活用することにより,これらのアルゴリズムを高速化するランダム化手法を提案する。
論文 参考訳（メタデータ） (2020-07-01T18:43:32Z) - Model Selection in Contextual Stochastic Bandit Problems [51.94632035240787]
基本アルゴリズムを選択できるメタアルゴリズムを開発した。
基本アルゴリズムの1つが$O(sqrtT)$後悔している場合でも、一般的には$Omega(sqrtT)$後悔よりも良いものを得ることはできません。
論文 参考訳（メタデータ） (2020-03-03T18:46:34Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。