論文の概要: Linear Bandits with Memory: from Rotting to Rising

• arxiv url: http://arxiv.org/abs/2302.08345v2
• Date: Thu, 25 May 2023 07:53:34 GMT
• ステータス: 処理完了
• システム内更新日: 2023-05-26 20:57:46.330549
• Title: Linear Bandits with Memory: from Rotting to Rising
• Title（参考訳）: 記憶のある線形バンド:回転から上昇まで
• Authors: Giulia Clerici, Pierre Laforgue, Nicol\`o Cesa-Bianchi
• Abstract要約: 推奨における飽和効果のような非定常現象は、主に有限個の腕を持つ包帯を用いてモデル化されている。 固定サイズウィンドウにおける学習者の過去の行動の影響を受けない,非定常線形バンディットモデルを提案する。
• 参考スコア（独自算出の注目度）: 5.5969337839476765
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Nonstationary phenomena, such as satiation effects in recommendations, have mostly been modeled using bandits with finitely many arms. However, the richer action space provided by linear bandits is often preferred in practice. In this work, we introduce a novel nonstationary linear bandit model, where current rewards are influenced by the learner's past actions in a fixed-size window. Our model, which recovers stationary linear bandits as a special case, leverages two parameters: the window size $m \ge 0$, and an exponent $\gamma$ that captures the rotting ($\gamma < 0)$ or rising ($\gamma > 0$) nature of the phenomenon. When both $m$ and $\gamma$ are known, we propose and analyze a variant of OFUL which minimizes regret against cycling policies. By choosing the cycle length so as to trade-off approximation and estimation errors, we then prove a bound of order $\sqrt{d}\,(m+1)^{\frac{1}{2}+\max\{\gamma,0\}}\,T^{3/4}$ (ignoring log factors) on the regret against the optimal sequence of actions, where $T$ is the horizon and $d$ is the dimension of the linear action space. Through a bandit model selection approach, our results are extended to the case where $m$ and $\gamma$ are unknown. Finally, we complement our theoretical results with experiments against natural baselines.
• Abstract（参考訳）: 推奨の風刺効果のような非定常現象は、主に有限個の腕を持つバンディットを用いてモデル化されている。 しかし、線形バンディットによって提供されるよりリッチなアクション空間は、実際は好まれる。 本研究では,固定サイズウィンドウにおける学習者の過去の行動の影響を受けない,新しい非定常線形バンディットモデルを提案する。 定常線形帯域を特別な場合として回復するモデルでは、ウィンドウサイズ$m \ge 0$ と、その現象の回転($\gamma < 0)$ または上昇($\gamma > 0$)の性質を捉える指数 $\gamma$ という2つのパラメータを利用する。 m$と$\gamma$の両方が知られているとき、サイクルポリシーに対する後悔を最小限に抑えるOFULの変種を提案し、分析する。 近似と推定誤差をトレードオフするためにサイクル長を選択することで、最適のアクション列に対する後悔に対して、次数 $\sqrt{d}\,(m+1)^{\frac{1}{2}+\max\{\gamma,0\}}\,T^{3/4}$(ログ要素を無視して)の有界を証明し、そこで$T$は地平線であり、$d$は線形アクション空間の次元である。 banditモデル選択アプローチによって、結果は$m$と$\gamma$が不明な場合に拡張されます。 最後に, 自然ベースラインに対する実験により, 理論結果を補完する。

関連論文リスト

• Linear bandits with polylogarithmic minimax regret [8.97780713904412]
  本研究では,未知ベクトルに近づいた単位球上での動作を選択すると,サブガウス雑音パラメータが線形に消滅する線形帯域の雑音モデルについて検討する。 我々は,この問題に対するアルゴリズムを導入し,この最小限の後悔のスケーリングを,時間軸で$log3(T)$,時間軸で$T$として示す。
  論文  参考訳（メタデータ） (2024-02-19T10:56:47Z)
• Borda Regret Minimization for Generalized Linear Dueling Bandits [65.09919504862496]
  本稿では,ボルダスコアが最も高い項目を識別することを目的とした,デュエルバンディットに対するボルダ後悔最小化問題について検討する。 本稿では,多くの既存モデルをカバーする一般化線形デュエルバンドモデルのリッチクラスを提案する。 我々のアルゴリズムは$tildeO(d2/3 T2/3)$ regretを達成し、これも最適である。
  論文  参考訳（メタデータ） (2023-03-15T17:59:27Z)
• Causal Bandits for Linear Structural Equation Models [58.2875460517691]
  本稿では,因果図形モデルにおける最適な介入順序を設計する問題について検討する。 グラフの構造は知られており、ノードは$N$である。 頻繁性(UCBベース)とベイズ的設定に2つのアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2022-08-26T16:21:31Z)
• Exploration in Linear Bandits with Rich Action Sets and its Implications for Inference [23.364534479492715]
  期待行列の最小固有値は、アルゴリズムの累積後悔が$sqrtn)$であるときに、$Omega(sqrtn)として増加することを示す。 本研究は, 線形帯域におけるEmphmodel selectionとEmphclusteringの2つの実践シナリオに適用する。
  論文  参考訳（メタデータ） (2022-07-23T20:25:07Z)
• Variance-Aware Sparse Linear Bandits [64.70681598741417]
  余分な線形包帯に対する最悪のミニマックスは$widetildeThetaleft(sqrtdTright)$である。 ノイズがなく、アクションセットが単位球面である良性設定では、ディビジョン・アンド・コンカーを使用して、$widetildemathcal O(1)$ regretを達成することができる。 我々は,任意の分散対応線形帯域幅アルゴリズムを分散対応線形帯域幅アルゴリズムに変換する汎用フレームワークを開発した。
  論文  参考訳（メタデータ） (2022-05-26T15:55:44Z)
• Adversarial Combinatorial Bandits with General Non-linear Reward Functions [29.775097827244853]
  既知の非線形報酬関数を用いて対向性バンディットを研究し、対向性線形バンディットに関する既存の研究を延長する。 我々は、$N$の腕と$K$の腕のサブセットが$T$の期間のそれぞれで選択されている場合、ミニマックスの最適な後悔は$widetildeTheta_d(Nd T)$報酬関数が$dK$の$d$度であり、$ta_K(sqrtK T)$報酬関数が低度ではない場合です。
  論文  参考訳（メタデータ） (2021-01-05T00:56:27Z)
• Impact of Representation Learning in Linear Bandits [83.17684841392754]
  本研究では,表現学習が帯域幅問題の効率性を向上させる方法について検討する。 我々は,$widetildeO(TsqrtkN + sqrtdkNT)$ regretを達成する新しいアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-10-13T16:35:30Z)
• Nearly Dimension-Independent Sparse Linear Bandit over Small Action Spaces via Best Subset Selection [71.9765117768556]
  本研究では,高次元線形モデルの下での文脈的帯域問題について考察する。 この設定は、パーソナライズされたレコメンデーション、オンライン広告、パーソナライズされた医療など、不可欠な応用を見出す。 本稿では,最適部分集合選択法を用いて2重成長エポックを推定する手法を提案する。
  論文  参考訳（メタデータ） (2020-09-04T04:10:39Z)
• Stochastic Bandits with Linear Constraints [69.757694218456]
  制約付き文脈線形帯域設定について検討し、エージェントの目標は一連のポリシーを作成することである。 楽観的悲観的線形帯域(OPLB)と呼ばれる,この問題に対する高信頼束縛アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-06-17T22:32:19Z)
• Nearly Optimal Regret for Stochastic Linear Bandits with Heavy-Tailed Payoffs [35.988644745703645]
  我々は、リニアバンディットをヘビーテールのペイオフで分析し、そこではペイオフは1+epsilon$のモーメントしか持たない。 本稿では,$widetildeO(dfrac12Tfrac11+epsilon)$のサブ線形後悔境界を満足する2つの新しいアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-04-28T13:01:38Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。