論文の概要: Non-stationary Bandit Convex Optimization: A Comprehensive Study

• arxiv url: http://arxiv.org/abs/2506.02980v1
• Date: Tue, 03 Jun 2025 15:18:41 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-06-04 21:47:35.81141
• Title: Non-stationary Bandit Convex Optimization: A Comprehensive Study
• Title（参考訳）: 非定常帯域凸最適化に関する総合的研究
• Authors: Xiaoqi Liu, Dorian Baudry, Julian Zimmert, Patrick Rebeschini, Arya Akhavan,
• Abstract要約: Bandit Convex Optimizationは、シーケンシャルな意思決定問題のクラスである。 非定常環境でこの問題を研究する。 非定常性の標準的な3つの基準の下で、後悔を最小限に抑えることを目指しています。
• 参考スコア（独自算出の注目度）: 28.086802754034828
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Bandit Convex Optimization is a fundamental class of sequential decision-making problems, where the learner selects actions from a continuous domain and observes a loss (but not its gradient) at only one point per round. We study this problem in non-stationary environments, and aim to minimize the regret under three standard measures of non-stationarity: the number of switches $S$ in the comparator sequence, the total variation $\Delta$ of the loss functions, and the path-length $P$ of the comparator sequence. We propose a polynomial-time algorithm, Tilted Exponentially Weighted Average with Sleeping Experts (TEWA-SE), which adapts the sleeping experts framework from online convex optimization to the bandit setting. For strongly convex losses, we prove that TEWA-SE is minimax-optimal with respect to known $S$ and $\Delta$ by establishing matching upper and lower bounds. By equipping TEWA-SE with the Bandit-over-Bandit framework, we extend our analysis to environments with unknown non-stationarity measures. For general convex losses, we introduce a second algorithm, clipped Exploration by Optimization (cExO), based on exponential weights over a discretized action space. While not polynomial-time computable, this method achieves minimax-optimal regret with respect to known $S$ and $\Delta$, and improves on the best existing bounds with respect to $P$.
• Abstract（参考訳）: Bandit Convex Optimizationはシーケンシャルな意思決定問題の基本的なクラスであり、学習者は連続したドメインからアクションを選択し、(勾配ではなく)損失を1ラウンド当たり1ポイントで観測する。 非定常環境でこの問題を研究し、非定常性の標準的な3つの尺度(コンパレータシーケンスにおけるスイッチ数$S$、損失関数の総変分$\Delta$、コンパレータシーケンスのパス長$P$)で後悔を最小限に抑えることを目的としている。 本稿では,オンライン凸最適化から帯域設定への睡眠専門家フレームワークの適用を目的とした多項式時間アルゴリズムTilted Exponentially Weighted Average with Sleeping Experts (TEWA-SE)を提案する。 強い凸損失に対しては、TEWA-SE が既知の$S$ と $\Delta$ に対して最小最適であることを証明する。 TEWA-SEにBandit-over-Banditフレームワークを組み込むことで、未知の非定常対策のある環境に解析を拡張する。 一般の凸損失に対して、離散化された作用空間上の指数重みに基づく2つ目のアルゴリズムであるExploration by Optimization (cExO)を導入する。 多項式時間計算可能ではないが、この手法は既知の$S$と$\Delta$に関して最小最大最適後悔を達成し、$P$に関して最良の既存の境界を改善する。

関連論文リスト

• Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic Shortest Path [80.60592344361073]
  線形混合遷移カーネルを用いた最短経路(SSP)問題について検討する。 エージェントは繰り返し環境と対話し、累積コストを最小化しながら特定の目標状態に到達する。 既存の作業は、イテレーションコスト関数の厳密な下限や、最適ポリシーに対する期待長の上限を仮定することが多い。
  論文  参考訳（メタデータ） (2024-02-14T07:52:00Z)
• Universal Online Learning with Gradient Variations: A Multi-layer Online Ensemble Approach [57.92727189589498]
  本稿では,2段階の適応性を持つオンライン凸最適化手法を提案する。 我々は$mathcalO(log V_T)$, $mathcalO(d log V_T)$, $hatmathcalO(sqrtV_T)$ regret bounds for strong convex, exp-concave and convex loss function。
  論文  参考訳（メタデータ） (2023-07-17T09:55:35Z)
• Non-stationary Online Convex Optimization with Arbitrary Delays [50.46856739179311]
  本稿では,非定常環境における遅延オンライン凸最適化(OCO)について検討する。 まず, 遅延勾配の勾配降下ステップを, 到着順に応じて行う単純なアルゴリズム, DOGDを提案する。 DOGDが達成した動的後悔境界を$O(sqrtbardT(P_T+1))$に削減する改良アルゴリズムを開発した。
  論文  参考訳（メタデータ） (2023-05-20T07:54:07Z)
• Best-of-Three-Worlds Linear Bandit Algorithm with Variance-Adaptive Regret Bounds [27.92755687977196]
  本稿では,2つの階層の環境に適応する線形帯域幅アルゴリズムを提案する。 高いレベルでは、提案アルゴリズムは様々な種類の環境に適応する。 提案アルゴリズムは、最適動作に対する累積損失のすべてに依存する、データ依存の後悔境界を有する。
  論文  参考訳（メタデータ） (2023-02-24T00:02:24Z)
• Adaptivity and Non-stationarity: Problem-dependent Dynamic Regret for Online Convex Optimization [70.4342220499858]
  本稿では,スムーズさを生かし,問題依存量による動的後悔のT$への依存を補う新しいオンラインアルゴリズムを提案する。 この結果が本質的な難易度に適応しているのは, 既往の結果よりも厳密であり, 最悪の場合, 同一レートの保護が可能であるからである。
  論文  参考訳（メタデータ） (2021-12-29T02:42:59Z)
• Optimal and Efficient Dynamic Regret Algorithms for Non-Stationary Dueling Bandits [27.279654173896372]
  我々は,非定常的あるいは時間的に異なる選好の下で,$K$のDueling Banditsにおける空力的後悔の最小化問題について検討した。 これは、エージェントが各ラウンドで一対のアイテムを選択し、このペアに対する相対的な二項のウィンロスフィードバックのみを観察するオンライン学習設定である。
  論文  参考訳（メタデータ） (2021-11-06T16:46:55Z)
• Dynamic Regret of Convex and Smooth Functions [93.71361250701075]
  非定常環境におけるオンライン凸最適化について検討する。 パフォーマンス指標として動的後悔を選択します。 本研究では, 滑らかさを活かして, 動的後悔をさらに高めることが可能であることを示す。
  論文  参考訳（メタデータ） (2020-07-07T14:10:57Z)

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

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