論文の概要: On the Finite-Time Performance of the Knowledge Gradient Algorithm
- arxiv url: http://arxiv.org/abs/2206.06847v1
- Date: Tue, 14 Jun 2022 13:42:05 GMT
- ステータス: 処理完了
- システム内更新日: 2022-06-15 14:14:16.022227
- Title: On the Finite-Time Performance of the Knowledge Gradient Algorithm
- Title（参考訳）: 知識勾配アルゴリズムの有限時間性能について
- Authors: Yanwen Li and Siyang Gao
- Abstract要約: 知識勾配(KG)アルゴリズムは、ベストアーム識別(BAI)問題に対して人気があり効果的なアルゴリズムである。
KGアルゴリズムの有限時間性能に関する新しい理論的結果を示す。
- 参考スコア（独自算出の注目度）: 1.713291434132985
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The knowledge gradient (KG) algorithm is a popular and effective algorithm
for the best arm identification (BAI) problem. Due to the complex calculation
of KG, theoretical analysis of this algorithm is difficult, and existing
results are mostly about the asymptotic performance of it, e.g., consistency,
asymptotic sample allocation, etc. In this research, we present new theoretical
results about the finite-time performance of the KG algorithm. Under
independent and normally distributed rewards, we derive lower bounds and upper
bounds for the probability of error and simple regret of the algorithm. With
these bounds, existing asymptotic results become simple corollaries. We also
show the performance of the algorithm for the multi-armed bandit (MAB) problem.
These developments not only extend the existing analysis of the KG algorithm,
but can also be used to analyze other improvement-based algorithms. Last, we
use numerical experiments to further demonstrate the finite-time behavior of
the KG algorithm.
- Abstract（参考訳）: 知識勾配(KG)アルゴリズムは、ベストアーム識別(BAI)問題に対して人気があり効果的なアルゴリズムである。
KGの複雑な計算のため、このアルゴリズムの理論解析は困難であり、既存の結果は主として、一貫性、漸近的なサンプル割り当てなど、その漸近的な性能に関するものである。
本研究では,kgアルゴリズムの有限時間性能に関する新たな理論的結果を示す。
独立で正規に分散した報酬の下では、エラーの確率とアルゴリズムの単純な後悔のために下限と上限を導出する。
これらの境界により、既存の漸近的な結果が単純な系譜となる。
また,mab (multi-armed bandit) 問題に対するアルゴリズムの性能を示す。
これらの発展は、既存の kg アルゴリズムの解析を拡張するだけでなく、他の改良に基づくアルゴリズムの分析にも利用できる。
最後に、KGアルゴリズムの有限時間挙動をさらに実証するために数値実験を用いる。
関連論文リスト
- Iterative Quantum Algorithms for Maximum Independent Set: A Tale of
Low-Depth Quantum Algorithms [0.0]
我々は、反復最大量子アルゴリズム(Iterative Maximum Quantum Algorithms)と呼ばれる、量子最適化のための新しいハイブリッドアプローチのクラスについて研究する。
深度$p=1$のQAOAの場合、このアルゴリズムはMISの古典的欲求アルゴリズムと全く同じ操作と選択を行う。
論文 参考訳（メタデータ） (2023-09-22T18:00:03Z) - Dual Algorithmic Reasoning [9.701208207491879]
本稿では,基礎となるアルゴリズム問題の双対性を利用してアルゴリズムを学習することを提案する。
アルゴリズム学習における最適化問題の2つの定義を同時に学習することで、より良い学習が可能になることを実証する。
次に、難易度の高い脳血管分類タスクにデプロイすることで、二元アルゴリズム推論の現実的な実用性を検証する。
論文 参考訳（メタデータ） (2023-02-09T08:46:23Z) - Amortized Implicit Differentiation for Stochastic Bilevel Optimization [53.12363770169761]
決定論的条件と決定論的条件の両方において、二段階最適化問題を解決するアルゴリズムのクラスについて検討する。
厳密な勾配の推定を補正するために、ウォームスタート戦略を利用する。
このフレームワークを用いることで、これらのアルゴリズムは勾配の偏りのない推定値にアクセス可能な手法の計算複雑性と一致することを示す。
論文 参考訳（メタデータ） (2021-11-29T15:10:09Z) - Fractal Structure and Generalization Properties of Stochastic
Optimization Algorithms [71.62575565990502]
最適化アルゴリズムの一般化誤差は、その一般化尺度の根底にあるフラクタル構造の複雑性'にバウンドできることを示す。
さらに、特定の問題(リニア/ロジスティックレグレッション、隠れ/層ニューラルネットワークなど)とアルゴリズムに対して、結果をさらに専門化します。
論文 参考訳（メタデータ） (2021-06-09T08:05:36Z) - Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
本稿では,線形モデルから信号整数を推定する古典整数最小二乗問題について検討する。
問題はNPハードであり、信号処理、バイオインフォマティクス、通信、機械学習といった様々な応用でしばしば発生する。
本稿では, 深いニューラルネットワークを用いて, 単純化されたメモリバウンドA*アルゴリズムの最適推定を推定し, HATSアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-01-07T08:00:02Z) - Polynomial-Time Algorithms for Counting and Sampling Markov Equivalent
DAGs [6.252236971703546]
因果解析において、有向非巡回グラフ(DAG)の計数と一様サンプリングが基本である。
本稿では,これらのタスクをグラフィカルな時間から実行し,この領域における長年にわたるオープンな課題を解決できることを示す。
我々のアルゴリズムは効果的で容易に実装できる。
論文 参考訳（メタデータ） (2020-12-17T15:47:15Z) - An Asymptotically Optimal Primal-Dual Incremental Algorithm for
Contextual Linear Bandits [129.1029690825929]
複数の次元に沿った最先端技術を改善する新しいアルゴリズムを提案する。
非文脈線形帯域の特別な場合において、学習地平線に対して最小限の最適性を確立する。
論文 参考訳（メタデータ） (2020-10-23T09:12:47Z) - The limits of min-max optimization algorithms: convergence to spurious
non-critical sets [82.74514886461257]
min-max最適化アルゴリズムは周期サイクルや同様の現象が存在するため、はるかに大きな問題に遭遇する。
問題のどの点も引き付けないアルゴリズムが存在することを示す。
ほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほとんどである。
論文 参考訳（メタデータ） (2020-06-16T10:49:27Z) - Active Model Estimation in Markov Decision Processes [108.46146218973189]
マルコフ決定過程(MDP)をモデル化した環境の正確なモデル学習のための効率的な探索の課題について検討する。
マルコフに基づくアルゴリズムは,本アルゴリズムと極大エントロピーアルゴリズムの両方を小サンプル方式で上回っていることを示す。
論文 参考訳（メタデータ） (2020-03-06T16:17:24Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。