論文の概要: An Experimental Design Approach for Regret Minimization in Logistic
Bandits
- arxiv url: http://arxiv.org/abs/2202.02407v1
- Date: Fri, 4 Feb 2022 21:56:40 GMT
- ステータス: 処理完了
- システム内更新日: 2022-02-08 14:37:21.960872
- Title: An Experimental Design Approach for Regret Minimization in Logistic
Bandits
- Title(参考訳): ロジスティックバンディットにおける後悔最小化のための実験的設計手法
- Authors: Blake Mason, Kwang-Sung Jun, Lalit Jain
- Abstract要約: ロジスティックな盗賊の最大の課題は、潜在的に大きな問題に依存する定数$kappa$への依存を減らすことである。
そこで本研究では,新しいウォームアップサンプリングアルゴリズムを提案する。
- 参考スコア(独自算出の注目度): 26.674062544226636
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In this work we consider the problem of regret minimization for logistic
bandits. The main challenge of logistic bandits is reducing the dependence on a
potentially large problem dependent constant $\kappa$ that can at worst scale
exponentially with the norm of the unknown parameter $\theta_{\ast}$. Abeille
et al. (2021) have applied self-concordance of the logistic function to remove
this worst-case dependence providing regret guarantees like
$O(d\log^2(\kappa)\sqrt{\dot\mu T}\log(|\mathcal{X}|))$ where $d$ is the
dimensionality, $T$ is the time horizon, and $\dot\mu$ is the variance of the
best-arm. This work improves upon this bound in the fixed arm setting by
employing an experimental design procedure that achieves a minimax regret of
$O(\sqrt{d \dot\mu T\log(|\mathcal{X}|)})$. Our regret bound in fact takes a
tighter instance (i.e., gap) dependent regret bound for the first time in
logistic bandits. We also propose a new warmup sampling algorithm that can
dramatically reduce the lower order term in the regret in general and prove
that it can replace the lower order term dependency on $\kappa$ to
$\log^2(\kappa)$ for some instances. Finally, we discuss the impact of the bias
of the MLE on the logistic bandit problem, providing an example where $d^2$
lower order regret (cf., it is $d$ for linear bandits) may not be improved as
long as the MLE is used and how bias-corrected estimators may be used to make
it closer to $d$.
- Abstract(参考訳): 本研究では,ロジスティックバンディットの最小化問題について考察する。
ロジスティックバンディットの主な課題は、未知のパラメータ $\theta_{\ast}$ のノルムで指数関数的に極大にスケール可能な、潜在的に大きな問題依存定数 $\kappa$ への依存を減らすことである。
Abeille et al. (2021) は、この最悪のケース依存を取り除くために、ロジスティック関数の自己一致を適用し、例えば$O(d\log^2(\kappa)\sqrt{\dot\mu T}\log(|\mathcal{X}|))$$d$は次元、$T$は時間軸、$\dot\mu$はベストアームの分散を提供する。
この作業は、$O(\sqrt{d \dot\mu T\log(|\mathcal{X}|)})$のミニマックス後悔を実現する実験的な設計手順を用いることで、固定アーム設定におけるこの境界を改善する。
私たちの後悔は、実際により厳密な例(すなわちギャップ)を、ロジスティックな盗賊の中で初めて従属的後悔とみなす。
また,後悔の下位の項を劇的に減少させ,いくつかのインスタンスに対して$\kappa$ から$\log^2(\kappa)$ への下位の項依存性を置換できる新しいウォームアップサンプリングアルゴリズムを提案する。
最後に、ロジスティック・バンディット問題に対するmleのバイアスの影響について論じ、mleが使用される限り、$d^2$低次の後悔(cf.、リニア・バンディットは$d$)が改善されない可能性がある例と、バイアス補正された推定器が$d$に近いものにどのように使われるかを示す。
関連論文リスト
- Batched Stochastic Bandit for Nondegenerate Functions [8.015503209312786]
本稿では,非退化関数に対するバッチ帯域学習問題について検討する。
本稿では,非退化関数に対するバッチバンドイット問題をほぼ最適に解くアルゴリズムを提案する。
論文 参考訳(メタデータ) (2024-05-09T12:50:16Z) - Improved Regret for Bandit Convex Optimization with Delayed Feedback [50.46856739179311]
遅延フィードバックを伴うバンド凸最適化(BCO)。
我々は,新しいアルゴリズムを開発し,一般にO(sqrtnT3/4+sqrtdT)$の後悔境界を満足していることを証明する。
提案アルゴリズムは,強い凸関数に対して$O((nT)2/3log/3T+dlog T)$に制限された後悔を改善することができることを示す。
論文 参考訳(メタデータ) (2024-02-14T13:08:26Z) - Improved Regret Bounds of (Multinomial) Logistic Bandits via
Regret-to-Confidence-Set Conversion [40.159846982245746]
我々は,オンライン学習アルゴリズムのテキストテキシスタンスのみに基づく凸信頼セットを,後悔の保証付きで構築する。
R2CSを用いて、計算実現可能性を維持しながら、ロジスティックな包帯におけるw.r.t.$S$を厳格に改善する。
我々は,この分析を多項ロジスティック・バンディットにまで拡張し,R2CSの有効性を示した。
論文 参考訳(メタデータ) (2023-10-28T01:27:52Z) - Horizon-Free and Variance-Dependent Reinforcement Learning for Latent
Markov Decision Processes [62.90204655228324]
我々は,後期マルコフ決定過程(LMDP)における強化学習(RL)の文脈を考慮した後悔の最小化について検討した。
我々は,モデル最適化と値最適化の両手法でインスタンス化できる,新しいモデルベースアルゴリズムフレームワークを設計する。
論文 参考訳(メタデータ) (2022-10-20T21:32:01Z) - Variance-Aware Sparse Linear Bandits [64.70681598741417]
余分な線形包帯に対する最悪のミニマックスは$widetildeThetaleft(sqrtdTright)$である。
ノイズがなく、アクションセットが単位球面である良性設定では、ディビジョン・アンド・コンカーを使用して、$widetildemathcal O(1)$ regretを達成することができる。
我々は,任意の分散対応線形帯域幅アルゴリズムを分散対応線形帯域幅アルゴリズムに変換する汎用フレームワークを開発した。
論文 参考訳(メタデータ) (2022-05-26T15:55:44Z) - Generalized Bandit Regret Minimizer Framework in Imperfect Information
Extensive-Form Game [9.933208900617174]
我々は,IIEGのダイナミクスを知らない対話型バンディットフィードバック設定の問題点を考察する。
NEを学習するには、後悔最小化器は、全フィードバック損失勾配$ellt$ by $v(zt)$を推定し、後悔を最小化する。
モデルフリーであり、$O(sqrtX B/T+sqrtY C/T)$から$O()$までの最良の収束率を大幅に向上させる。
論文 参考訳(メタデータ) (2022-03-11T13:45:42Z) - Scale Free Adversarial Multi Armed Bandits [13.757095663704858]
本稿では,MAB(Scale-Free Adversarial Multi Armed Bandit)問題について考察する。
我々はFTRLアルゴリズムを設計するが、これはMABに対する最初の無スケールな後悔の保証が伴う。
また,Bregman Divergencesの局所ノルム下界を求める新しい手法を開発した。
論文 参考訳(メタデータ) (2021-06-08T21:26:57Z) - Minimax Regret for Stochastic Shortest Path [63.45407095296692]
我々は、エージェントが最小の総予想コストで目標状態に達する必要がある最短パス(SSP)問題を研究します。
この設定に対するminimaxの後悔は、$widetilde O(B_star sqrt|S| |A|K)$であり、$B_star$は任意の状態から最適なポリシーの予想コストに拘束されることを示しています。
本アルゴリズムは, 有限水平MDPにおける強化学習の新たな削減を基礎として, エピソードごとのインタイム動作を行う。
論文 参考訳(メタデータ) (2021-03-24T10:11:49Z) - Thresholded Lasso Bandit [70.17389393497125]
Thresholded Lasso banditは、報酬関数を定義するベクトルとスパースサポートを推定するアルゴリズムである。
一般には $mathcalO( log d + sqrtT )$ や $mathcalO( log d + sqrtT )$ としてスケールする非漸近的後悔の上界を確立する。
論文 参考訳(メタデータ) (2020-10-22T19:14:37Z) - Near-optimal Regret Bounds for Stochastic Shortest Path [63.029132134792555]
最短経路 (SSP) は計画と制御においてよく知られた問題であり、エージェントは最小の総コストで目標状態に到達する必要がある。
任意の学習アルゴリズムは、最悪の場合、少なくとも$Omega(B_star sqrt|S| |A|K)$後悔しなければならない。
論文 参考訳(メタデータ) (2020-02-23T09:10:14Z) - Improved Optimistic Algorithms for Logistic Bandits [16.140301473601454]
そこで本稿では,報酬関数の非線形性について,より詳細な検証に基づく新しい楽観的アルゴリズムを提案する。
我々は、$tildemathcalO(sqrtT)$ regretを楽しんでおり、$kappa$に依存しないが、第2の順序の項には依存しないことを示す。
論文 参考訳(メタデータ) (2020-02-18T12:52:32Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。