論文の概要: Linear Bandits under Exact Sliding-Window Constraints

• arxiv url: http://arxiv.org/abs/2610.08745v1
• Date: Tue, 06 Oct 2026 17:41:08 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-08 02:58:30.154323
• Title: Linear Bandits under Exact Sliding-Window Constraints
• Title（参考訳）: 厳密なスライディング・ウィンドウ制約下における線形帯域
• Abstract要約: 凸性と巡回シフト不変性は、$wmid T$と加法$O(w)$ギャップがなければ、定常解が最適であることを示す。 我々は,オフライン最適軌道に対して,$widetildeO(dsqrtT+d+w)$の稀なOFULアルゴリズムを開発した。 実世界および総合的なベンチマークに対する我々のアプローチを評価し、報酬を達成しつつ正確な実現可能性を維持しつつ、ポリシー更新を著しく少なくしたベースラインに匹敵する後悔を示す。
• 参考スコア（独自算出の注目度）: 16.541844988375914
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study linear bandits under exact sliding-window constraints, where every consecutive block of actions must belong to a prescribed feasible set. In the offline setting, where the reward function is known, we show that convexity and cyclic-shift invariance make a stationary solution optimal when $w\mid T$ and within an additive $O(w)$ gap otherwise. In the online setting, we show that geometric structure alone is insufficient for learning, and sublinear regret can be impossible. We introduce a transition diameter $τ$ that quantifies feasible reachability and develop a rare-switching OFUL algorithm with regret $\widetilde{O}(d\sqrt{T}+τd+w)$ against the offline-optimal feasible trajectory. Finally, we remove cyclic invariance and consider general sliding-window constraints, where optimal behavior may be non-stationary. We represent recent action history as the state of a finite-memory control problem and introduce a history-state diameter $D$ that measures feasible communication between viable histories. Combining optimistic remaining-horizon planning with rare policy updates, we obtain a regret bound of $\widetilde{O}(d\sqrt{T}+dD+w)$. We evaluate our approach on real-world and synthetic benchmarks, showing that it maintains exact feasibility while achieving reward and regret comparable to baselines with substantially fewer policy updates.
• Abstract（参考訳）: 我々は, 連続する動作ブロックが所定の実行可能集合に属するような, 正確なスライディングウインドウ制約の下で線形帯域について検討する。 報酬関数が知られているオフライン設定において、凸性と巡回シフト不変性は、$w\mid T$ および加法的$O(w)$ギャップ内での定常解を最適にすることを示す。 オンライン環境では、幾何学構造だけでは学習には不十分であり、サブ線形後悔は不可能であることを示す。 実現可能な到達性を定量化する遷移直径$τ$を導入し、オフライン最適軌道に対して、後悔$\widetilde{O}(d\sqrt{T}+τd+w)$で希少なOFULアルゴリズムを開発する。 最後に、循環的不変性を取り除き、最適挙動が非定常であるような一般的なすべり窓の制約を考える。 我々は、最近の行動履歴を有限メモリ制御問題の状態として表現し、実行可能な履歴間の通信を計測する履歴状態の直径$D$を導入している。 楽観的な残留水平計画と稀なポリシー更新を組み合わせることで、$\widetilde{O}(d\sqrt{T}+dD+w)$の後悔境界が得られる。 実世界および総合的なベンチマークに対する我々のアプローチを評価し、報酬を達成しつつ正確な実現可能性を維持しつつ、ポリシー更新を著しく少なくしたベースラインに匹敵する後悔を示す。

関連論文リスト

• Block Optimism for Nonstationary Bandits with Latent Linear Dynamics [33.79708176601716]
  潜在線形力学を用いた内因性非定常バンドイット問題について検討する。 適応的ブロックレベルの最適化により、このレートを改善できることが示される。 我々は、以前の$tildeO(T2/3)$保証よりも大幅に改善された$tildeO(sqrt T)$の遺言境界を証明した。
  論文  参考訳（メタデータ） (2026-10-01T01:43:18Z)
• Constrained Online Learning with Noisy Constraint Values [55.29259818039367]
  一般的な実現可能性の下では、我々のLEDGERアルゴリズムは、期待される損失$O(sqrt T)と期待される予算違反$O(sqrtTlog(eT))を達成します。 スレーター条件、フィードバックチャネル間の独立性、絶対的制約値境界は不要である。
  論文  参考訳（メタデータ） (2026-09-07T01:38:41Z)
• Finite and Corruption-Robust Regret Bounds in Online Inverse Linear Optimization under M-Convex Action Sets [27.973926244529267]
  本研究では,コンテキストレコメンデーションとして知られる逆逆線形最適化について検討する。 学習者は、M-集合上の最適解のキャラクタリゼーションとボリューム引数を組み合わせることで、これを後悔する。
  論文  参考訳（メタデータ） (2026-02-02T05:48:54Z)
• Order-Optimal Instance-Dependent Bounds for Offline Reinforcement Learning with Preference Feedback [56.6950165117658]
  我々は、暗黙の報酬が未知パラメータの線形関数である、好みフィードバックによるオフライン強化学習について検討する。 そこで我々は,UnderlineLocally Underline Underline Weights あるいは sc RL-LOW を用いたアルゴリズムを提案する。 我々は,sc RL-LOWの次数次最適性を示すため,単純な後悔マッチングの指数において,下限と上限が順序的に一致することが観察された。
  論文  参考訳（メタデータ） (2024-06-18T02:03:12Z)
• Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic Shortest Path [80.60592344361073]
  線形混合遷移カーネルを用いた最短経路(SSP)問題について検討する。 エージェントは繰り返し環境と対話し、累積コストを最小化しながら特定の目標状態に到達する。 既存の作業は、イテレーションコスト関数の厳密な下限や、最適ポリシーに対する期待長の上限を仮定することが多い。
  論文  参考訳（メタデータ） (2024-02-14T07:52:00Z)
• On the Interplay Between Misspecification and Sub-optimality Gap in Linear Contextual Bandits [76.2262680277608]
  本研究では,線形関数クラスによって期待される報酬関数を近似できるような,不特定条件下での線形文脈帯域について検討する。 このアルゴリズムは, 対数的因子に比例した設定において, ギャップ依存の残差が$tilde O (d2/Delta)$と同じであることを示す。
  論文  参考訳（メタデータ） (2023-03-16T15:24:29Z)
• Online Convex Optimization with Stochastic Constraints: Zero Constraint Violation and Bandit Feedback [0.0]
  本稿では,O(sqrtT)$期待後悔とゼロ制約違反を保証できるドリフト・プラス・ペナルティアルゴリズムの変種を提案する。 我々のアルゴリズムは、バニラドリフト・プラス・ペナルティ法とは対照的に、時間地平線の長さが$T$である。
  論文  参考訳（メタデータ） (2023-01-26T18:04:26Z)
• 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)
• Nearly Dimension-Independent Sparse Linear Bandit over Small Action Spaces via Best Subset Selection [71.9765117768556]
  本研究では,高次元線形モデルの下での文脈的帯域問題について考察する。 この設定は、パーソナライズされたレコメンデーション、オンライン広告、パーソナライズされた医療など、不可欠な応用を見出す。 本稿では,最適部分集合選択法を用いて2重成長エポックを推定する手法を提案する。
  論文  参考訳（メタデータ） (2020-09-04T04:10:39Z)
• Provably Efficient Safe Exploration via Primal-Dual Policy Optimization [105.7510838453122]
  制約付きマルコフ決定過程(CMDP)を用いた安全強化学習(SRL)問題について検討する。 本稿では,関数近似設定において,安全な探索を行うCMDPの効率の良いオンラインポリシー最適化アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-03-01T17:47:03Z)

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

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