論文の概要: Constrained Linear Thompson Sampling

• arxiv url: http://arxiv.org/abs/2503.02043v1
• Date: Mon, 03 Mar 2025 20:44:58 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-03-05 19:16:28.777554
• Title: Constrained Linear Thompson Sampling
• Title（参考訳）: 拘束線形トンプソンサンプリング
• Authors: Aditya Gangrade, Venkatesh Saligrama,
• Abstract要約: 本研究では, エージェントが凸領域からのアクションを逐次選択し, 未知の目的を最大化する安全線形バンドイット問題について検討する。 既存のアプローチは、頻繁な信頼境界を持つ楽観主義に基づく手法に依存しており、しばしば計算的に高価な行動選択ルーチンに繋がる。 我々は,後悔の最小化と制約満足度を効率的にバランスするサンプリングベースのフレームワークであるCOLTS(Constrained Linear Thompson Sampling)を提案する。
• 参考スコア（独自算出の注目度）: 39.724313550777715
• License:
• Abstract: We study the safe linear bandit problem, where an agent sequentially selects actions from a convex domain to maximize an unknown objective while ensuring unknown linear constraints are satisfied on a per-round basis. Existing approaches primarily rely on optimism-based methods with frequentist confidence bounds, often leading to computationally expensive action selection routines. We propose COnstrained Linear Thompson Sampling (COLTS), a sampling-based framework that efficiently balances regret minimization and constraint satisfaction by selecting actions on the basis of noisy perturbations of the estimates of the unknown objective vector and constraint matrix. We introduce three variants of COLTS, distinguished by the learner's available side information: - S-COLTS assumes access to a known safe action and ensures strict constraint enforcement by combining the COLTS approach with a rescaling towards the safe action. For $d$-dimensional actions, this yields $\tilde{O}(\sqrt{d^3 T})$ regret and zero constraint violations (or risk). - E-COLTS enforces constraints softly under Slater's condition, and attains regret and risk of $\tilde{O}(\sqrt{d^3 T})$ by combining COLTS with uniform exploration. - R-COLTS requires no side information, and ensures instance-independent regret and risk of $\tilde{O}(\sqrt{d^3 T})$ by leveraging repeated resampling. A key technical innovation is a coupled noise design, which maintains optimism while preserving computational efficiency, which is combined with a scaling based analysis technique to address the variation of the per-round feasible region induced by sampled constraint matrices. Our methods match the regret bounds of prior approaches, while significantly reducing computational costs compared to them, thus yielding a scalable and practical approach for constrained bandit linear optimization.
• Abstract（参考訳）: 安全線形帯域問題では, エージェントが連続して凸領域から動作を選択し, 未知の目的を最大化し, 未知の線形制約が全ラウンドで満たされることを保証する。 既存のアプローチは主に、頻繁な信頼境界を持つ楽観主義に基づく手法に依存しており、しばしば計算的に高価な行動選択ルーチンに繋がる。 未知の目的ベクトルと制約行列の推定値のノイズ摂動に基づいて行動を選択することにより、後悔の最小化と制約満足度を効率的にバランスさせるサンプリングベースフレームワークであるCOLTSを提案する。 S-COLTSは、既知の安全なアクションへのアクセスを前提とし、COLTSアプローチと安全なアクションへの再スケーリングを組み合わせることで厳格な制約執行を保証する。 $d$-dimensional アクションの場合、これは $\tilde{O}(\sqrt{d^3 T})$ regret と 0 の制約違反(またはリスク)をもたらす。 - E-COLTSはスレーターの条件下で制約を緩やかに強制し、COLTSと一様探索を組み合わせることで、$\tilde{O}(\sqrt{d^3 T})$の後悔とリスクを得る。 - R-COLTS はサイド情報を必要としないため、繰り返し再サンプリングを活用することで、インスタンスに依存しない後悔と $\tilde{O}(\sqrt{d^3 T})$ のリスクを保証する。 重要な技術的革新は結合ノイズ設計であり、これは計算効率を保ちながら楽観性を保ち、スケーリングに基づく分析技術と組み合わせて、サンプリングされた制約行列によって誘導される全領域の変動に対処するものである。 提案手法は,従来の手法と比較して計算コストを大幅に削減し,制約付き帯域線形最適化のためのスケーラブルで実用的な手法を実現する。

関連論文リスト

• Learning to Explore with Lagrangians for Bandits under Unknown Linear Constraints [8.784438985280094]
  線形制約が未知の多腕バンディットにおける純粋探索として問題を研究する。 まず、制約下での純粋な探索のために、サンプルの複雑さを低く抑えたラグランジアン緩和を提案する。 第二に、ラグランジアンの下界と凸の性質を利用して、トラック・アンド・ストップとガミファイド・エクスプローラー(LATSとLAGEX)の2つの計算効率の良い拡張を提案する。
  論文  参考訳（メタデータ） (2024-10-24T15:26:14Z)
• Online Constraint Tightening in Stochastic Model Predictive Control: A Regression Approach [49.056933332667114]
  確率制約付き最適制御問題に対する解析解は存在しない。 制御中の制約強調パラメータをオンラインで学習するためのデータ駆動型アプローチを提案する。 提案手法は, 確率制約を厳密に満たす制約強調パラメータを導出する。
  論文  参考訳（メタデータ） (2023-10-04T16:22:02Z)
• Safe Linear Bandits over Unknown Polytopes [39.177982674455784]
  安全線形バンディット問題(英: safe linear bandit problem、SLB)は、線形プログラミングのオンライン手法である。 ポリトープ上でのSLBの有効性とスムーズな安全性のトレードオフについて検討した。
  論文  参考訳（メタデータ） (2022-09-27T21:13:32Z)
• Log Barriers for Safe Black-box Optimization with Application to Safe Reinforcement Learning [72.97229770329214]
  本稿では,学習時の安全性維持が不可欠である高次元非線形最適化問題に対する一般的なアプローチを提案する。 LBSGDと呼ばれるアプローチは、慎重に選択されたステップサイズで対数障壁近似を適用することに基づいている。 安全強化学習における政策課題の違反を最小限に抑えるためのアプローチの有効性を実証する。
  論文  参考訳（メタデータ） (2022-07-21T11:14:47Z)
• Interactively Learning Preference Constraints in Linear Bandits [100.78514640066565]
  我々は、既知の報酬と未知の制約で逐次意思決定を研究する。 応用として,運転シミュレーションにおいて,人間の嗜好を表現するための学習制約を検討する。
  論文  参考訳（メタデータ） (2022-06-10T17:52:58Z)
• Penalized Proximal Policy Optimization for Safe Reinforcement Learning [68.86485583981866]
  本稿では、等価な制約のない問題の単一最小化により、煩雑な制約付きポリシー反復を解決するP3Oを提案する。 P3Oは、コスト制約を排除し、クリップされたサロゲート目的による信頼領域制約を除去するために、単純なyet効果のペナルティ関数を利用する。 P3Oは,一連の制約された機関車作業において,報酬改善と制約満足度の両方に関して,最先端のアルゴリズムより優れていることを示す。
  論文  参考訳（メタデータ） (2022-05-24T06:15:51Z)
• Safe Online Bid Optimization with Return-On-Investment and Budget Constraints subject to Uncertainty [87.81197574939355]
  最適化問題と学習問題の両方について検討する。 我々は、潜在的に線形な数の制約違反を犠牲にして、サブ線形後悔を保証するアルゴリズム、すなわちGCBを提供する。 より興味深いことに、我々はGCB_safe(psi,phi)というアルゴリズムを提供し、サブ線形擬似回帰と安全性w.h.p.の両方を、耐性 psi と phi を受け入れるコストで保証する。
  論文  参考訳（メタデータ） (2022-01-18T17:24:20Z)
• Concave Utility Reinforcement Learning with Zero-Constraint Violations [43.29210413964558]
  本稿では,凸制約を伴うCURL(Concave utility reinforcement Learning)の問題点について考察する。 制約違反をゼロにするモデルベース学習アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-09-12T06:13:33Z)

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

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