論文の概要: Exploiting Problem Geometry in Safe Linear Bandits
- arxiv url: http://arxiv.org/abs/2308.15006v1
- Date: Tue, 29 Aug 2023 03:54:53 GMT
- ステータス: 処理完了
- システム内更新日: 2023-08-30 15:47:17.107988
- Title: Exploiting Problem Geometry in Safe Linear Bandits
- Title(参考訳): 安全線形バンディットにおける問題幾何の活用
- Authors: Spencer Hutchinson, Berkay Turan, Mahnoosh Alizadeh
- Abstract要約: 安全線形バンドイット問題は、学習者の動作が全てのラウンドにおいて不確実な線形制約を満たす必要がある古典線形バンドイット問題のバージョンである。
特定の問題設定の幾何を活用すれば、よく分離された問題インスタンスとアクションセットの両方に対して、改善された後悔の保証が達成できることがわかった。
- 参考スコア(独自算出の注目度): 4.84955052297084
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The safe linear bandit problem is a version of the classic linear bandit
problem where the learner's actions must satisfy an uncertain linear constraint
at all rounds. Due its applicability to many real-world settings, this problem
has received considerable attention in recent years. We find that by exploiting
the geometry of the specific problem setting, we can achieve improved regret
guarantees for both well-separated problem instances and action sets that are
finite star convex sets. Additionally, we propose a novel algorithm for this
setting that chooses problem parameters adaptively and enjoys at least as good
regret guarantees as existing algorithms. Lastly, we introduce a generalization
of the safe linear bandit setting where the constraints are convex and adapt
our algorithms and analyses to this setting by leveraging a novel
convex-analysis based approach. Simulation results show improved performance
over existing algorithms for a variety of randomly sampled settings.
- Abstract(参考訳): 安全線形バンドイット問題は、学習者の動作が全てのラウンドにおいて不確実な線形制約を満たす必要がある古典線形バンドイット問題のバージョンである。
多くの実世界の環境に適用できるため、近年ではこの問題が注目されている。
特定の問題設定の幾何を利用することにより、よく分離された問題インスタンスと有限個の星凸集合であるアクションセットの両方に対する改善された後悔保証を達成することができる。
さらに,この問題パラメータを適応的に選択し,既成アルゴリズムと同等に良好な後悔の保証を享受できる新しいアルゴリズムを提案する。
最後に,制約が凸である安全な線形バンディット設定の一般化を導入し,新しい凸解析に基づくアプローチを用いて,アルゴリズムと解析をこの設定に適用する。
シミュレーションの結果、様々なランダムなサンプル設定のための既存のアルゴリズムよりも性能が向上した。
関連論文リスト
- Likelihood Ratio Confidence Sets for Sequential Decision Making [51.66638486226482]
確率に基づく推論の原理を再検討し、確率比を用いて妥当な信頼シーケンスを構築することを提案する。
本手法は, 精度の高い問題に特に適している。
提案手法は,オンライン凸最適化への接続に光を当てることにより,推定器の最適シーケンスを確実に選択する方法を示す。
論文 参考訳(メタデータ) (2023-11-08T00:10:21Z) - Convex Methods for Constrained Linear Bandits [2.5782420501870296]
この研究は、安全な帯域幅アルゴリズム、特に安全な線形帯域幅の計算的側面に関する包括的な研究を示す。
まず,安全線形バンディット問題に対する最適ポリシーの特性を特徴付けるとともに,安全線形バンディットアルゴリズムのエンドツーエンドパイプラインを提案する。
論文 参考訳(メタデータ) (2023-11-07T20:45:46Z) - The Impact of the Geometric Properties of the Constraint Set in Safe
Optimization with Bandit Feedback [5.758073912084366]
我々は,エージェントが逐次行動を選択し,環境からの反応を観察する,帯域幅フィードバックによる安全な最適化問題を考える。
この問題に対するアルゴリズムを提案し,制約セットの幾何学的性質がアルゴリズムの後悔にどのように影響するかを検討する。
論文 参考訳(メタデータ) (2023-05-01T15:48:34Z) - 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) - Optimal Rates for Random Order Online Optimization [60.011653053877126]
敵が損失関数を選択できるカテットガルバー2020onlineについて検討するが、一様にランダムな順序で提示される。
2020onlineアルゴリズムが最適境界を達成し,安定性を著しく向上することを示す。
論文 参考訳(メタデータ) (2021-06-29T09:48:46Z) - On the Optimality of Batch Policy Optimization Algorithms [106.89498352537682]
バッチポリシー最適化は、環境と対話する前に既存のデータをポリシー構築に活用することを検討する。
信頼調整インデックスアルゴリズムは楽観的,悲観的,中立的いずれであってもミニマックス最適であることを示す。
最適値予測の本来の難易度を考慮した新しい重み付き最小値基準を提案する。
論文 参考訳(メタデータ) (2021-04-06T05:23:20Z) - Experimental Design for Regret Minimization in Linear Bandits [19.8309784360219]
オンライン・リニア・バンドレットにおける後悔を最小限に抑える設計に基づく新しいアルゴリズムを提案する。
我々は、現在最先端の有限時間後悔保証を提供し、このアルゴリズムが帯域幅と半帯域幅の両方のフィードバックシステムに適用可能であることを示す。
論文 参考訳(メタデータ) (2020-11-01T17:59:19Z) - An Asymptotically Optimal Primal-Dual Incremental Algorithm for
Contextual Linear Bandits [129.1029690825929]
複数の次元に沿った最先端技術を改善する新しいアルゴリズムを提案する。
非文脈線形帯域の特別な場合において、学習地平線に対して最小限の最適性を確立する。
論文 参考訳(メタデータ) (2020-10-23T09:12:47Z) - On Lower Bounds for Standard and Robust Gaussian Process Bandit
Optimization [55.937424268654645]
有界ノルムを持つ関数のブラックボックス最適化問題に対するアルゴリズム非依存な下界を考える。
本稿では, 単純さ, 汎用性, エラー確率への依存性の向上など, 後悔の下位境界を導出するための新しい証明手法を提案する。
論文 参考訳(メタデータ) (2020-08-20T03:48:14Z) - Bandit algorithms to emulate human decision making using probabilistic
distortions [20.422725678982726]
報奨分布に歪んだ確率を持つ2つの多重武装バンディット問題を定式化する。
以上のような後悔の最小化の問題と、マルチアームバンディットのための最高の腕識別フレームワークについて考察する。
論文 参考訳(メタデータ) (2016-11-30T17:37:51Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。