論文の概要: Regret minimization in Linear Bandits with offline data via extended D-optimal exploration
- arxiv url: http://arxiv.org/abs/2508.08420v1
- Date: Mon, 11 Aug 2025 19:14:56 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-08-13 21:07:34.21208
- Title: Regret minimization in Linear Bandits with offline data via extended D-optimal exploration
- Title（参考訳）: 拡張D-最適探査によるオフラインデータを用いた線形帯域のレギュレット最小化
- Authors: Sushant Vijayan, Arun Suggala, Karthikeyan VS, Soumyabrata Pal,
- Abstract要約: 本稿では, 線形帯域におけるオンライン後悔の問題を, 基礎となる帯域モデルから事前観測(オフラインデータ)にアクセスして考察する。
オフライン・オンライン・フェイズド・エミネーション(OOPE)というアルゴリズムは,オフラインデータを効果的に組み込んでオンラインの後悔を軽減する。
- 参考スコア（独自算出の注目度）: 10.562108865927007
- License: http://creativecommons.org/licenses/by-nc-sa/4.0/
- Abstract: We consider the problem of online regret minimization in linear bandits with access to prior observations (offline data) from the underlying bandit model. There are numerous applications where extensive offline data is often available, such as in recommendation systems, online advertising. Consequently, this problem has been studied intensively in recent literature. Our algorithm, Offline-Online Phased Elimination (OOPE), effectively incorporates the offline data to substantially reduce the online regret compared to prior work. To leverage offline information prudently, OOPE uses an extended D-optimal design within each exploration phase. OOPE achieves an online regret is $\tilde{O}(\sqrt{\deff T \log \left(|\mathcal{A}|T\right)}+d^2)$. $\deff \leq d)$ is the effective problem dimension which measures the number of poorly explored directions in offline data and depends on the eigen-spectrum $(\lambda_k)_{k \in [d]}$ of the Gram matrix of the offline data. The eigen-spectrum $(\lambda_k)_{k \in [d]}$ is a quantitative measure of the \emph{quality} of offline data. If the offline data is poorly explored ($\deff \approx d$), we recover the established regret bounds for purely online setting while, when offline data is abundant ($\Toff >> T$) and well-explored ($\deff = o(1) $), the online regret reduces substantially. Additionally, we provide the first known minimax regret lower bounds in this setting that depend explicitly on the quality of the offline data. These lower bounds establish the optimality of our algorithm in regimes where offline data is either well-explored or poorly explored. Finally, by using a Frank-Wolfe approximation to the extended optimal design we further improve the $O(d^{2})$ term to $O\left(\frac{d^{2}}{\deff} \min \{ \deff,1\} \right)$, which can be substantial in high dimensions with moderate quality of offline data $\deff = \Omega(1)$.
- Abstract（参考訳）: 本稿では,線形帯域におけるオンライン後悔の最小化の問題について考察し,その基礎となる帯域モデルから事前観測(オフラインデータ)にアクセス可能であることを考察する。
推薦システムやオンライン広告など、大規模なオフラインデータが頻繁に利用できるアプリケーションも数多く存在する。
その結果、近年の文献ではこの問題が集中的に研究されている。
オフライン・オンライン・フェイズド・エミッション(OOPE)というアルゴリズムは,オフラインデータを効果的に組み込んでオンラインの後悔を軽減する。
オフライン情報を巧みに活用するために、OOPEは探索フェーズ毎に拡張されたD-最適設計を使用する。
OOPE は $\tilde{O}(\sqrt{\deff T \log \left(|\mathcal{A}|T\right)}+d^2)$ である。
$\deff \leq d)$ は、オフラインデータのあまり探索されていない方向の数を計測し、オフラインデータのグラム行列の固有スペクトル $(\lambda_k)_{k \in [d]}$ に依存する効果的な問題次元である。
eigen-spectrum $(\lambda_k)_{k \in [d]}$はオフラインデータのemph{quality}の定量的測度である。
オフラインデータが十分に調査されていない場合(\deff \approx d$)、オフラインデータが豊富な場合(\Toff >> T$)と、よく調査された場合(\deff = o(1) $)、オンラインの後悔は大幅に減少する。
さらに、この設定において、オフラインデータの品質に明示的に依存する、最初の既知のミニマックス後悔の低い境界を提供する。
これらの下位境界は、オフラインデータがよく探索されているか、十分に探索されていない状態において、我々のアルゴリズムの最適性を確立する。
最後に、拡張最適設計へのフランク=ウルフ近似を用いることで、$O(d^{2})$項を$O\left(\frac{d^{2}}{\deff} \min \{ \deff,1\} \right)$に改善する。
関連論文リスト
- Contextual Online Pricing with (Biased) Offline Data [22.723289890639723]
バイアスのあるオフラインデータを用いて、コンテキストのオンライン価格について検討する。
Optimism-in-the-face-of-Uncertainty (OFU) ポリシは、最小限の最適化、インスタンス依存のリセットバウンドである $tildemathcalObig を実現する。
論文 参考訳（メタデータ） (2025-07-03T16:21:49Z) - Augmenting Online RL with Offline Data is All You Need: A Unified Hybrid RL Algorithm Design and Analysis [18.323002218335215]
本稿では、エージェントがオフラインデータセットとオンラインインタラクションの両方を利用して最適なポリシーを学習できる強化学習(RL)のためのハイブリッド学習フレームワークについて検討する。
統合されたアルゴリズムと分析を行い、オフラインデータセットによる信頼性に基づくオンラインRLアルゴリズムの強化は、純粋なオンラインまたはオフラインのアルゴリズムよりも優れていることを示す。
論文 参考訳（メタデータ） (2025-05-19T22:58:54Z) - On the Statistical Complexity for Offline and Low-Adaptive Reinforcement Learning with Structures [63.36095790552758]
本稿では、オフラインおよび低適応環境における強化学習(RL)の統計的基礎に関する最近の進歩を概観する。
まず最初に、オフラインRLが、RLを使用する最近のAIブレークスルーとは無関係であっても、ほぼすべての実生活のML問題に対して適切なモデルである理由について議論する。
オフラインポリシー評価(OPE)とオフラインポリシー学習(OPL)という,オフラインRLの基本的な2つの問題に展開する。
論文 参考訳（メタデータ） (2025-01-03T20:27:53Z) - Order-Optimal Instance-Dependent Bounds for Offline Reinforcement Learning with Preference Feedback [56.6950165117658]
我々は、暗黙の報酬が未知パラメータの線形関数である、好みフィードバックによるオフライン強化学習について検討する。
そこで我々は,UnderlineLocally Underline Underline Weights あるいは sc RL-LOW を用いたアルゴリズムを提案する。
我々は,sc RL-LOWの次数次最適性を示すため,単純な後悔マッチングの指数において,下限と上限が順序的に一致することが観察された。
論文 参考訳（メタデータ） (2024-06-18T02:03:12Z) - Optimal Best-Arm Identification in Bandits with Access to Offline Data [27.365122983434887]
オフラインデータとオンライン学習を組み合わせることを検討する。
差分$が小さい場合、サンプルの複雑さに基づいて低い境界に一致するアルゴリズムを開発する。
我々のアルゴリズムは, サンプル当たりの平均取得コストが$tildeO(K)$で計算的に効率的であり, 下界問題の最適条件の注意深い評価に頼っている。
論文 参考訳（メタデータ） (2023-06-15T11:12:35Z) - On Instance-Dependent Bounds for Offline Reinforcement Learning with
Linear Function Approximation [80.86358123230757]
本稿では,Bootstrapped and Constrained Pessimistic Value Iteration (BCP-VI) というアルゴリズムを提案する。
部分的なデータカバレッジの仮定の下で、BCP-VI は最適な Q-値関数に正のギャップがあるときに、オフライン RL に対して $tildemathcalO(frac1K)$ の高速レートを得る。
これらは、アダプティブデータからの線形関数近似を持つオフラインRLに対してそれぞれ、最初の$tildemathcalO(frac1K)$boundと絶対零部分最適境界である。
論文 参考訳（メタデータ） (2022-11-23T18:50:44Z) - Pessimism in the Face of Confounders: Provably Efficient Offline Reinforcement Learning in Partially Observable Markov Decision Processes [99.26864533035454]
半可観測マルコフ決定過程におけるオフライン強化学習(RL)について検討する。
本稿では,UnderlineProxy変数 underlinePessimistic UnderlinePolicy UnderlineOptimization (textttP3O)アルゴリズムを提案する。
textttP3Oは、確立されたデータセットを持つPOMDPのための証明可能な最初のオフラインRLアルゴリズムである。
論文 参考訳（メタデータ） (2022-05-26T19:13:55Z) - Policy Finetuning: Bridging Sample-Efficient Offline and Online
Reinforcement Learning [59.02541753781001]
本稿では、学習者が「参照ポリシー」にさらにアクセス可能なオンラインRLの政策微調整に関する理論的研究を開始する。
我々はまず、$varepsilon$$widetildeO(H3SCstar/varepsilon2)$のエピソード内で、ほぼ最適ポリシーを求める鋭いオフライン還元アルゴリズムを設計する。
次に、Omega(H3SminCstar, A/varepsilon2)$のサンプル複雑性を、任意のポリシー微調整アルゴリズムに対して低いバウンドで設定します。
論文 参考訳（メタデータ） (2021-06-09T08:28:55Z) - High-Dimensional Sparse Linear Bandits [67.9378546011416]
データ・ポーア・システマティクスにおける疎線形包帯に対して、新しい$Omega(n2/3)$ dimension-free minimax regret lower boundを導出する。
また、関連する特徴に対する信号の大きさに関する追加の仮定の下で、次元のない$O(sqrtn)$ regret上界も証明する。
論文 参考訳（メタデータ） (2020-11-08T16:48:11Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。