論文の概要: ANACONDA: An Improved Dynamic Regret Algorithm for Adaptive
Non-Stationary Dueling Bandits
- arxiv url: http://arxiv.org/abs/2210.14322v1
- Date: Tue, 25 Oct 2022 20:26:02 GMT
- ステータス: 処理完了
- システム内更新日: 2022-10-27 13:19:17.739320
- Title: ANACONDA: An Improved Dynamic Regret Algorithm for Adaptive
Non-Stationary Dueling Bandits
- Title（参考訳）: ANACONDA: 適応型非定常デュエル帯域に対する動的レグレットアルゴリズムの改良
- Authors: Thomas Kleine Buening and Aadirupa Saha
- Abstract要約: 本研究では,非定常デュエル帯域の問題について検討し,この問題に対する適応的動的後悔アルゴリズムを提案する。
ほぼ最適の $tildeO(sqrtStexttCW T)$ dynamic regret bound を示します。
- 参考スコア（独自算出の注目度）: 20.128001589147512
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study the problem of non-stationary dueling bandits and provide the first
adaptive dynamic regret algorithm for this problem. The only two existing
attempts in this line of work fall short across multiple dimensions, including
pessimistic measures of non-stationary complexity and non-adaptive parameter
tuning that requires knowledge of the number of preference changes. We develop
an elimination-based rescheduling algorithm to overcome these shortcomings and
show a near-optimal $\tilde{O}(\sqrt{S^{\texttt{CW}} T})$ dynamic regret bound,
where $S^{\texttt{CW}}$ is the number of times the Condorcet winner changes in
$T$ rounds. This yields the first near-optimal dynamic regret algorithm for
unknown $S^{\texttt{CW}}$. We further study other related notions of
non-stationarity for which we also prove near-optimal dynamic regret guarantees
under additional assumptions on the underlying preference model.
- Abstract（参考訳）: 本研究では,非定常なデュエルバンディットの問題を調べ,この問題に対する適応的動的後悔アルゴリズムを提供する。
この行の既存の2つの試みは、非定常的複雑性の悲観的な測度や、好みの変化の数に関する知識を必要とする非適応的パラメータチューニングを含む、複数の次元で不足する。
我々はこれらの欠点を克服し、ほぼ最適の$\tilde{O}(\sqrt{S^{\textt{CW}} T})$ dynamic regret bound, ここで、$S^{\textt{CW}}$は、コンドルセットの勝者が$T$ラウンドで変化した回数である。
これにより、未知の$S^{\textt{CW}}$に対する最初の近似的動的後悔アルゴリズムが得られる。
さらに,非定常性(non-stationarity)に関する他の関連する概念についても検討し,基礎となる選好モデルに対する追加の仮定の下で,準最適動的後悔の保証を証明した。
関連論文リスト
- An Equivalence Between Static and Dynamic Regret Minimization [10.812831455376218]
線形損失に対して、動的後悔最小化は、拡張決定空間における静的後悔最小化と等価であることを示す。
R_T(u_1,dots,u_T)le tildeという形式の動的後悔を保証するアルゴリズムを提供する。
論文 参考訳（メタデータ） (2024-06-03T17:54:58Z) - Variance-Dependent Regret Bounds for Non-stationary Linear Bandits [52.872628573907434]
報酬分布の分散と$B_K$の分散を利用するアルゴリズムを提案する。
Restarted Weighted$textOFUL+$とRestarted$textSAVE+$の2つの新しいアルゴリズムを紹介します。
特に、V_K$が$K$よりはるかに小さい場合、我々のアルゴリズムは、異なる設定下での非定常線形バンドレットの最先端結果よりも優れている。
論文 参考訳（メタデータ） (2024-03-15T23:36:55Z) - Adaptive Regret for Bandits Made Possible: Two Queries Suffice [26.769372199571002]
我々は、強い適応的後悔という厳密な概念の下で、クエリと後悔の最適包帯アルゴリズムを与える。
驚いたことに、1ラウンドあたり2つのクエリで$tildeO(sqrtn|I|)$ Adaptive Bandit Learner(StABL)を達成できる。
論文 参考訳（メタデータ） (2024-01-17T15:32:04Z) - A New Look at Dynamic Regret for Non-Stationary Stochastic Bandits [11.918230810566945]
本研究では,学習過程において各腕の報酬統計が数回変化しうる非定常的マルチアームバンディット問題について検討する。
我々は、$K$の武器付きバンディット問題において、ほぼ最適の$widetilde O(sqrtK N(S+1))$ dynamic regretを実現する方法を提案する。
論文 参考訳（メタデータ） (2022-01-17T17:23:56Z) - Adaptivity and Non-stationarity: Problem-dependent Dynamic Regret for Online Convex Optimization [70.4342220499858]
本稿では,スムーズさを生かし,問題依存量による動的後悔のT$への依存を補う新しいオンラインアルゴリズムを提案する。
この結果が本質的な難易度に適応しているのは, 既往の結果よりも厳密であり, 最悪の場合, 同一レートの保護が可能であるからである。
論文 参考訳（メタデータ） (2021-12-29T02:42:59Z) - Optimal and Efficient Dynamic Regret Algorithms for Non-Stationary
Dueling Bandits [27.279654173896372]
我々は,非定常的あるいは時間的に異なる選好の下で,$K$のDueling Banditsにおける空力的後悔の最小化問題について検討した。
これは、エージェントが各ラウンドで一対のアイテムを選択し、このペアに対する相対的な二項のウィンロスフィードバックのみを観察するオンライン学習設定である。
論文 参考訳（メタデータ） (2021-11-06T16:46:55Z) - Non-stationary Reinforcement Learning without Prior Knowledge: An
Optimal Black-box Approach [42.021871809877595]
近静止環境における最適な後悔を伴う強化学習アルゴリズムを、非定常環境における最適な動的後悔を伴う別のアルゴリズムに変換するブラックボックス還元を提案する。
提案手法は, 線形包帯, エピソードMDP, 無限水平MDPの技量を有意に改善することを示す。
論文 参考訳（メタデータ） (2021-02-10T12:43:31Z) - Lenient Regret for Multi-Armed Bandits [72.56064196252498]
エージェントが順番に行動を選択し、その行動に対する報酬を観察するマルチアーマッド・バンディット(MAB)問題を考察する。
アルゴリズムの大多数は、後悔、すなわち最高の行動の報酬とエージェントの行動の累積的な差を最小化しようとするが、この基準は望ましくない結果をもたらすかもしれない。
我々は、いくつかの$epsilon$よりも小さな最適性ギャップを無視した、より寛大で寛大で後悔すべき基準を提案する。
論文 参考訳（メタデータ） (2020-08-10T08:30:52Z) - Efficient Optimistic Exploration in Linear-Quadratic Regulators via
Lagrangian Relaxation [107.06364966905821]
線形2次レギュレータ(LQR)設定における探索・探索ジレンマについて検討した。
有限 MDP に対する楽観的アルゴリズムで用いられる拡張値反復アルゴリズムに着想を得て,Oulq の楽観的最適化を緩和することを提案する。
我々は、少なくとも$Obig(log (1/epsilon)big)$ Riccati方程式を解くことで、$epsilon$-OptimisticControllerを効率的に計算できることを示した。
論文 参考訳（メタデータ） (2020-07-13T16:30:47Z) - Dynamic Regret of Convex and Smooth Functions [93.71361250701075]
非定常環境におけるオンライン凸最適化について検討する。
パフォーマンス指標として動的後悔を選択します。
本研究では, 滑らかさを活かして, 動的後悔をさらに高めることが可能であることを示す。
論文 参考訳（メタデータ） (2020-07-07T14:10:57Z) - Stochastic Linear Bandits Robust to Adversarial Attacks [117.665995707568]
我々はロバスト位相除去アルゴリズムの2つの変種を提供し、その1つは$C$を知っており、もう1つはそうでない。
いずれの変種も、倒壊しない場合には、それぞれ$C = 0$ となり、それぞれ追加の加法項が生じる。
文脈的設定では、単純な欲求的アルゴリズムは、明示的な探索を行わず、C$を知らないにもかかわらず、ほぼ最適加法的後悔項で証明可能な堅牢性を示す。
論文 参考訳（メタデータ） (2020-07-07T09:00:57Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。