論文の概要: Hierarchical Upper Confidence Bounds for Constrained Online Learning
- arxiv url: http://arxiv.org/abs/2410.17216v1
- Date: Tue, 22 Oct 2024 17:41:14 GMT
- ステータス: 翻訳完了
- システム内更新日: 2024-10-23 14:26:57.694925
- Title: Hierarchical Upper Confidence Bounds for Constrained Online Learning
- Title(参考訳): 制約付きオンライン学習のための階層的上位信頼境界
- Authors: Ali Baheri,
- Abstract要約: 階層的制約付き帯域幅(HCB)フレームワークを導入し、コンテキスト的帯域幅問題を拡張して階層的決定構造とマルチレベル制約を組み込む。
我々の理論的解析はHC-UCBのサブ線形後悔境界を確立し、すべての階層レベルでの制約満足度を高い確率で保証する。
- 参考スコア(独自算出の注目度): 4.8951183832371
- License:
- Abstract: The multi-armed bandit (MAB) problem is a foundational framework in sequential decision-making under uncertainty, extensively studied for its applications in areas such as clinical trials, online advertising, and resource allocation. Traditional MAB formulations, however, do not adequately capture scenarios where decisions are structured hierarchically, involve multi-level constraints, or feature context-dependent action spaces. In this paper, we introduce the hierarchical constrained bandits (HCB) framework, which extends the contextual bandit problem to incorporate hierarchical decision structures and multi-level constraints. We propose the hierarchical constrained upper confidence bound (HC-UCB) algorithm, designed to address the complexities of the HCB problem by leveraging confidence bounds within a hierarchical setting. Our theoretical analysis establishes sublinear regret bounds for HC-UCB and provides high-probability guarantees for constraint satisfaction at all hierarchical levels. Furthermore, we derive a minimax lower bound on the regret for the HCB problem, demonstrating the near-optimality of our algorithm. The results are significant for real-world applications where decision-making processes are inherently hierarchical and constrained, offering a robust and efficient solution that balances exploration and exploitation across multiple levels of decision-making.
- Abstract(参考訳): マルチアーム・バンディット(MAB)問題は、不確実性の下でのシーケンシャルな意思決定の基盤となる枠組みであり、治験、オンライン広告、資源配分などの分野で広く研究されている。
しかし、従来のMABの定式化は、決定が階層的に構造化されるシナリオ、複数レベルの制約、コンテキスト依存のアクション空間を含むシナリオを適切に捉えていない。
本稿では,階層的制約付き帯域幅(HCB)フレームワークを紹介し,階層的決定構造とマルチレベル制約を組み込むためのコンテキスト的帯域幅問題を拡張した。
本稿では階層的制約付き高信頼境界(HC-UCB)アルゴリズムを提案する。
我々の理論的解析はHC-UCBのサブ線形後悔境界を確立し、すべての階層レベルでの制約満足度を高い確率で保証する。
さらに,HCB問題に対する後悔を最小限に抑え,アルゴリズムの最適性を示す。
その結果は、意思決定プロセスが本質的に階層的かつ制約的であり、複数の意思決定レベルにわたる探索とエクスプロイトのバランスをとる堅牢で効率的なソリューションを提供する現実世界のアプリケーションにとって重要である。
関連論文リスト
- Offline Learning for Combinatorial Multi-armed Bandits [56.96242764723241]
Off-CMABはCMABの最初のオフライン学習フレームワークである。
Off-CMABは悲観的な報酬推定と解法を組み合わせる。
合成および実世界のデータセットの実験は、CLCBの優れた性能を強調している。
論文 参考訳(メタデータ) (2025-01-31T16:56:18Z) - Decision Making in Changing Environments: Robustness, Query-Based Learning, and Differential Privacy [59.64384863882473]
本研究では,環境が時間とともに変化する対話的意思決定の課題について考察する。
意思決定の複雑さと敵意的な設定の複雑さを提供するフレームワークを提案する。
論文 参考訳(メタデータ) (2025-01-24T21:31:50Z) - A Provably Efficient Option-Based Algorithm for both High-Level and Low-Level Learning [54.20447310988282]
異なる(高低と高低の)時間的抽象化において,後悔最小化アルゴリズムのメタアルゴリズムを交互に提案する。
高いレベルでは、半マルコフ決定プロセス(SMDP)として、固定された低レベルポリシーで、低いレベルでは内部オプションポリシーを固定された高レベルポリシーで学習する。
論文 参考訳(メタデータ) (2024-06-21T13:17:33Z) - A Primal-Dual-Assisted Penalty Approach to Bilevel Optimization with Coupled Constraints [66.61399765513383]
We developed a BLOCC algorithm to tackle BiLevel Optimization problems with Coupled Constraints。
2つのよく知られた実世界のアプリケーションでその効果を実証する。
論文 参考訳(メタデータ) (2024-06-14T15:59:36Z) - On the Complexity of Adversarial Decision Making [101.14158787665252]
決定推定係数は, 相手の意思決定に対する後悔度を低く抑えるのに必要であり, 十分であることを示す。
我々は、決定推定係数を他のよく知られた複雑性尺度の変種に結びつける新しい構造結果を提供する。
論文 参考訳(メタデータ) (2022-06-27T06:20:37Z) - Adjacency constraint for efficient hierarchical reinforcement learning [25.15808501708926]
目標条件強化学習(HRL)は、強化学習(RL)技術をスケールアップするための有望なアプローチである。
HRLは、高レベル、すなわちゴール空間のアクション空間が大きいため、トレーニングの非効率さに悩まされることが多い。
本研究では,高レベル動作空間を現在の状態の隣接する領域$k$-stepに制限することにより,この問題を効果的に緩和できることを示す。
論文 参考訳(メタデータ) (2021-10-30T09:26:45Z) - Value-Function-based Sequential Minimization for Bi-level Optimization [52.39882976848064]
勾配に基づくBi-Level Optimization (BLO)法は、現代の学習課題に広く応用されている。
機能的制約のあるBLOや悲観的なBLOなど、難解なシナリオでBLOを解くことができる勾配ベースの方法はほとんどない。
上記の問題に対処するために,BVFSM(Bi-level Value-Function-based Sequential Minimization)を提案する。
論文 参考訳(メタデータ) (2021-10-11T03:13:39Z) - Deep reinforcement learning driven inspection and maintenance planning
under incomplete information and constraints [0.0]
検査・保守方針の決定は、複雑な最適化問題を構成する。
本研究は,制約付き部分観測可能決定プロセス(POMDP)と多エージェント深層強化学習(DRL)の協調フレームワーク内で,これらの課題に対処するものである。
提案手法は, 十分に確立された政策ベースラインを上回り, 検査・介入行動の適正な処方の促進を図っている。
論文 参考訳(メタデータ) (2020-07-02T20:44:07Z) - Generating Adjacency-Constrained Subgoals in Hierarchical Reinforcement
Learning [22.319208517053816]
目標条件付き階層型強化学習(HRL)は、強化学習技術をスケールアップするための有望なアプローチである。
HRLは、高レベル、すなわちゴール空間のアクション空間がしばしば大きいため、トレーニングの非効率さに悩まされる。
動作空間上の制約は、現在の状態の$k$-stepの隣接領域に制限することで効果的に緩和できることを示す。
論文 参考訳(メタデータ) (2020-06-20T03:34:45Z) - Safety-guaranteed Reinforcement Learning based on Multi-class Support
Vector Machine [5.578687473172938]
決定論的システム力学を用いたモデルフリーなRL設定におけるハードステート制約を満たす問題に対処する。
提案アルゴリズムは離散状態と行動空間に対して開発され,多クラスサポートベクターマシン(SVM)を用いてポリシーを表現している。
論文 参考訳(メタデータ) (2020-06-12T19:58:49Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。