論文の概要: Revisiting Weighted Strategy for Non-stationary Parametric Bandits
- arxiv url: http://arxiv.org/abs/2303.02691v2
- Date: Wed, 7 Jun 2023 06:44:28 GMT
- ステータス: 処理完了
- システム内更新日: 2023-06-08 19:05:36.152956
- Title: Revisiting Weighted Strategy for Non-stationary Parametric Bandits
- Title（参考訳）: 非定常パラメトリックバンドに対する重み付け戦略の再検討
- Authors: Jing Wang, Peng Zhao, Zhi-Hua Zhou
- Abstract要約: 本稿では,非定常パラメトリックバンディットの重み付け戦略を再考する。
より単純な重みに基づくアルゴリズムを生成する改良された分析フレームワークを提案する。
我々の新しいフレームワークは、他のパラメトリックバンディットの後悔の限界を改善するのに使える。
- 参考スコア（独自算出の注目度）: 82.1942459195896
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Non-stationary parametric bandits have attracted much attention recently.
There are three principled ways to deal with non-stationarity, including
sliding-window, weighted, and restart strategies. As many non-stationary
environments exhibit gradual drifting patterns, the weighted strategy is
commonly adopted in real-world applications. However, previous theoretical
studies show that its analysis is more involved and the algorithms are either
computationally less efficient or statistically suboptimal. This paper revisits
the weighted strategy for non-stationary parametric bandits. In linear bandits
(LB), we discover that this undesirable feature is due to an inadequate regret
analysis, which results in an overly complex algorithm design. We propose a
refined analysis framework, which simplifies the derivation and importantly
produces a simpler weight-based algorithm that is as efficient as
window/restart-based algorithms while retaining the same regret as previous
studies. Furthermore, our new framework can be used to improve regret bounds of
other parametric bandits, including Generalized Linear Bandits (GLB) and
Self-Concordant Bandits (SCB). For example, we develop a simple weighted GLB
algorithm with an $\widetilde{O}(k_\mu^{\frac{5}{4}} c_\mu^{-\frac{3}{4}}
d^{\frac{3}{4}} P_T^{\frac{1}{4}}T^{\frac{3}{4}})$ regret, improving the
$\widetilde{O}(k_\mu^{2} c_\mu^{-1}d^{\frac{9}{10}}
P_T^{\frac{1}{5}}T^{\frac{4}{5}})$ bound in prior work, where $k_\mu$ and
$c_\mu$ characterize the reward model's nonlinearity, $P_T$ measures the
non-stationarity, $d$ and $T$ denote the dimension and time horizon.
- Abstract（参考訳）: 非定常パラメトリックバンドが近年注目を集めている。
非定常性を扱うには、スライディングウインドウ、重み付け、再起動戦略の3つの原則がある。
多くの非定常環境は段階的なドリフトパターンを示すため、重み付け戦略は現実の応用に一般的に採用されている。
しかし、以前の理論的研究により、解析はより複雑で、アルゴリズムは計算効率が低く、統計的に最適であることが示された。
本稿では,非定常パラメトリックバンドの重み付け戦略を再考する。
リニアバンディット(LB)では、この望ましくない特徴は不適切な後悔の分析によるものであることが判明し、結果としてアルゴリズムが複雑すぎる。
本稿では,従来の研究と同様の後悔を保ちつつ,ウィンドウ/リスタート型アルゴリズムと同等に効率よく,より単純な重みに基づくアルゴリズムを創出する改良型解析フレームワークを提案する。
さらに,本手法は一般化線形バンドイット (glb) や自己一致バンドイット (scb) など,他のパラメトリックバンドイットの後悔境界の改善にも利用できる。
例えば、$\widetilde{o}(k_\mu^{\frac{5}{4}} c_\mu^{-\frac{3}{4}} d^{\frac{3}{4}} p_t^{\frac{1}{4}}t^{\frac{3}{4}})$ という単純な重み付きglbアルゴリズムを開発し、$\widetilde{o}(k_\mu^{2} c_\mu^{-1}d^{\frac{9}{10}} p_t^{\frac{1}{5}}t^{\frac{4}{5}})$ を以前の作業で限定し、$k_\mu$ と $c_\mu$ が報酬モデルの非線形性を特徴づける。
関連論文リスト
- 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) - Efficient Frameworks for Generalized Low-Rank Matrix Bandit Problems [61.85150061213987]
一般化線形モデル (GLM) フレームワークを用いて, citelu2021low で提案した一般化低ランク行列帯域問題について検討する。
既存のアルゴリズムの計算不可能性と理論的制約を克服するため,まずG-ESTTフレームワークを提案する。
G-ESTT は $tildeO(sqrt(d_1+d_2)3/2Mr3/2T)$ bound of regret を達成でき、G-ESTS は $tildeO を達成できることを示す。
論文 参考訳（メタデータ） (2024-01-14T14:14:19Z) - Computationally Efficient Horizon-Free Reinforcement Learning for Linear
Mixture MDPs [111.75736569611159]
線形混合MDPのための計算効率のよい初めての地平線フリーアルゴリズムを提案する。
我々のアルゴリズムは、未知の遷移力学に対する重み付き最小二乗推定器に適応する。
これにより、$sigma_k2$'sが知られているときに、この設定で最もよく知られたアルゴリズムも改善される。
論文 参考訳（メタデータ） (2022-05-23T17:59:18Z) - Optimal and Efficient Dynamic Regret Algorithms for Non-Stationary
Dueling Bandits [27.279654173896372]
我々は,非定常的あるいは時間的に異なる選好の下で,$K$のDueling Banditsにおける空力的後悔の最小化問題について検討した。
これは、エージェントが各ラウンドで一対のアイテムを選択し、このペアに対する相対的な二項のウィンロスフィードバックのみを観察するオンライン学習設定である。
論文 参考訳（メタデータ） (2021-11-06T16:46:55Z) - Non-stationary Linear Bandits Revisited [26.082923174615495]
非定常線形帯域は、時間変化の根底にある回帰パラメータを持つ線形帯域の変種である。
これらのアルゴリズムに対して,$widetildeO(T3/4(1+P_T)1/4)$ dynamic regretを証明した。
論文 参考訳（メタデータ） (2021-03-09T10:07:17Z) - Correcting Momentum with Second-order Information [50.992629498861724]
最適積に$O(epsilon)$epsilon点を求める非臨界最適化のための新しいアルゴリズムを開発した。
我々は、さまざまな大規模ディープラーニングベンチマークとアーキテクチャで結果を検証する。
論文 参考訳（メタデータ） (2021-03-04T19:01:20Z) - Non-stationary Reinforcement Learning without Prior Knowledge: An
Optimal Black-box Approach [42.021871809877595]
近静止環境における最適な後悔を伴う強化学習アルゴリズムを、非定常環境における最適な動的後悔を伴う別のアルゴリズムに変換するブラックボックス還元を提案する。
提案手法は, 線形包帯, エピソードMDP, 無限水平MDPの技量を有意に改善することを示す。
論文 参考訳（メタデータ） (2021-02-10T12:43:31Z) - Efficient Learning in Non-Stationary Linear Markov Decision Processes [17.296084954104415]
非定常線形(低ランク)マルコフ決定過程(MDP)におけるエピソード強化学習の研究
OPT-WLSVI は最小二乗の重み付け値に基づく楽観的なモデルフリーのアルゴリズムであり、指数重み付けを用いて過去のデータをスムーズに忘れる。
我々のアルゴリズムは、各時点で最高のポリシーと競合するときに、$d$$$widetildemathcalO(d5/4H2 Delta1/4 K3/4)$で上限付けられた後悔を実現する。
論文 参考訳（メタデータ） (2020-10-24T11:02:45Z) - Stochastic Bandits with Linear Constraints [69.757694218456]
制約付き文脈線形帯域設定について検討し、エージェントの目標は一連のポリシーを作成することである。
楽観的悲観的線形帯域(OPLB)と呼ばれる,この問題に対する高信頼束縛アルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-06-17T22:32:19Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。