論文の概要: A New Look at Dynamic Regret for Non-Stationary Stochastic Bandits
- arxiv url: http://arxiv.org/abs/2201.06532v1
- Date: Mon, 17 Jan 2022 17:23:56 GMT
- ステータス: 処理完了
- システム内更新日: 2022-01-19 14:00:15.735915
- Title: A New Look at Dynamic Regret for Non-Stationary Stochastic Bandits
- Title（参考訳）: 非定常確率バンディットに対する動的後悔の新しい見方
- Authors: Yasin Abbasi-Yadkori, Andras Gyorgy, Nevena Lazic
- Abstract要約: 本研究では,学習過程において各腕の報酬統計が数回変化しうる非定常的マルチアームバンディット問題について検討する。
我々は、$K$の武器付きバンディット問題において、ほぼ最適の$widetilde O(sqrtK N(S+1))$ dynamic regretを実現する方法を提案する。
- 参考スコア（独自算出の注目度）: 11.918230810566945
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study the non-stationary stochastic multi-armed bandit problem, where the
reward statistics of each arm may change several times during the course of
learning. The performance of a learning algorithm is evaluated in terms of
their dynamic regret, which is defined as the difference of the expected
cumulative reward of an agent choosing the optimal arm in every round and the
cumulative reward of the learning algorithm. One way to measure the hardness of
such environments is to consider how many times the identity of the optimal arm
can change. We propose a method that achieves, in $K$-armed bandit problems, a
near-optimal $\widetilde O(\sqrt{K N(S+1)})$ dynamic regret, where $N$ is the
number of rounds and $S$ is the number of times the identity of the optimal arm
changes, without prior knowledge of $S$ and $N$. Previous works for this
problem obtain regret bounds that scale with the number of changes (or the
amount of change) in the reward functions, which can be much larger, or assume
prior knowledge of $S$ to achieve similar bounds.
- Abstract（参考訳）: 本研究では,学習過程において各腕の報酬統計が数回変化しうる非定常確率的マルチアームバンディット問題について検討する。
学習アルゴリズムの性能は、各ラウンドにおいて最適なアームを選択するエージェントの期待累積報酬と学習アルゴリズムの累積報酬との差として定義される動的後悔の観点から評価される。
このような環境の硬さを測る一つの方法は、最適な腕の同一性を何回変えられるかを考えることである。
我々は、$k$-armed bandit問題において、ほぼ最適に近い$\widetilde o(\sqrt{k n(s+1)})$ dynamic regretを実現する方法を提案する。
この問題の以前の研究は、報酬関数における変化の数(または変化の量)と共にスケールする後悔の限界を得るが、これはより大きい可能性があるし、あるいは同様の境界を達成するために$S$の事前の知識を仮定する。
関連論文リスト
- Sparsity-Agnostic Linear Bandits with Adaptive Adversaries [19.84322270472381]
本研究では,各ラウンドにおいて,学習者が要素を選択して報酬を得る一連の行動(特徴ベクトル)を受信する線形帯域について検討する。
期待される報酬は、選択されたアクションの固定だが未知の線形関数である。
線形報酬関数の非ゼロ係数数$S$に依存するスパース後悔境界について検討する。
論文 参考訳（メタデータ） (2024-06-03T10: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) - Combinatorial Stochastic-Greedy Bandit [79.1700188160944]
我々は,選択した$n$のアームセットのジョイント報酬以外の余分な情報が観測されない場合に,マルチアームのバンディット問題に対する新規グリーディ・バンディット(SGB)アルゴリズムを提案する。
SGBは最適化された拡張型コミットアプローチを採用しており、ベースアームの大きなセットを持つシナリオ用に特別に設計されている。
論文 参考訳（メタデータ） (2023-12-13T11:08:25Z) - Variance-Aware Regret Bounds for Stochastic Contextual Dueling Bandits [53.281230333364505]
本稿では, 一般化線形モデル(GLM)から, デュエルアームのバイナリ比較を生成するコンテキストデュエルバンド問題について検討する。
本稿では,SupLinUCB型アルゴリズムを提案する。このアルゴリズムは,計算効率と分散を意識したリセットバウンド$tilde Obig(dsqrtsum_t=1Tsigma_t2 + dbig)$を提案する。
我々の後悔は、比較が決定論的である場合の直感的な期待と自然に一致し、アルゴリズムは$tilde O(d)$ regretにのみ悩まされる。
論文 参考訳（メタデータ） (2023-10-02T08:15:52Z) - 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) - Top $K$ Ranking for Multi-Armed Bandit with Noisy Evaluations [102.32996053572144]
我々は,各ラウンドの開始時に,学習者が各アームの真の報酬について,ノイズのない独立した評価を受けるマルチアームバンディット・セッティングを考える。
評価の方法によって異なるアルゴリズムアプローチと理論的保証を導出する。
論文 参考訳（メタデータ） (2021-12-13T09:48:54Z) - 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) - Stochastic Linear Bandits Robust to Adversarial Attacks [117.665995707568]
我々はロバスト位相除去アルゴリズムの2つの変種を提供し、その1つは$C$を知っており、もう1つはそうでない。
いずれの変種も、倒壊しない場合には、それぞれ$C = 0$ となり、それぞれ追加の加法項が生じる。
文脈的設定では、単純な欲求的アルゴリズムは、明示的な探索を行わず、C$を知らないにもかかわらず、ほぼ最適加法的後悔項で証明可能な堅牢性を示す。
論文 参考訳（メタデータ） (2020-07-07T09:00:57Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。