論文の概要: Upper Counterfactual Confidence Bounds: a New Optimism Principle for
Contextual Bandits
- arxiv url: http://arxiv.org/abs/2007.07876v3
- Date: Fri, 12 Feb 2021 19:05:14 GMT
- ステータス: 処理完了
- システム内更新日: 2022-11-10 05:28:23.360900
- Title: Upper Counterfactual Confidence Bounds: a New Optimism Principle for
Contextual Bandits
- Title(参考訳): 上位対実的信頼境界--文脈帯域に対する新しい最適化原理
- Authors: Yunbei Xu and Assaf Zeevi
- Abstract要約: 本研究では,実現可能性条件下での一般的な文脈的包帯について検討する。
提案手法は,"Upper Counterfactual Confidence Bounds"と呼ばれる楽観的アルゴリズムを設計するための単純な汎用原理である。
これらのアルゴリズムは、大きなコンテキスト空間が存在する場合に、確実に最適かつ効率的であることを示す。
- 参考スコア(独自算出の注目度): 11.840747467007963
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The principle of optimism in the face of uncertainty is one of the most
widely used and successful ideas in multi-armed bandits and reinforcement
learning. However, existing optimistic algorithms (primarily UCB and its
variants) are often unable to deal with large context spaces. Essentially all
existing well performing algorithms for general contextual bandit problems rely
on weighted action allocation schemes; and theoretical guarantees for
optimism-based algorithms are only known for restricted formulations. In this
paper we study general contextual bandits under the realizability condition,
and propose a simple generic principle to design optimistic algorithms, dubbed
"Upper Counterfactual Confidence Bounds" (UCCB). We show that these algorithms
are provably optimal and efficient in the presence of large context spaces. Key
components of UCCB include: 1) a systematic analysis of confidence bounds in
policy space rather than in action space; and 2) the potential function
perspective that is used to express the power of optimism in the contextual
setting. We further show how the UCCB principle can be extended to infinite
action spaces, by constructing confidence bounds via the newly introduced
notion of "counterfactual action divergence."
- Abstract(参考訳): 不確実性に直面した楽観主義の原理は、多武装の盗賊や強化学習において最も広く使われ、成功したアイデアの1つである。
しかし、既存の楽観的なアルゴリズム(主に UCB とその変種)は大きなコンテキスト空間を扱うことができないことが多い。
本質的には、一般的な文脈的バンディット問題の既存の実行アルゴリズムはすべて重み付けされた行動割当スキームに依存しており、最適化に基づくアルゴリズムの理論的保証は制限された定式化でのみ知られている。
本稿では、実現可能性条件下での一般的なコンテキスト帯域について検討し、"Upper Counterfactual Confidence Bounds"(UCCB)と呼ばれる楽観的アルゴリズムを設計するための単純な汎用原理を提案する。
これらのアルゴリズムは,大規模文脈空間の存在下では最適かつ効率的であることが証明できる。
UCCBの主な構成要素は以下のとおりである。
1)行動空間ではなく政策空間における信頼境界の体系的分析
2) 文脈設定における楽観主義の力を表現するために用いられるポテンシャル関数の観点。
さらに, UCCBの原理を無限の作用空間に拡張し, 新たに導入された「対実的作用発散」という概念を通じて信頼境界を構築する方法を示す。
関連論文リスト
- Unified theory of upper confidence bound policies for bandit problems targeting total reward, maximal reward, and more [0.8287206589886879]
上位信頼境界(UCB)ポリシは、古典的全逆バンディット問題に対する順序最適解として認識される。
以上の結果から,UCB政策は全回帰問題と最大帯域幅問題の両方において順序最適性を実現する。
改善の可能性が最も高い腕を引くことを目的としたPIUCBアルゴリズムを提案する。
論文 参考訳(メタデータ) (2024-11-01T03:39:33Z) - Learning via Surrogate PAC-Bayes [13.412960492870996]
PAC-Bayes学習は、学習アルゴリズムの一般化能力を研究するための包括的な設定である。
本稿では,一連の代理学習目標を最適化することで,反復学習アルゴリズムを構築するための新しい原則的戦略を提案する。
PAC-Bayes境界による学習の一般的なレシピを提供するのに加えて、(i)サロゲートの反復最適化が元の一般化境界の最適化を意味することを示す理論的結果を提供する。
論文 参考訳(メタデータ) (2024-10-14T07:45:50Z) - e-COP : Episodic Constrained Optimization of Policies [12.854752753529151]
本稿では,制約付き強化学習(RL)のための第1ポリシー最適化アルゴリズムを提案する。
提案アルゴリズムは, エピソード設定に適応したSoTA (non-episodic) アルゴリズムと類似あるいは良好な性能を示す。
論文 参考訳(メタデータ) (2024-06-13T20:12:09Z) - Bayesian Design Principles for Frequentist Sequential Learning [11.421942894219901]
逐次学習問題に対する頻繁な後悔を最適化する理論を開発する。
各ラウンドで「アルゴリズム的信念」を生成するための新しい最適化手法を提案する。
本稿では,マルチアームバンディットの「ベスト・オブ・オール・ワールド」な経験的性能を実現するための新しいアルゴリズムを提案する。
論文 参考訳(メタデータ) (2023-10-01T22:17:37Z) - Oracle-Efficient Pessimism: Offline Policy Optimization in Contextual
Bandits [82.28442917447643]
悲観的OPOのための最初の一般オラクル効率アルゴリズムを提案する。
従来の悲観的アプローチと類似した統計的保証を得る。
我々は多種多様な構成の非正規化OPOに対して優位性を示す。
論文 参考訳(メタデータ) (2023-06-13T17:29:50Z) - Contextual bandits with concave rewards, and an application to fair
ranking [108.48223948875685]
CBCR (Contextual Bandits with Concave Rewards) に対する反省点のある最初のアルゴリズムを提案する。
我々は,スカラー・リワード問題に対するCBCRの後悔から,新たな縮小を導出した。
推薦の公正さによって動機づけられたCBCRの特別事例として,ランク付けと公正を意識した目的について述べる。
論文 参考訳(メタデータ) (2022-10-18T16:11:55Z) - Policy Mirror Descent for Regularized Reinforcement Learning: A
Generalized Framework with Linear Convergence [60.20076757208645]
本稿では,正規化RLを解くためのGPMDアルゴリズムを提案する。
我々は,このアルゴリズムが次元自由な方法で,全範囲の学習率に線形に収束することを実証した。
論文 参考訳(メタデータ) (2021-05-24T02:21:34Z) - On the Optimality of Batch Policy Optimization Algorithms [106.89498352537682]
バッチポリシー最適化は、環境と対話する前に既存のデータをポリシー構築に活用することを検討する。
信頼調整インデックスアルゴリズムは楽観的,悲観的,中立的いずれであってもミニマックス最適であることを示す。
最適値予測の本来の難易度を考慮した新しい重み付き最小値基準を提案する。
論文 参考訳(メタデータ) (2021-04-06T05:23:20Z) - Beyond UCB: Optimal and Efficient Contextual Bandits with Regression
Oracles [112.89548995091182]
我々は、文脈的帯域幅からオンライン回帰への、初めての普遍的で最適な削減を提供する。
我々のアルゴリズムは、実現可能性以上の分布仮定は必要とせず、コンテキストが逆選択された場合でも機能する。
論文 参考訳(メタデータ) (2020-02-12T11:33:46Z) - Improved Algorithms for Conservative Exploration in Bandits [113.55554483194832]
文脈線形帯域設定における保守的学習問題について検討し、新しいアルゴリズムである保守的制約付きLinUCB(CLUCB2)を導入する。
我々は、既存の結果と一致したCLUCB2に対する後悔の限界を導き、多くの合成および実世界の問題において、最先端の保守的バンディットアルゴリズムよりも優れていることを実証的に示す。
論文 参考訳(メタデータ) (2020-02-08T19:35:01Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。