論文の概要: Constrained Linear Thompson Sampling

• arxiv url: http://arxiv.org/abs/2503.02043v2
• Date: Wed, 18 Jun 2025 01:05:35 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-06-19 16:34:05.324546
• Title: Constrained Linear Thompson Sampling
• Title（参考訳）: 拘束線形トンプソンサンプリング
• Authors: Aditya Gangrade, Venkatesh Saligrama,
• Abstract要約: Constrained Linear Thompson Sampling (COLTS)は、摂動線形プログラムを解くことでアクションを選択するサンプリングベースのフレームワークである。 S-COLTSはゼロリスクと$widetildeO(sqrtd3 T)を許容するが、R-COLTSは$widetildeO(sqrtd3 T)を許容する。
• 参考スコア（独自算出の注目度）: 39.724313550777715
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study safe linear bandits (SLBs), where an agent selects actions from a convex set to maximize an unknown linear objective subject to unknown linear constraints in each round. Existing methods for SLBs provide strong regret guarantees, but require solving expensive optimization problems (e.g., second-order cones, NP hard programs). To address this, we propose Constrained Linear Thompson Sampling (COLTS), a sampling-based framework that selects actions by solving perturbed linear programs, which significantly reduces computational costs while matching the regret and risk of prior methods. We develop two main variants: S-COLTS, which ensures zero risk and $\widetilde{O}(\sqrt{d^3 T})$ regret given a safe action, and R-COLTS, which achieves $\widetilde{O}(\sqrt{d^3 T})$ regret and risk with no instance information. In simulations, these methods match or outperform state of the art SLB approaches while substantially improving scalability. On the technical front, we introduce a novel coupled noise design that ensures frequent `local optimism' about the true optimum, and a scaling-based analysis to handle the per-round variability of constraints.
• Abstract（参考訳）: 本研究では,各ラウンドにおける未知の線形制約を対象とする未知の線形対象を最大化するために,エージェントが凸集合から動作を選択する安全線形帯域 (SLB) について検討する。 既存のSLBの手法は、強い後悔の保証を提供するが、高価な最適化問題(例えば、二階錐、NPハードプログラム)を解く必要がある。 そこで本研究では,従来の手法の後悔とリスクをマッチングしながら,計算コストを大幅に削減し,摂動線形プログラムを解くことで動作を選択するサンプリングベースフレームワークであるConstrained Linear Thompson Sampling (COLTS)を提案する。 S-COLTS はゼロリスクを保証し、$\widetilde{O}(\sqrt{d^3 T}) は安全なアクションを与えられた後悔であり、R-COLTS は$\widetilde{O}(\sqrt{d^3 T}) はインスタンス情報のない後悔とリスクである。 シミュレーションでは、これらの手法はスケーラビリティを大幅に向上させながら、最先端のSLBアプローチに適合または性能を向上する。 技術的には、真の最適性について頻繁に「局所的楽観主義」を保障する新しい結合雑音設計と、制約の丸ごとの変動性を扱うためのスケーリングに基づく分析を導入する。

関連論文リスト

• 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)

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

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