論文の概要: Sequential Batch Learning in Finite-Action Linear Contextual Bandits
- arxiv url: http://arxiv.org/abs/2004.06321v1
- Date: Tue, 14 Apr 2020 06:47:40 GMT
- ステータス: 処理完了
- システム内更新日: 2022-12-13 09:14:34.753736
- Title: Sequential Batch Learning in Finite-Action Linear Contextual Bandits
- Title(参考訳): 有限作用線形コンテキストバンディットにおける逐次バッチ学習
- Authors: Yanjun Han, Zhengqing Zhou, Zhengyuan Zhou, Jose Blanchet, Peter W.
Glynn, Yinyu Ye
- Abstract要約: 有限作用集合を持つ線形文脈帯域における逐次バッチ学習問題について検討する。
この問題は、実用アプリケーションにおいて、多くのパーソナライズされたシーケンシャルな意思決定問題のよりきめ細かい定式化を提供する。
- 参考スコア(独自算出の注目度): 40.01661188919779
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study the sequential batch learning problem in linear contextual bandits
with finite action sets, where the decision maker is constrained to split
incoming individuals into (at most) a fixed number of batches and can only
observe outcomes for the individuals within a batch at the batch's end.
Compared to both standard online contextual bandits learning or offline policy
learning in contexutal bandits, this sequential batch learning problem provides
a finer-grained formulation of many personalized sequential decision making
problems in practical applications, including medical treatment in clinical
trials, product recommendation in e-commerce and adaptive experiment design in
crowdsourcing.
We study two settings of the problem: one where the contexts are arbitrarily
generated and the other where the contexts are \textit{iid} drawn from some
distribution. In each setting, we establish a regret lower bound and provide an
algorithm, whose regret upper bound nearly matches the lower bound. As an
important insight revealed therefrom, in the former setting, we show that the
number of batches required to achieve the fully online performance is
polynomial in the time horizon, while for the latter setting, a
pure-exploitation algorithm with a judicious batch partition scheme achieves
the fully online performance even when the number of batches is less than
logarithmic in the time horizon. Together, our results provide a near-complete
characterization of sequential decision making in linear contextual bandits
when batch constraints are present.
- Abstract(参考訳): 有限作用集合を持つ線形コンテキスト帯域における逐次バッチ学習問題について検討し、決定者は、入ってくる個人を(多くは)一定の数のバッチに分割することを制約され、バッチの終了時にバッチ内の個人に対してのみ結果を確認することができる。
この逐次的バッチ学習問題により,臨床治験における医療治療,電子商取引における製品推薦,クラウドソーシングにおける適応的実験設計など,多種多様な個別的な意思決定問題のよりきめ細やかな定式化が可能となった。
問題の2つの設定について検討する。1つは文脈が任意に生成され、もう1つは、ある分布から引き出されたコンテキストが \textit{iid} である。
各設定において、後悔の下限を設定し、その上限が下限にほぼ一致するようなアルゴリズムを提供する。
そこで得られた重要な知見として,前者では,全オンライン性能を達成するために必要なバッチ数が時間軸の多項式であるのに対し,後者では,分節分割スキームを用いた純粋探索アルゴリズムが,時間軸のバッチ数が対数に満たない場合でも,全オンライン性能を達成していることを示す。
その結果,バッチ制約が存在する場合の線形コンテキスト帯域における逐次決定のほぼ完全な特徴付けが得られた。
関連論文リスト
- Optimal cross-learning for contextual bandits with unknown context
distributions [28.087360479901978]
本稿では,バルセイロ等のクロスラーニング環境において,文脈的包括的アルゴリズムを設計する際の問題点について考察する。
コンテクスト数によらずに$widetildeO(sqrtTK)$というほぼ厳密な(対数的要因まで)後悔境界を持つ効率的なアルゴリズムを提供する。
アルゴリズムのコアとなるのは,複数のエポックにまたがるアルゴリズムの実行をコーディネートする新しい手法である。
論文 参考訳(メタデータ) (2024-01-03T18:02:13Z) - Primal-Dual Continual Learning: Stability and Plasticity through
Lagrange Multipliers [93.17404959573146]
制約付き最適化問題を直接実行することは可能かつ有益であることを示す。
メモリベースのメソッドでは、以前のタスクからのサンプルの小さなサブセットをリプレイバッファに格納できる。
準最適境界を導出し、様々な連続学習ベンチマークで理論的結果を実証的に相関させる。
論文 参考訳(メタデータ) (2023-09-29T21:23:27Z) - Continual Learning in Linear Classification on Separable Data [34.78569443156924]
正規化の弱い学習は、逐次極大問題の解法に還元されることを示す。
次に、様々な設定の下で、忘れることやその他の関心事に関する上限を策定する。
正規化スケジューリングや重み付けといった,一般的なトレーニングプラクティスに対する実践的な影響について論じる。
論文 参考訳(メタデータ) (2023-06-06T09:34:11Z) - Smoothed Online Learning is as Easy as Statistical Learning [77.00766067963195]
この設定では、最初のオラクル効率、非回帰アルゴリズムを提供する。
古典的な設定で関数クラスが学習可能な場合、文脈的包帯に対するオラクル効率のよい非回帰アルゴリズムが存在することを示す。
論文 参考訳(メタデータ) (2022-02-09T19:22:34Z) - Parallelizing Contextual Linear Bandits [82.65675585004448]
並列な)コンテキスト線形バンディットアルゴリズムの族を提示し、その遺残はそれらの完全シーケンシャルなアルゴリズムとほぼ同一である。
また,これらの並列アルゴリズムについて,材料発見や生物配列設計の問題など,いくつかの領域で実証評価を行った。
論文 参考訳(メタデータ) (2021-05-21T22:22:02Z) - Batched Neural Bandits [107.5072688105936]
BatchNeuralUCBはニューラルネットワークと楽観性を組み合わせ、探索と探索のトレードオフに対処する。
BatchNeuralUCBは、完全なシーケンシャルバージョンと同じ後悔を達成しつつ、ポリシー更新の数を大幅に減らしています。
論文 参考訳(メタデータ) (2021-02-25T17:36:44Z) - Dynamic Batch Learning in High-Dimensional Sparse Linear Contextual
Bandits [18.64677502651614]
高次元線形空間帯域における動的バッチ学習の問題点について検討する。
我々の研究は、高次元の疎線形文脈帯域における動的バッチ学習の理論的理解への第一歩となる。
論文 参考訳(メタデータ) (2020-08-27T05:34:34Z) - Improved Algorithms for Conservative Exploration in Bandits [113.55554483194832]
文脈線形帯域設定における保守的学習問題について検討し、新しいアルゴリズムである保守的制約付きLinUCB(CLUCB2)を導入する。
我々は、既存の結果と一致したCLUCB2に対する後悔の限界を導き、多くの合成および実世界の問題において、最先端の保守的バンディットアルゴリズムよりも優れていることを実証的に示す。
論文 参考訳(メタデータ) (2020-02-08T19:35:01Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。