論文の概要: Provably Efficient High-Dimensional Bandit Learning with Batched Feedbacks

• arxiv url: http://arxiv.org/abs/2311.13180v2
• Date: Fri, 24 Nov 2023 18:31:21 GMT
• ステータス: 処理完了
• システム内更新日: 2023-11-27 12:26:37.882070
• Title: Provably Efficient High-Dimensional Bandit Learning with Batched Feedbacks
• Title（参考訳）: バッチフィードバックを用いた高次元帯域学習
• Authors: Jianqing Fan, Zhaoran Wang, Zhuoran Yang, and Chenlu Ye
• Abstract要約: 本稿では,オンラインインタラクションのT$ステップをバッチに分割したバッチフィードバックによる高次元マルチアームコンテキストバンドレットについて検討する。 具体的には、各バッチは以前のバッチに依存するポリシーに従ってデータを収集し、その報酬はバッチの最後にのみ明らかにする。 我々のアルゴリズムは,$mathcalO( log T)$ バッチで完全に逐次的に設定されたものに匹敵する後悔の限界を達成している。
• 参考スコア（独自算出の注目度）: 93.00280593719513
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study high-dimensional multi-armed contextual bandits with batched feedback where the $T$ steps of online interactions are divided into $L$ batches. In specific, each batch collects data according to a policy that depends on previous batches and the rewards are revealed only at the end of the batch. Such a feedback structure is popular in applications such as personalized medicine and online advertisement, where the online data often do not arrive in a fully serial manner. We consider high-dimensional and linear settings where the reward function of the bandit model admits either a sparse or low-rank structure and ask how small a number of batches are needed for a comparable performance with fully dynamic data in which $L = T$. For these settings, we design a provably sample-efficient algorithm which achieves a $ \mathcal{\tilde O}(s_0^2 \log^2 T)$ regret in the sparse case and $ \mathcal{\tilde O} ( r ^2 \log^2 T)$ regret in the low-rank case, using only $L = \mathcal{O}( \log T)$ batches. Here $s_0$ and $r$ are the sparsity and rank of the reward parameter in sparse and low-rank cases, respectively, and $ \mathcal{\tilde O}(\cdot)$ omits logarithmic factors involving the feature dimensions. In other words, our algorithm achieves regret bounds comparable to those in fully sequential setting with only $\mathcal{O}( \log T)$ batches. Our algorithm features a novel batch allocation method that adjusts the batch sizes according to the estimation accuracy within each batch and cumulative regret. Furthermore, we also conduct experiments with synthetic and real-world data to validate our theory.
• Abstract（参考訳）: 本稿では,オンラインインタラクションのT$ステップをバッチに分割したバッチフィードバックによる高次元マルチアームコンテキストバンドレットについて検討する。 具体的には、各バッチは以前のバッチに依存するポリシーに従ってデータを収集し、その報酬はバッチの最後にのみ明らかにする。 このようなフィードバック構造は、パーソナライズされた医療やオンライン広告などのアプリケーションで人気があり、オンラインデータが完全にシリアルに届かないことが多い。 我々は、banditモデルの報酬関数がスパースまたはローランク構造のいずれかを認め、$l = t$の完全な動的データと同等の性能を実現するために、バッチがどれだけ小さいか尋ねる高次元および線形の設定を考える。 これらの設定のために、スパースケースで$ \mathcal{\tilde O}(s_0^2 \log^2 T)$後悔と$ \mathcal{\tilde O} (r ^2 \log^2 T)$後悔を、低ランクケースでは$L = \mathcal{O}( \log T)$バッチのみを用いて、証明可能なサンプル効率のアルゴリズムを設計する。 ここで、$s_0$ と $r$ はそれぞれスパースとローランクのケースにおける報酬パラメータのスパースとランクであり、$mathcal{\tilde o}(\cdot)$ は特徴次元を含む対数因子を省略する。 言い換えれば、我々のアルゴリズムは、$\mathcal{O}( \log T)$ batches で完全に逐次設定のものと同等の後悔境界を達成する。 本アルゴリズムは,各バッチ内の推定精度と累積後悔に応じてバッチサイズを調整する新しいバッチ割当法を特徴とする。 さらに,合成データと実世界データを用いて実験を行い,理論を検証する。

関連論文リスト

• Fast Rates for Bandit PAC Multiclass Classification [73.17969992976501]
  我々は,帯域幅フィードバックを用いたマルチクラスPAC学習について検討し,入力を$K$ラベルの1つに分類し,予測されたラベルが正しいか否かに制限する。 我々の主な貢献は、問題の無知な$(varepsilon,delta)$PACバージョンのための新しい学習アルゴリズムを設計することである。
  論文  参考訳（メタデータ） (2024-06-18T08:54:04Z)
• Cooperative Thresholded Lasso for Sparse Linear Bandit [6.52540785559241]
  本稿では,マルチエージェント・スパース文脈線形帯域問題に対処する新しい手法を提案する。 疎線形帯域における行単位の分散データに対処する最初のアルゴリズムである。 後悔を最小限に抑えるために効率的な特徴抽出が重要となる高次元マルチエージェント問題に適用可能である。
  論文  参考訳（メタデータ） (2023-05-30T16:05:44Z)
• Efficient List-Decodable Regression using Batches [33.300073775123835]
  バッチを用いたリスト復号化線形回帰の研究を始める。 この設定では、バッチの$alpha in (0,1]$分しか真ではない。 それぞれの真のバッチは、共通の未知の分布から$ge n$ i.i.dのサンプルを含み、残りのバッチは、任意の、あるいは、敵対的なサンプルを含むことができる。
  論文  参考訳（メタデータ） (2022-11-23T07:08:00Z)
• Near-Optimal Regret Bounds for Multi-batch Reinforcement Learning [54.806166861456035]
  本研究では,有限水平マルコフ決定過程(MDP)によってモデル化されたエピソディック強化学習(RL)問題をバッチ数に制約を加えて検討する。 我々は,$tildeO(sqrtSAH3Kln (1/delta))$tildeO(cdot)をほぼ最適に後悔するアルゴリズムを設計し,$(S,A,H,K)$の対数項を$K$で隠蔽する。 技術的貢献は2つある: 1) 探索のためのほぼ最適設計スキーム
  論文  参考訳（メタデータ） (2022-10-15T09:22:22Z)
• Almost Optimal Batch-Regret Tradeoff for Batch Linear Contextual Bandits [45.43968161616453]
  バッチ線形文脈帯域に対する最適バッチ-regretトレードオフについて検討する。 時間的地平線が成長するにつれて2相表現を特徴とする後悔の保証を証明します。 また, 動的上界に依存した新しい行列不等式濃度を証明した。
  論文  参考訳（メタデータ） (2021-10-15T12:32:33Z)
• Thresholded Lasso Bandit [70.17389393497125]
  Thresholded Lasso banditは、報酬関数を定義するベクトルとスパースサポートを推定するアルゴリズムである。 一般には $mathcalO( log d + sqrtT )$ や $mathcalO( log d + sqrtT )$ としてスケールする非漸近的後悔の上界を確立する。
  論文  参考訳（メタデータ） (2020-10-22T19:14:37Z)
• Stochastic Bandits with Linear Constraints [69.757694218456]
  制約付き文脈線形帯域設定について検討し、エージェントの目標は一連のポリシーを作成することである。 楽観的悲観的線形帯域(OPLB)と呼ばれる,この問題に対する高信頼束縛アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-06-17T22:32:19Z)
• An Efficient Algorithm For Generalized Linear Bandit: Online Stochastic Gradient Descent and Thompson Sampling [83.48992319018147]
  プレイヤーが過去の観測結果に基づいて逐次意思決定を行い、累積報酬を最大化する文脈的帯域幅問題を考える。 この問題を解決する自然な方法は、ステップごとの時間とメモリの複雑さを一定に抑えるために、オンライン勾配降下(SGD)を適用することである。 本研究では,オンラインSGDが一般化線形帯域問題に適用可能であることを示す。 過去の情報を活用するためにシングルステップのSGD更新を利用するSGD-TSアルゴリズムは、全時間複雑度で$tildeO(sqrtT)$ regretを達成する。
  論文  参考訳（メタデータ） (2020-06-07T01:12:39Z)
• Optimal Contextual Pricing and Extensions [32.152826900874075]
  このアルゴリズムは$Omega(d log T)$ lower bound up to the $d log d$ additive factor。 これらのアルゴリズムは、凸領域のスタイナー固有値を様々なスケールで有界化する新しい手法に基づいている。
  論文  参考訳（メタデータ） (2020-03-03T18:46:29Z)

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

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