論文の概要: Near Optimal Pure Exploration in Logistic Bandits
- arxiv url: http://arxiv.org/abs/2410.20640v1
- Date: Mon, 28 Oct 2024 00:05:57 GMT
- ステータス: 翻訳完了
- システム内更新日: 2024-10-29 12:17:51.476958
- Title: Near Optimal Pure Exploration in Logistic Bandits
- Title（参考訳）: ロジスティック帯域における最適近傍純探索
- Authors: Eduardo Ochoa Rivera, Ambuj Tewari,
- Abstract要約: 一般化線形モデル(GLM)の帯域幅における一般純粋探索問題に対する最初のトラック・アンド・ストップアルゴリズムを開発した。
Log-TSは、期待される複雑性のインスタンス固有の下限を対数係数に近似する効率的なアルゴリズムである。
- 参考スコア（独自算出の注目度）: 17.98959620987217
- License:
- Abstract: Bandit algorithms have garnered significant attention due to their practical applications in real-world scenarios. However, beyond simple settings such as multi-arm or linear bandits, optimal algorithms remain scarce. Notably, no optimal solution exists for pure exploration problems in the context of generalized linear model (GLM) bandits. In this paper, we narrow this gap and develop the first track-and-stop algorithm for general pure exploration problems under the logistic bandit called logistic track-and-stop (Log-TS). Log-TS is an efficient algorithm that asymptotically matches an approximation for the instance-specific lower bound of the expected sample complexity up to a logarithmic factor.
- Abstract（参考訳）: Banditアルゴリズムは、現実のシナリオで実用化されているため、大きな注目を集めている。
しかし、マルチアームや線形バンディットのような単純な設定以外には、最適なアルゴリズムは乏しいままである。
特に、一般化線形モデル(GLM)バンディットの文脈における純粋探索問題に対する最適解は存在しない。
本稿では,このギャップを狭くし,ロジスティック・トラック・アンド・ストップ(Log-TS)と呼ばれるロジスティック・バンディットの下で,一般的な純粋な探索問題に対する最初のトラック・アンド・ストップ・アルゴリズムを開発する。
Log-TSは、予想されるサンプルの複雑性のインスタンス固有の下限の近似を対数係数まで漸近的に近似する効率的なアルゴリズムである。
関連論文リスト
- Indexed Minimum Empirical Divergence-Based Algorithms for Linear Bandits [55.938644481736446]
Indexed Minimum Empirical Divergence (IMED)は、マルチアームバンディット問題に対する非常に効果的なアプローチである。
UCBベースのアルゴリズムとトンプソンサンプリングを実証的に上回ることが観察されている。
我々は、LinIMEDアルゴリズムのファミリーと呼ぶIMEDアルゴリズムの新しい線形バージョンを提案する。
論文 参考訳（メタデータ） (2024-05-24T04:11:58Z) - Nearest Neighbour with Bandit Feedback [4.9094025705644695]
我々のアルゴリズムは、データ生成プロセスに関する仮定が全くなされていない完全に逆向きな設定を処理します。
ユークリッド空間におけるバンドイト問題に適用した場合,アルゴリズムに対する一般的な後悔と解析を行う。
論文 参考訳（メタデータ） (2023-06-23T20:09:01Z) - An Optimal Algorithm for the Real-Valued Combinatorial Pure Exploration
of Multi-Armed Bandit [65.268245109828]
多武装バンディット(R-CPE-MAB)の真価純探査問題について検討する。
既存のR-CPE-MABの手法は、いわゆるトランスダクティブ線形帯域の特殊な場合と見なすことができる。
本稿では,差分探索アルゴリズム (CombGapE) を提案する。
論文 参考訳（メタデータ） (2023-06-15T15:37:31Z) - Optimal Gradient-based Algorithms for Non-concave Bandit Optimization [76.57464214864756]
この研究は、未知の報酬関数が非可逆であるようなバンドイット問題の大群を考察する。
我々のアルゴリズムは、非常に一般化されたゼロ階最適化のパラダイムに基づいている。
標準的な楽観的アルゴリズムは次元因子によって準最適であることを示す。
論文 参考訳（メタデータ） (2021-07-09T16:04:24Z) - 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) - Gamification of Pure Exploration for Linear Bandits [34.16123941778227]
線形バンディットの文脈において、ベストアーム識別を含む活発な純粋探索環境について検討する。
標準的なマルチアームバンディットには最適アルゴリズムが存在するが、リニアバンディットにおけるベストアーム識別のためのアルゴリズムの存在は明白である。
線形帯域における固定信頼純粋探索のための第一の洞察的最適アルゴリズムを設計する。
論文 参考訳（メタデータ） (2020-07-02T08:20:35Z) - Second-Order Guarantees in Centralized, Federated and Decentralized
Nonconvex Optimization [64.26238893241322]
単純なアルゴリズムは、多くの文脈において優れた経験的結果をもたらすことが示されている。
いくつかの研究は、非最適化問題を研究するための厳密な分析的正当化を追求している。
これらの分析における重要な洞察は、摂動が局所的な降下アルゴリズムを許容する上で重要な役割を担っていることである。
論文 参考訳（メタデータ） (2020-03-31T16:54:22Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。