論文の概要: Optimal and Efficient Dynamic Regret Algorithms for Non-Stationary
Dueling Bandits
- arxiv url: http://arxiv.org/abs/2111.03917v1
- Date: Sat, 6 Nov 2021 16:46:55 GMT
- ステータス: 処理完了
- システム内更新日: 2021-11-10 10:56:43.678060
- Title: Optimal and Efficient Dynamic Regret Algorithms for Non-Stationary
Dueling Bandits
- Title（参考訳）: 非定常デューリングバンディットに対する最適かつ効率的な動的後悔アルゴリズム
- Authors: Shubham Gupta, Aadirupa Saha
- Abstract要約: 我々は,非定常的あるいは時間的に異なる選好の下で,$K$のDueling Banditsにおける空力的後悔の最小化問題について検討した。
これは、エージェントが各ラウンドで一対のアイテムを選択し、このペアに対する相対的な二項のウィンロスフィードバックのみを観察するオンライン学習設定である。
- 参考スコア（独自算出の注目度）: 27.279654173896372
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We study the problem of \emph{dynamic regret minimization} in $K$-armed
Dueling Bandits under non-stationary or time varying preferences. This is an
online learning setup where the agent chooses a pair of items at each round and
observes only a relative binary `win-loss' feedback for this pair, sampled from
an underlying preference matrix at that round. We first study the problem of
static-regret minimization for adversarial preference sequences and design an
efficient algorithm with $O(\sqrt{KT})$ high probability regret. We next use
similar algorithmic ideas to propose an efficient and provably optimal
algorithm for dynamic-regret minimization under two notions of
non-stationarities. In particular, we establish $\tO(\sqrt{SKT})$ and
$\tO({V_T^{1/3}K^{1/3}T^{2/3}})$ dynamic-regret guarantees, $S$ being the total
number of `effective-switches' in the underlying preference relations and $V_T$
being a measure of `continuous-variation' non-stationarity. The complexity of
these problems have not been studied prior to this work despite the
practicability of non-stationary environments in real world systems. We justify
the optimality of our algorithms by proving matching lower bound guarantees
under both the above-mentioned notions of non-stationarities. Finally, we
corroborate our results with extensive simulations and compare the efficacy of
our algorithms over state-of-the-art baselines.
- Abstract（参考訳）: 非定常または時間変化の選好の下で、$K$武装デュエルバンドにおける 'emph{dynamic regret minimization} の問題を研究する。
これは、エージェントが各ラウンドの2つのアイテムを選択し、そのラウンドの下位の選好行列からサンプリングされた、このペアの相対的なバイナリ‘win-loss’フィードバックのみを観察するオンライン学習セットアップである。
まず,逆選好系列に対する静的レグレット最小化の問題を調べ,$o(\sqrt{kt})$高確率後悔を伴う効率的なアルゴリズムを設計する。
次に、非定常性という2つの概念の下で、動的回帰最小化のための効率的かつ証明可能なアルゴリズムを提案する。
特に、$\tO(\sqrt{SKT})$および$\tO({V_T^{1/3}K^{1/3}T^{2/3}})$ dynamic-regret guarantees, $S$は下層の嗜好関係における「有効スイッチ」の総数、$V_T$は「連続変量」非定常性の尺度である。
これらの問題の複雑さは、現実のシステムにおける非定常環境の実践性にもかかわらず、この研究以前には研究されていない。
このアルゴリズムの最適性は、上記の非定常の概念の両方の下で、下限保証の一致を証明することによって正当化される。
最後に,広範なシミュレーションを行い,最先端のベースラインに対するアルゴリズムの有効性を比較検討した。
関連論文リスト
- Perturb-and-Project: Differentially Private Similarities and Marginals [73.98880839337873]
差分プライバシーのための入力摂動フレームワークを再検討し、入力にノイズを付加する。
まず、ペアワイズ・コサイン類似性をプライベートにリリースするための新しい効率的なアルゴリズムを設計する。
我々は,$k$の辺縁クエリを$n$の機能に対して計算する新しいアルゴリズムを導出する。
論文 参考訳（メタデータ） (2024-06-07T12:07:16Z) - Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic
Shortest Path [80.60592344361073]
線形混合遷移カーネルを用いた最短経路(SSP)問題について検討する。
エージェントは繰り返し環境と対話し、累積コストを最小化しながら特定の目標状態に到達する。
既存の作業は、イテレーションコスト関数の厳密な下限や、最適ポリシーに対する期待長の上限を仮定することが多い。
論文 参考訳（メタデータ） (2024-02-14T07:52:00Z) - Combinatorial Stochastic-Greedy Bandit [79.1700188160944]
我々は,選択した$n$のアームセットのジョイント報酬以外の余分な情報が観測されない場合に,マルチアームのバンディット問題に対する新規グリーディ・バンディット(SGB)アルゴリズムを提案する。
SGBは最適化された拡張型コミットアプローチを採用しており、ベースアームの大きなセットを持つシナリオ用に特別に設計されている。
論文 参考訳（メタデータ） (2023-12-13T11:08:25Z) - Strictly Low Rank Constraint Optimization -- An Asymptotically
$\mathcal{O}(\frac{1}{t^2})$ Method [5.770309971945476]
最適解における空間性を促進するために,テキスト規則化を用いた非テキスト・非滑らかな問題のクラスを提案する。
我々のアルゴリズムは、滑らかな凸問題に対する一階法に対するネステロフの最適収束と全く同じ$Ofrac(t2)$の特異収束を達成することができることを示す。
論文 参考訳（メタデータ） (2023-07-04T16:55:41Z) - Revisiting Weighted Strategy for Non-stationary Parametric Bandits [82.1942459195896]
本稿では,非定常パラメトリックバンディットの重み付け戦略を再考する。
より単純な重みに基づくアルゴリズムを生成する改良された分析フレームワークを提案する。
我々の新しいフレームワークは、他のパラメトリックバンディットの後悔の限界を改善するのに使える。
論文 参考訳（メタデータ） (2023-03-05T15:11:14Z) - Best-of-Three-Worlds Linear Bandit Algorithm with Variance-Adaptive
Regret Bounds [27.92755687977196]
本稿では,2つの階層の環境に適応する線形帯域幅アルゴリズムを提案する。
高いレベルでは、提案アルゴリズムは様々な種類の環境に適応する。
提案アルゴリズムは、最適動作に対する累積損失のすべてに依存する、データ依存の後悔境界を有する。
論文 参考訳（メタデータ） (2023-02-24T00:02:24Z) - ANACONDA: An Improved Dynamic Regret Algorithm for Adaptive
Non-Stationary Dueling Bandits [20.128001589147512]
本研究では,非定常デュエル帯域の問題について検討し,この問題に対する適応的動的後悔アルゴリズムを提案する。
ほぼ最適の $tildeO(sqrtStexttCW T)$ dynamic regret bound を示します。
論文 参考訳（メタデータ） (2022-10-25T20:26:02Z) - Minimax Optimization with Smooth Algorithmic Adversaries [59.47122537182611]
対戦相手が展開するスムーズなアルゴリズムに対して,Min-playerの新しいアルゴリズムを提案する。
本アルゴリズムは,制限周期のない単調進行を保証し,適切な勾配上昇数を求める。
論文 参考訳（メタデータ） (2021-06-02T22:03:36Z) - Non-stationary Reinforcement Learning without Prior Knowledge: An
Optimal Black-box Approach [42.021871809877595]
近静止環境における最適な後悔を伴う強化学習アルゴリズムを、非定常環境における最適な動的後悔を伴う別のアルゴリズムに変換するブラックボックス還元を提案する。
提案手法は, 線形包帯, エピソードMDP, 無限水平MDPの技量を有意に改善することを示す。
論文 参考訳（メタデータ） (2021-02-10T12:43:31Z) - Ranking a set of objects: a graph based least-square approach [70.7866286425868]
同一労働者の群集によるノイズの多いペアワイズ比較から始まる$N$オブジェクトのランク付けの問題について考察する。
品質評価のために,最小二乗内在的最適化基準に依存する非適応的ランキングアルゴリズムのクラスを提案する。
論文 参考訳（メタデータ） (2020-02-26T16:19:09Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。