論文の概要: On Limited-Memory Subsampling Strategies for Bandits

• arxiv url: http://arxiv.org/abs/2106.10935v1
• Date: Mon, 21 Jun 2021 09:11:22 GMT
• ステータス: 処理完了
• システム内更新日: 2021-06-22 15:55:06.799153
• Title: On Limited-Memory Subsampling Strategies for Bandits
• Title（参考訳）: バンディットのリミテッドメモリサブサンプリング戦略について
• Authors: Dorian Baudry (Inria, CRIStAL, CNRS), Yoan Russac (DI-ENS, CNRS, VALDA), Olivier Capp\'e (DI-ENS, CNRS, VALDA)
• Abstract要約: 本稿では,Budry et al. (2020) の最近の研究で提案されている単純な決定論的部分サンプリング則が,一次元指数関数族において最適であることを示す。 また、これらの保証は、アルゴリズムメモリを時間軸の多対数関数に制限する場合にも有効であることを示す。 本稿では,近年の観測結果のみをサブサンプリングに用い,既知の急激な変化を前提とした最適後悔保証を実現するアルゴリズムの変種を提案する。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: There has been a recent surge of interest in nonparametric bandit algorithms based on subsampling. One drawback however of these approaches is the additional complexity required by random subsampling and the storage of the full history of rewards. Our first contribution is to show that a simple deterministic subsampling rule, proposed in the recent work of Baudry et al. (2020) under the name of ''last-block subsampling'', is asymptotically optimal in one-parameter exponential families. In addition, we prove that these guarantees also hold when limiting the algorithm memory to a polylogarithmic function of the time horizon. These findings open up new perspectives, in particular for non-stationary scenarios in which the arm distributions evolve over time. We propose a variant of the algorithm in which only the most recent observations are used for subsampling, achieving optimal regret guarantees under the assumption of a known number of abrupt changes. Extensive numerical simulations highlight the merits of this approach, particularly when the changes are not only affecting the means of the rewards.
• Abstract（参考訳）: 近年,サブサンプリングに基づく非パラメトリックバンディットアルゴリズムへの関心が高まっている。 しかし、これらのアプローチの欠点は、ランダムなサブサンプリングによる追加の複雑さと、報酬の全履歴の保存である。 最初の貢献は、baudryらの最近の研究で提案された、単純な決定論的サブサンプリングルールを示すことです。 (2020) は 'last-block subsampling' という名前で、一パラメータ指数関数族において漸近的に最適である。 さらに,これらの保証は,アルゴリズムメモリを時間軸の多対数関数に制限する場合にも有効であることを示す。 これらの発見は、特にアーム分布が時間とともに進化する非定常シナリオにおいて、新しい視点を開く。 本稿では,近年の観測結果のみをサブサンプリングに用い,既知の急激な変化を前提とした最適後悔保証を実現するアルゴリズムの変種を提案する。 大規模な数値シミュレーションは、特に変化が報酬の手段に影響を与えているだけでなく、このアプローチの利点を強調している。

関連論文リスト

• Near-Optimal Algorithm for Non-Stationary Kernelized Bandits [6.379833644595456]
  時変ベイズ最適化(英語版)とも呼ばれる非定常カーネル化バンドイット問題(KB)について検討する。 我々は,2乗指数およびマタン核を持つ非定常KBに対して,アルゴリズムに依存しない最初のリフレッシュローバウンドを示す。 本稿では,ランダムな置換による位相除去を再開する手法を提案する。
  論文  参考訳（メタデータ） (2024-10-21T14:28:26Z)
• 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)
• Multi-Armed Bandits with Abstention [62.749500564313834]
  本稿では, 新たな戦略要素である禁忌を取り入れた, 正準多重武装バンディット問題の拡張を提案する。 この強化されたフレームワークでは、エージェントは各タイムステップでアームを選択することだけでなく、観察する前に即時報酬を受け付けないオプションも備えている。
  論文  参考訳（メタデータ） (2024-02-23T06:27:12Z)
• Non-Stationary Bandits under Recharging Payoffs: Improved Planning with Sublinear Regret [34.44347218903429]
  マルチアームバンディット設定は、最近非定常状態において研究されている。 各アクションの平均的なペイオフは、前回のプレイ以来のラウンド数の増加しない機能である。 我々は,我々のアルゴリズムがサブ線形後悔を伴う帯域幅アルゴリズムにどのように変換されるかを示す。
  論文  参考訳（メタデータ） (2022-05-29T23:55:36Z)
• Damped Online Newton Step for Portfolio Selection [96.0297968061824]
  古典的なオンラインポートフォリオ選択の問題を再考し、各ラウンドで学習者がポートフォリオの集合上の分布を選択し、その富を割り当てる。 この問題に対する対数的後悔を達成する既存のアルゴリズムは、ラウンドの総数とスケールする時間と空間の複雑さがある。 対数的後悔を伴う最初の実用的オンラインポートフォリオ選択アルゴリズムを提示し、その時間と空間の複雑さは水平線上で対数的にのみ依存する。
  論文  参考訳（メタデータ） (2022-02-15T17:01:55Z)
• A PDE-Based Analysis of the Symmetric Two-Armed Bernoulli Bandit [1.2183405753834562]
  この研究は、両腕のベルヌーイ・バンディット問題(英語版)(Bernoulli bandit problem)の、腕の手段の和が1であるバージョンに対処する。 我々は, それぞれの問題を線形熱方程式の解に関連付けることにより, minmax最適後悔と擬似回帰の先行順序項を得る。
  論文  参考訳（メタデータ） (2022-02-11T17:03:18Z)
• Filtered Poisson Process Bandit on a Continuum [1.4180331276028662]
  動作が非均一なポアソン過程のフィルタリング実現を誘導する連続武装バンドイットのバージョンを考える。 本稿では,行動空間のデータ適応的離散化を利用した高信頼境界アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-07-20T09:39:17Z)
• Approximation Schemes for ReLU Regression [80.33702497406632]
  我々はReLU回帰の根本的な問題を考察する。 目的は、未知の分布から引き出された2乗損失に対して、最も適したReLUを出力することである。
  論文  参考訳（メタデータ） (2020-05-26T16:26:17Z)
• Efficient improper learning for online logistic regression [68.8204255655161]
  サンプル数 n の対数的後悔を持つ任意の正則アルゴリズムは、必然的に B の指数乗法定数を損なうことが知られている。 本研究では、対数的後悔を保ちながら、この指数定数を回避する効率的な不適切なアルゴリズムを設計する。 シュロゲート損失を伴う正規化経験的リスク最小化に基づく新しいアルゴリズムは、O(B log(Bn))として、オーダーO(d2)の1回あたりの時間複雑度で、後悔のスケーリングを満足させる。
  論文  参考訳（メタデータ） (2020-03-18T09:16:14Z)
• A General Theory of the Stochastic Linear Bandit and Its Applications [8.071506311915398]
  本稿では,線形バンディット問題に対する一般解析フレームワークとアルゴリズム群を紹介する。 予測における最適化という新たな概念は、OFULの過剰探索問題を減少させるSieeved greedy(SG)と呼ばれる新しいアルゴリズムを生み出します。 SGが理論的に最適であることを示すことに加えて、実験シミュレーションにより、SGはgreedy、OFUL、TSといった既存のベンチマークよりも優れていることが示された。
  論文  参考訳（メタデータ） (2020-02-12T18:54:41Z)
• Frequentist Regret Bounds for Randomized Least-Squares Value Iteration [94.47472987987805]
  有限水平強化学習(RL)における探索・探索ジレンマの検討 本稿では,ランダム化最小二乗値 (RLSVI) の楽観的な変種を紹介する。 マルコフ決定過程が低ランク遷移ダイナミクスを持つという仮定の下で、RSVIの頻繁な後悔は、$widetilde O(d2 H2 sqrtT)$$ d $ が特徴次元であり、$ H $ が地平線であり、$ T $ が総数であることを示す。
  論文  参考訳（メタデータ） (2019-11-01T19:48:57Z)

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

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