論文の概要: Conservative Contextual Bandits: Beyond Linear Representations
- arxiv url: http://arxiv.org/abs/2412.06165v1
- Date: Mon, 09 Dec 2024 02:57:27 GMT
- ステータス: 翻訳完了
- システム内更新日: 2024-12-10 14:59:08.846629
- Title: Conservative Contextual Bandits: Beyond Linear Representations
- Title(参考訳): 保守的文脈帯域:リニア表現を超えて
- Authors: Rohan Deb, Mohammad Ghavamzadeh, Arindam Banerjee,
- Abstract要約: 保守的コンバンディット(CCB)は、エージェントのポリシーと後悔を最小限に抑えるとともに、安全上の制約を満たすことを要求することで、シーケンシャルな意思決定における安全性に対処する。
Inverse Gap Weighting (IGW) ベースの探索とオンライン回帰オラクルを用いて, $mathttC-SquareCB$ と $mathttC-FastCB$ の2つのアルゴリズムを開発した。
安全性制約は高い確率で満たされており、$mathttC- SquareCB$の後悔は水平線で$T$のサブ線形であることを示す。
- 参考スコア(独自算出の注目度): 29.5947486908322
- License:
- Abstract: Conservative Contextual Bandits (CCBs) address safety in sequential decision making by requiring that an agent's policy, along with minimizing regret, also satisfies a safety constraint: the performance is not worse than a baseline policy (e.g., the policy that the company has in production) by more than $(1+\alpha)$ factor. Prior work developed UCB-style algorithms in the multi-armed [Wu et al., 2016] and contextual linear [Kazerouni et al., 2017] settings. However, in practice the cost of the arms is often a non-linear function, and therefore existing UCB algorithms are ineffective in such settings. In this paper, we consider CCBs beyond the linear case and develop two algorithms $\mathtt{C-SquareCB}$ and $\mathtt{C-FastCB}$, using Inverse Gap Weighting (IGW) based exploration and an online regression oracle. We show that the safety constraint is satisfied with high probability and that the regret of $\mathtt{C-SquareCB}$ is sub-linear in horizon $T$, while the regret of $\mathtt{C-FastCB}$ is first-order and is sub-linear in $L^*$, the cumulative loss of the optimal policy. Subsequently, we use a neural network for function approximation and online gradient descent as the regression oracle to provide $\tilde{O}(\sqrt{KT} + K/\alpha) $ and $\tilde{O}(\sqrt{KL^*} + K (1 + 1/\alpha))$ regret bounds, respectively. Finally, we demonstrate the efficacy of our algorithms on real-world data and show that they significantly outperform the existing baseline while maintaining the performance guarantee.
- Abstract(参考訳): 保守的文脈帯域(CCB)は、エージェントのポリシーと、後悔を最小限に抑えるとともに、安全上の制約を満たすことを要求する。
先行研究では,マルチアーム [Wu et al , 2016] とコンテキスト線形 [Kazerouni et al , 2017] 設定で UCB スタイルのアルゴリズムを開発した。
しかし、実際には腕のコストは非線形関数であるため、既存のUTBアルゴリズムはそのような設定では有効ではない。
本稿では,逆ギャップ重み付け(IGW)に基づく探索とオンライン回帰オラクルを用いて,CCBを線形ケースを超えて検討し,2つのアルゴリズム($\mathtt{C-SquareCB}$と$\mathtt{C-FastCB}$)を開発する。
安全性制約は高い確率で満たされ、$\matht{C-SquareCB}$の後悔は地平線上のサブラインナーであり、$\matht{C-FastCB}$の後悔は1次であり、$L^*$のサブラインナーであり、最適ポリシーの累積損失であることを示す。
その後、関数近似とオンライン勾配降下を回帰オラクルとしてニューラルネットワークを用いて、それぞれ$\tilde{O}(\sqrt{KT} + K/\alpha)$と$\tilde{O}(\sqrt{KL^*} + K (1 + 1/\alpha)$後悔境界を与える。
最後に、実世界のデータに対するアルゴリズムの有効性を実証し、性能保証を維持しつつ、既存のベースラインを大幅に上回っていることを示す。
関連論文リスト
- On the Interplay Between Misspecification and Sub-optimality Gap in
Linear Contextual Bandits [76.2262680277608]
本研究では,線形関数クラスによって期待される報酬関数を近似できるような,不特定条件下での線形文脈帯域について検討する。
このアルゴリズムは, 対数的因子に比例した設定において, ギャップ依存の残差が$tilde O (d2/Delta)$と同じであることを示す。
論文 参考訳(メタデータ) (2023-03-16T15:24:29Z) - Towards Painless Policy Optimization for Constrained MDPs [46.12526917024248]
我々は、無限の地平線における政策最適化、$gamma$-discounted constrained Markov decision process (CMDP)について研究する。
我々の目標は、小さな制約違反で大きな期待された報酬を達成する政策を返却することである。
本稿では,任意のアルゴリズムに対して,報酬の準最適性と制約違反を拘束できる汎用的原始双対フレームワークを提案する。
論文 参考訳(メタデータ) (2022-04-11T15:08:09Z) - An Efficient Pessimistic-Optimistic Algorithm for Constrained Linear
Bandits [16.103685478563072]
本稿では,一般制約付き線形帯域について考察する。
目的は、各ラウンドにおける一連の制約の対象となる水平線上の累積報酬を最大化することである。
本稿では,この問題に対する悲観的最適化アルゴリズムを提案する。
論文 参考訳(メタデータ) (2021-02-10T07:30:37Z) - Near-Optimal Regret Bounds for Contextual Combinatorial Semi-Bandits
with Linear Payoff Functions [53.77572276969548]
我々は、C$2$UCBアルゴリズムが分割マトロイド制約に対して最適な後悔結合$tildeO(dsqrtkT + dk)$を有することを示した。
一般的な制約に対して,C$2$UCBアルゴリズムで腕の報酬推定値を変更するアルゴリズムを提案する。
論文 参考訳(メタデータ) (2021-01-20T04:29:18Z) - Stochastic Bandits with Linear Constraints [69.757694218456]
制約付き文脈線形帯域設定について検討し、エージェントの目標は一連のポリシーを作成することである。
楽観的悲観的線形帯域(OPLB)と呼ばれる,この問題に対する高信頼束縛アルゴリズムを提案する。
論文 参考訳(メタデータ) (2020-06-17T22:32:19Z) - Low-Rank Generalized Linear Bandit Problems [19.052901817304743]
低ランク線型バンドイット問題において、作用の報酬は、作用と未知の低ランク行列$Theta*$の間の内部積である。
低ランク行列の被覆によって構築される指数重み付き平均予測器と、オンラインから信頼度セットへの変換パバシ2012onlineの新たな組み合わせに基づくアルゴリズムを提案する。
論文 参考訳(メタデータ) (2020-06-04T15:30:14Z) - Provably Efficient Safe Exploration via Primal-Dual Policy Optimization [105.7510838453122]
制約付きマルコフ決定過程(CMDP)を用いた安全強化学習(SRL)問題について検討する。
本稿では,関数近似設定において,安全な探索を行うCMDPの効率の良いオンラインポリシー最適化アルゴリズムを提案する。
論文 参考訳(メタデータ) (2020-03-01T17:47:03Z) - Learning Near Optimal Policies with Low Inherent Bellman Error [115.16037976819331]
エピソード強化学習における近似線形作用値関数を用いた探索問題について検討する。
我々は,検討した設定に対して最適な統計率を達成するアルゴリズムを用いて,Emphbatch仮定のみを用いて探索を行うことが可能であることを示す。
論文 参考訳(メタデータ) (2020-02-29T02:02:40Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。