論文の概要: An Index-based Deterministic Asymptotically Optimal Algorithm for
Constrained Multi-armed Bandit Problems
- arxiv url: http://arxiv.org/abs/2007.14550v1
- Date: Wed, 29 Jul 2020 01:54:22 GMT
- ステータス: 処理完了
- システム内更新日: 2022-11-05 20:01:31.588985
- Title: An Index-based Deterministic Asymptotically Optimal Algorithm for
Constrained Multi-armed Bandit Problems
- Title(参考訳): 制約付きマルチアームバンド問題に対する指数に基づく決定論的漸近的最適アルゴリズム
- Authors: Hyeong Soo Chang
- Abstract要約: 制約付きマルチアームバンディットのモデルでは、インデックスベースの決定論的最適アルゴリズムが存在することを示す。
我々は、T が地平線サイズ、A がバンディットの腕の集合であるような 1-O(|A|Te-T) として与えられる最適性の確率に制限された有限時間を与える。
- 参考スコア(独自算出の注目度): 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: For the model of constrained multi-armed bandit, we show that by construction
there exists an index-based deterministic asymptotically optimal algorithm. The
optimality is achieved by the convergence of the probability of choosing an
optimal feasible arm to one over infinite horizon. The algorithm is built upon
Locatelli et al.'s "anytime parameter-free thresholding" algorithm under the
assumption that the optimal value is known. We provide a finite-time bound to
the probability of the asymptotic optimality given as 1-O(|A|Te^{-T}) where T
is the horizon size and A is the set of the arms in the bandit. We then study a
relaxed-version of the algorithm in a general form that estimates the optimal
value and discuss the asymptotic optimality of the algorithm after a
sufficiently large T with examples.
- Abstract(参考訳): 制約付き多腕バンディットのモデルについて,構成上,指数に基づく決定論的漸近的最適アルゴリズムが存在することを示す。
最適性は、最適実現可能なアームを無限の地平線上で選択する確率の収束によって達成される。
このアルゴリズムはlocationlli et al.の"anytime parameter-free thresholding"アルゴリズムに基づいており、最適値が知られていると仮定している。
我々は、T が地平線の大きさであり、A がバンドイットの腕の集合であるような 1-O(|A|Te^{-T}) として与えられる漸近最適性の確率に制限される有限時間を与える。
次に, 最適値を推定する一般形式におけるアルゴリズムの緩和変換を考察し, 十分大きな t を例とした後のアルゴリズムの漸近的最適性について論じる。
関連論文リスト
- Sample Complexity for Quadratic Bandits: Hessian Dependent Bounds and
Optimal Algorithms [64.10576998630981]
最適なヘッセン依存型サンプルの複雑さを, 初めて厳密に評価した。
ヘシアン非依存のアルゴリズムは、すべてのヘシアンインスタンスに対して最適なサンプル複雑さを普遍的に達成する。
本アルゴリズムにより得られたサンプルの最適複雑さは,重み付き雑音分布においても有効である。
論文 参考訳(メタデータ) (2023-06-21T17:03:22Z) - n-Step Temporal Difference Learning with Optimal n [3.4944387787356344]
我々は,n段階時間差(TD)学習アルゴリズムにおいて,nの最適値を求める問題を考察する。
同時摂動近似を含むモデルフリー最適化手法を用いて最適nを求める。
任意の初期値に対して、n の最適値は SDPSA で達成されることを示す。
論文 参考訳(メタデータ) (2023-03-13T12:44:32Z) - Convergence Rate Analysis for Optimal Computing Budget Allocation
Algorithms [1.713291434132985]
オーディナル最適化(Ordinal Optimization, OO)は、離散イベント動的システムを最適化するための広く研究されている手法である。
OOのよく知られた方法は、最適計算予算配分(OCBA)である。
本稿では,2つのOCBAアルゴリズムについて検討する。
論文 参考訳(メタデータ) (2022-11-27T04:55:40Z) - Non-Convex Optimization with Certificates and Fast Rates Through Kernel
Sums of Squares [68.8204255655161]
非最適化近似問題を考える。
本稿では,最優先計算を保証するアルゴリズムを提案する。
論文 参考訳(メタデータ) (2022-04-11T09:37:04Z) - An Asymptotically Optimal Primal-Dual Incremental Algorithm for
Contextual Linear Bandits [129.1029690825929]
複数の次元に沿った最先端技術を改善する新しいアルゴリズムを提案する。
非文脈線形帯域の特別な場合において、学習地平線に対して最小限の最適性を確立する。
論文 参考訳(メタデータ) (2020-10-23T09:12:47Z) - Adaptive Sampling for Best Policy Identification in Markov Decision
Processes [79.4957965474334]
本稿では,学習者が生成モデルにアクセスできる場合の,割引マルコフ決定(MDP)における最良の政治的識別の問題について検討する。
最先端アルゴリズムの利点を論じ、解説する。
論文 参考訳(メタデータ) (2020-09-28T15:22:24Z) - ROOT-SGD: Sharp Nonasymptotics and Asymptotic Efficiency in a Single
Algorithm [77.71051081132912]
第一次アルゴリズムを用いて,厳密な凸と滑らかな非制約最適化問題の解法について検討する。
emphRecursive One-Over-T Root (ROOTSGD) と呼ばれる小説を考案する。
有限サンプル勾配, 漸近感覚, 感覚を同時に達成することを証明する。
論文 参考訳(メタデータ) (2020-08-28T14:46:56Z) - Gamification of Pure Exploration for Linear Bandits [34.16123941778227]
線形バンディットの文脈において、ベストアーム識別を含む活発な純粋探索環境について検討する。
標準的なマルチアームバンディットには最適アルゴリズムが存在するが、リニアバンディットにおけるベストアーム識別のためのアルゴリズムの存在は明白である。
線形帯域における固定信頼純粋探索のための第一の洞察的最適アルゴリズムを設計する。
論文 参考訳(メタデータ) (2020-07-02T08:20:35Z) - Convergence of adaptive algorithms for weakly convex constrained
optimization [59.36386973876765]
モローエンベロープの勾配のノルムに対して$mathcaltilde O(t-1/4)$収束率を証明する。
我々の分析では、最小バッチサイズが1ドル、定数が1位と2位のモーメントパラメータが1ドル、そしておそらくスムーズな最適化ドメインで機能する。
論文 参考訳(メタデータ) (2020-06-11T17:43:19Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。