論文の概要: Learning to Explore with Lagrangians for Bandits under Unknown Linear Constraints

• arxiv url: http://arxiv.org/abs/2410.18844v1
• Date: Thu, 24 Oct 2024 15:26:14 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-10-25 12:52:01.710004
• Title: Learning to Explore with Lagrangians for Bandits under Unknown Linear Constraints
• Title（参考訳）: 未知の線形制約下におけるラグランジアンによる帯域探索の学習
• Authors: Udvas Das, Debabrota Basu,
• Abstract要約: 線形制約が未知の多腕バンディットにおける純粋探索として問題を研究する。 まず、制約下での純粋な探索のために、サンプルの複雑さを低く抑えたラグランジアン緩和を提案する。 第二に、ラグランジアンの下界と凸の性質を利用して、トラック・アンド・ストップとガミファイド・エクスプローラー(LATSとLAGEX)の2つの計算効率の良い拡張を提案する。
• 参考スコア（独自算出の注目度）: 8.784438985280094
• License:
• Abstract: Pure exploration in bandits models multiple real-world problems, such as tuning hyper-parameters or conducting user studies, where different safety, resource, and fairness constraints on the decision space naturally appear. We study these problems as pure exploration in multi-armed bandits with unknown linear constraints, where the aim is to identify an $r$$\textit{-good feasible policy}$. First, we propose a Lagrangian relaxation of the sample complexity lower bound for pure exploration under constraints. We show how this lower bound evolves with the sequential estimation of constraints. Second, we leverage the Lagrangian lower bound and the properties of convex optimisation to propose two computationally efficient extensions of Track-and-Stop and Gamified Explorer, namely LATS and LAGEX. To this end, we propose a constraint-adaptive stopping rule, and while tracking the lower bound, use pessimistic estimate of the feasible set at each step. We show that these algorithms achieve asymptotically optimal sample complexity upper bounds up to constraint-dependent constants. Finally, we conduct numerical experiments with different reward distributions and constraints that validate efficient performance of LAGEX and LATS with respect to baselines.
• Abstract（参考訳）: 盗賊の純粋探索は、ハイパーパラメータのチューニングやユーザスタディの実行など、決定空間の安全性、リソース、公正性の制約が自然に現れる、複数の現実的な問題をモデル化する。 我々はこれらの問題を、未知の線形制約を持つ多腕包帯における純粋な探索として研究し、$r$$\textit{-good feasible policy}$を識別することを目的とする。 まず、制約下での純粋な探索のために、サンプルの複雑さを低く抑えたラグランジアン緩和を提案する。 この下界が,制約の逐次推定によってどのように進化するかを示す。 第二に、ラグランジアンの下界と凸最適化の特性を利用して、トラック・アンド・ストップとガミファイド・エクスプローラーの2つの計算効率の良い拡張、すなわちLATSとLAGEXを提案する。 この目的のために,制約適応型停止規則を提案し,下界を追従しながら,各ステップで実現可能な集合の悲観的な推定値を用いる。 これらのアルゴリズムは,制約依存定数の上限まで,漸近的に最適なサンプル複雑性を実現する。 最後に,LAGEX と LATS の有効性能をベースラインに対して検証する,異なる報酬分布と制約を用いた数値実験を行った。

関連論文リスト

• Contextual Bandits with Stage-wise Constraints [46.412612374393895]
  段階的制約(各ラウンドにおける制約)の存在下での文脈的包帯について検討する。 本稿では,この問題に対する高信頼度有界アルゴリズムを提案し,それに対するT$ラウンドの後悔を証明した。
  論文  参考訳（メタデータ） (2024-01-15T23:58:21Z)
• Pure Exploration in Bandits with Linear Constraints [15.547603114649464]
  マルチアーム・バンディット・セットアップにおいて、最適ポリシーを一定の信頼度で識別する問題に対処する。 この設定に最適な2つのアルゴリズムを導入する。1つはトラック・アンド・ストップ法であり、もう1つはゲーム理論に基づく手法である。 限界を検証し、制約が問題の硬さをどのように変えるかを視覚化する実験結果を提供する。
  論文  参考訳（メタデータ） (2023-06-22T10:00:33Z)
• Interactively Learning Preference Constraints in Linear Bandits [100.78514640066565]
  我々は、既知の報酬と未知の制約で逐次意思決定を研究する。 応用として,運転シミュレーションにおいて,人間の嗜好を表現するための学習制約を検討する。
  論文  参考訳（メタデータ） (2022-06-10T17:52:58Z)
• On Kernelized Multi-Armed Bandits with Constraints [16.102401271318012]
  一般に未知の報酬関数と一般未知の制約関数を併用した帯域幅問題について検討する。 本稿では,アルゴリズムの性能解析のための一般的なフレームワークを提案する。 本稿では,数値実験により提案アルゴリズムの優れた性能を示す。
  論文  参考訳（メタデータ） (2022-03-29T14:02:03Z)
• A Unifying Theory of Thompson Sampling for Continuous Risk-Averse Bandits [91.3755431537592]
  本稿では,多腕バンディット問題に対するリスク-逆トンプソンサンプリングアルゴリズムの解析を統一する。 大規模偏差理論における収縮原理を用いることで、連続リスク汎関数に対する新しい濃度境界が証明される。 リスク関数の幅広いクラスと「ニセ」関数が連続性条件を満たすことを示す。
  論文  参考訳（メタデータ） (2021-08-25T17:09:01Z)
• Shortest-Path Constrained Reinforcement Learning for Sparse Reward Tasks [59.419152768018506]
  最適ポリシーは必ずk-SP制約を満たすことを示す。 本研究では,SP制約に違反するポリシーを完全に排除する代わりに,新たなコスト関数を提案する。 また,MiniGrid,DeepMind Lab,Atari,Fetchを用いた実験の結果,提案手法はPPOを著しく改善することが示された。
  論文  参考訳（メタデータ） (2021-07-13T21:39:21Z)
• A Stochastic Composite Augmented Lagrangian Method For Reinforcement Learning [9.204659134755795]
  深層強化学習のための線形プログラミング(LP)の定式化について検討する。 拡張ラグランジアン法は、LPの解法において二重サンプリング障害に悩まされる。 深層パラメタライズされたラグランジアン法を提案する。
  論文  参考訳（メタデータ） (2021-05-20T13:08:06Z)
• An Asymptotically Optimal Primal-Dual Incremental Algorithm for Contextual Linear Bandits [129.1029690825929]
  複数の次元に沿った最先端技術を改善する新しいアルゴリズムを提案する。 非文脈線形帯域の特別な場合において、学習地平線に対して最小限の最適性を確立する。
  論文  参考訳（メタデータ） (2020-10-23T09:12:47Z)
• Nearly Dimension-Independent Sparse Linear Bandit over Small Action Spaces via Best Subset Selection [71.9765117768556]
  本研究では,高次元線形モデルの下での文脈的帯域問題について考察する。 この設定は、パーソナライズされたレコメンデーション、オンライン広告、パーソナライズされた医療など、不可欠な応用を見出す。 本稿では,最適部分集合選択法を用いて2重成長エポックを推定する手法を提案する。
  論文  参考訳（メタデータ） (2020-09-04T04:10:39Z)
• On Lower Bounds for Standard and Robust Gaussian Process Bandit Optimization [55.937424268654645]
  有界ノルムを持つ関数のブラックボックス最適化問題に対するアルゴリズム非依存な下界を考える。 本稿では, 単純さ, 汎用性, エラー確率への依存性の向上など, 後悔の下位境界を導出するための新しい証明手法を提案する。
  論文  参考訳（メタデータ） (2020-08-20T03:48:14Z)
• Bandits with Mean Bounds [33.00136718515412]
  本研究では,各アームの平均値に有界な側情報を与えるバンディット問題の変種について検討する。 これらがより厳密なガウス因子の推定に変換されることを証明し、これらの推定を利用する新しいアルゴリズムを開発する。
  論文  参考訳（メタデータ） (2020-02-19T19:36:43Z)

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

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