論文の概要: Perturbed-History Exploration in Stochastic Linear Bandits
- arxiv url: http://arxiv.org/abs/1903.09132v2
- Date: Mon, 10 Jul 2023 22:24:34 GMT
- ステータス: 処理完了
- システム内更新日: 2023-07-12 19:42:32.103432
- Title: Perturbed-History Exploration in Stochastic Linear Bandits
- Title(参考訳): 確率線形帯域における摂動履歴探査
- Authors: Branislav Kveton, Csaba Szepesvari, Mohammad Ghavamzadeh, and Craig
Boutilier
- Abstract要約: 線形帯域における累積後悔に対する新しいオンラインアルゴリズムを提案する。
このアルゴリズムは、その乱れた歴史に基づいて訓練された線形モデルにおいて、最も推定された報酬で腕を引っ張る。
- 参考スコア(独自算出の注目度): 35.70267786499955
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We propose a new online algorithm for cumulative regret minimization in a
stochastic linear bandit. The algorithm pulls the arm with the highest
estimated reward in a linear model trained on its perturbed history. Therefore,
we call it perturbed-history exploration in a linear bandit (LinPHE). The
perturbed history is a mixture of observed rewards and randomly generated
i.i.d. pseudo-rewards. We derive a $\tilde{O}(d \sqrt{n})$ gap-free bound on
the $n$-round regret of LinPHE, where $d$ is the number of features. The key
steps in our analysis are new concentration and anti-concentration bounds on
the weighted sum of Bernoulli random variables. To show the generality of our
design, we generalize LinPHE to a logistic model. We evaluate our algorithms
empirically and show that they are practical.
- Abstract(参考訳): 確率線形帯域における累積後悔最小化のための新しいオンラインアルゴリズムを提案する。
アルゴリズムは、摂動履歴に基づいて訓練された線形モデルにおいて、最も高い推定報酬でアームを引っ張る。
そのため,リニア・バンディット (linphe) における摂動・歴史探査と呼ぶ。
摂動歴史は観察された報酬とランダムに生成された擬似逆転の混合である。
我々は、LinPHE の $n$-round regret 上の $\tilde{O}(d \sqrt{n})$ gap-free bound を導出する。
我々の分析における重要なステップは、ベルヌーイ確率変数の重み付け和上の新しい濃度と反濃度境界である。
設計の一般性を示すため、LinPHEをロジスティックモデルに一般化する。
アルゴリズムを実証的に評価し,実用的であることを示す。
関連論文リスト
- Exploration via linearly perturbed loss minimisation [4.856378369489158]
本稿では,構造的バンディット問題に対する線形損失摂動(EVILL)による探索を紹介する。
一般化された線形包帯の場合、EVILLは乱れ歴史探索(PHE)に還元され、ランダムな乱れ報酬のトレーニングによって探索が行われる。
本稿では,従来のPHE方式では存在しないデータ依存摂動について提案する。
論文 参考訳(メタデータ) (2023-11-13T18:54:43Z) - Linear Bandits with Memory: from Rotting to Rising [5.5969337839476765]
推奨における飽和効果のような非定常現象は、主に有限個の腕を持つ包帯を用いてモデル化されている。
固定サイズウィンドウにおける学習者の過去の行動の影響を受けない,非定常線形バンディットモデルを提案する。
論文 参考訳(メタデータ) (2023-02-16T15:02:07Z) - Efficient Truncated Linear Regression with Unknown Noise Variance [26.870279729431328]
雑音のばらつきが不明な場合に, 線形回帰の計算的, 統計的に効率的な推定器を提案する。
提案手法は, トランキャット標本の負の類似度に対して, プロジェクテッド・グラディエント・ディフレッシュを効果的に実装することに基づく。
論文 参考訳(メタデータ) (2022-08-25T12:17:37Z) - Optimal Online Generalized Linear Regression with Stochastic Noise and
Its Application to Heteroscedastic Bandits [88.6139446295537]
一般化線形モデルの設定におけるオンライン一般化線形回帰の問題について検討する。
ラベルノイズに対処するため、古典的追従正規化リーダ(FTRL)アルゴリズムを鋭く解析する。
本稿では,FTRLに基づくアルゴリズムを提案する。
論文 参考訳(メタデータ) (2022-02-28T08:25:26Z) - Anti-Concentrated Confidence Bonuses for Scalable Exploration [57.91943847134011]
固有の報酬は、探検と探検のトレードオフを扱う上で中心的な役割を果たす。
楕円ボーナスを効率的に近似するためのエンファンティ集中型信頼境界を導入する。
我々は,Atariベンチマーク上での現代固有の報酬と競合する,深層強化学習のための実用的な変種を開発する。
論文 参考訳(メタデータ) (2021-10-21T15:25:15Z) - Randomized Exploration for Reinforcement Learning with General Value
Function Approximation [122.70803181751135]
本稿では,ランダム化最小二乗値反復(RLSVI)アルゴリズムに着想を得たモデルレス強化学習アルゴリズムを提案する。
提案アルゴリズムは,スカラーノイズを用いたトレーニングデータを簡易に摂動させることにより,探索を促進する。
我々はこの理論を、既知の困難な探査課題にまたがる実証的な評価で補完する。
論文 参考訳(メタデータ) (2021-06-15T02:23:07Z) - Online Markov Decision Processes with Aggregate Bandit Feedback [74.85532145498742]
本稿では,オンライン有限水平マルコフ決定過程の新たな変種について検討する。
各エピソードにおいて、学習者は、エピソードの選択した方針によって実現された軌道に沿って蓄積された損失を被り、総括的盗聴フィードバックを観察する。
我々の主な結果は計算効率のよいアルゴリズムで、$O(sqrtK)$ regret for this set, where $K$ is the number of episodes。
論文 参考訳(メタデータ) (2021-01-31T16:49:07Z) - 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) - Randomized Exploration in Generalized Linear Bandits [56.05007606177762]
一般化線形帯域に対する2つのランダム化アルゴリズムについて検討する。
最初のGLM-TSLは、ラプラス近似から後方分布への一般化線形モデル(GLM)をサンプリングする。
第2のGLM-FPLは、過去の報酬のランダムな摂動履歴にGLMを適合させる。
論文 参考訳(メタデータ) (2019-06-21T04:57:54Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。