論文の概要: Bellman-Centric Learning: Near-Optimal Regret for Linear Bandits with Memory

• arxiv url: http://arxiv.org/abs/2610.05659v1
• Date: Mon, 05 Oct 2026 01:09:01 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-10 12:12:51.541045
• Title: Bellman-Centric Learning: Near-Optimal Regret for Linear Bandits with Memory
• Title（参考訳）: Bellman-Centric Learning: メモリ付き線形帯域に対する準最適レグレット
• Abstract要約: 本研究では,過去の動作が任意の行列値を持つメモリマップを通じて内因性非定常性を誘導するメモリを用いた線形帯域について検討する。 RSM-LinUCB はベルマン中心のアルゴリズムであり,線形帯域で学習し,強化学習で計画を立てる。
• 参考スコア（独自算出の注目度）: 9.049760884454429
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study linear bandits with memory, where past actions induce endogenous nonstationarity through an arbitrary known, bounded matrix-valued memory map. To trade off exploration and exploitation while accounting for the memory dynamics, we develop RSM-LinUCB, a Bellman-centric algorithm that learns as in linear bandits and plans as in reinforcement learning. This design admits a novel regret decomposition which separates the memory-induced error from the cumulative reward estimation error along the learner's trajectory. We prove a high-probability regret bound of $\widetilde O\big(dRS(M+1)+σd\sqrt T\big)$, where $T$ is the learning horizon, $d$ is the parameter dimension, $M$ is the memory length, $R$ and $S$ bound the memory-map operator norm and reward-parameter norm, respectively, and $σ$ is the sub-Gaussian noise scale. Our results reveal that the multiplicative memory-horizon coupling in prior bounds is not intrinsic: memory only contributes an additive cost, up to logarithmic factors. We also prove a matching minimax lower bound, establishing near-optimality. We further extend the algorithm to generalized linear rewards, preserving this separation with near-optimal memory and leading statistical dependence. Our algorithms outperform the baselines in numerical experiments on synthetic instances and semi-synthetic KV- and semantic-cache tasks.
• Abstract（参考訳）: 本研究では,過去の動作が任意の行列値を持つメモリマップを通じて内因性非定常性を誘導するメモリ付き線形帯域について検討する。 メモリダイナミクスを考慮に入れた探索と利用のトレードオフとして,線形帯域幅や強化学習の計画などを学ぶベルマン中心のアルゴリズム RSM-LinUCB を開発した。 この設計は、記憶による誤りを学習者の軌道に沿った累積報酬推定誤差から分離する新たな後悔の分解を許容する。 例えば、$T$ は学習地平線、$d$ はパラメータ次元、$M$ はメモリ長、$R$ はメモリマップ演算子ノルム、$S$ はメモリマップ演算子ノルム、$σ$ はサブガウス雑音スケールである。 以上の結果から, メモリは対数的要因まで, 加算コストにのみ寄与する, 先行境界における乗法的メモリ-水平結合は本質的ではないことが判明した。 また、一致したミニマックス下限を証明し、ほぼ最適性を確立する。 我々はさらに、このアルゴリズムを一般化された線形報酬に拡張し、この分離をほぼ最適メモリで保存し、統計的依存を導く。 本アルゴリズムは, 合成事例と半合成KV, セマンティックキャッシュタスクの数値実験において, ベースラインよりも優れていた。

関連論文リスト

• Generalized Linear Bandits with Memory [30.756127188585907]
  メモリを用いた一般化線形バンドレットについて検討し, メモリ行列による報酬の過去の行動に依存する内因性非定常的設定について検討した。 既知の $tildeO(T3/4)$ regret bound はゆるい解析から生じるものであり、線形の場合の $tildeO(sqrtT)$ regret rate を回復するシャープな解析を提供する。
  論文  参考訳（メタデータ） (2026-08-16T16:39:09Z)
• Nonstationary Generalized Linear Bandits with Discounted Online Mirror Descent [39.805192541498634]
  本研究では,非定常線形計算(GLBs)について検討し,期待される報酬を未知の時間変化パラメータを持つ非線形リンク関数を用いてモデル化する。 本稿では,パラメータ推定に割引オンラインミラー降下(DOMD)を利用する非定常GLBに対する新しいアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2026-05-25T08:40:32Z)
• Revisiting Weighted Strategy for Non-stationary Parametric Bandits and MDPs [56.246783503873225]
  本稿では,非定常パラメトリックバンディットの重み付け戦略を再考する。 本稿では,ウィンドウ/リスタートベースアルゴリズムと同様に,より単純な重みに基づくアルゴリズムを提案する。 我々のフレームワークは、他のパラメトリックバンディットの後悔の限界を改善するのに使える。
  論文  参考訳（メタデータ） (2026-01-03T04:50:21Z)
• Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic Shortest Path [80.60592344361073]
  線形混合遷移カーネルを用いた最短経路(SSP)問題について検討する。 エージェントは繰り返し環境と対話し、累積コストを最小化しながら特定の目標状態に到達する。 既存の作業は、イテレーションコスト関数の厳密な下限や、最適ポリシーに対する期待長の上限を仮定することが多い。
  論文  参考訳（メタデータ） (2024-02-14T07:52:00Z)
• Topology-aware Embedding Memory for Continual Learning on Expanding Networks [63.35819388164267]
  本稿では,メモリリプレイ技術を用いて,メモリ爆発問題に対処する枠組みを提案する。 Topology-aware Embedding Memory (TEM) を用いたPDGNNは最先端技術よりも優れている。
  論文  参考訳（メタデータ） (2024-01-24T03:03:17Z)
• Sketchy: Memory-efficient Adaptive Regularization with Frequent Directions [22.09320263962004]
  ディープラーニング(DL)学習タスクにおけるKronecker-factored gradient covariance matrixのスペクトルは、小さなリード固有空間に集中している。 本稿では,行列プレコンディショナを維持するためのメモリと計算要求を低減させる汎用的手法について述べる。 ShampooやAdamと競合する手法で、第2の瞬間を追跡するにはサブ線形メモリしか必要ありません。
  論文  参考訳（メタデータ） (2023-02-07T21:50:06Z)
• Nearly Optimal Regret for Learning Adversarial MDPs with Linear Function Approximation [92.3161051419884]
  我々は、敵対的な報酬と完全な情報フィードバックで有限正方体エピソディックマルコフ決定プロセスのための強化学習を研究します。 我々は、$tildeO(dHsqrtT)$ regretを達成できることを示し、$H$はエピソードの長さである。 また、対数因子までの$tildeOmega(dHsqrtT)$の値が一致することを証明する。
  論文  参考訳（メタデータ） (2021-02-17T18:54:08Z)
• Provably Efficient Reinforcement Learning for Discounted MDPs with Feature Mapping [99.59319332864129]
  本稿では,割引決定(MDP)のための強化学習について検討する。 本稿では,特徴写像を利用した新しいアルゴリズムを提案し,$tilde O(dsqrtT/ (1-gamma)2)$ regretを求める。 以上の結果から,提案した強化学習アルゴリズムは,最大1-γ-0.5$の係数でほぼ最適であることが示唆された。
  論文  参考訳（メタデータ） (2020-06-23T17:08:54Z)
• Learning Near Optimal Policies with Low Inherent Bellman Error [115.16037976819331]
  エピソード強化学習における近似線形作用値関数を用いた探索問題について検討する。 我々は,検討した設定に対して最適な統計率を達成するアルゴリズムを用いて,Emphbatch仮定のみを用いて探索を行うことが可能であることを示す。
  論文  参考訳（メタデータ） (2020-02-29T02:02:40Z)

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

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