論文の概要: Contextual Bandits for Unbounded Context Distributions

• arxiv url: http://arxiv.org/abs/2408.09655v1
• Date: Mon, 19 Aug 2024 02:30:37 GMT
• ステータス: 処理完了
• システム内更新日: 2024-08-20 17:44:03.338030
• Title: Contextual Bandits for Unbounded Context Distributions
• Title（参考訳）: 非有界な文脈分布に対する文脈帯域
• Authors: Puning Zhao, Jiafei Wu, Zhe Liu, Huiwen Wu,
• Abstract要約: 非パラメトリックな文脈的包帯は、シーケンシャルな意思決定問題の重要なモデルである。 UCB探査と近接する2つの手法を提案する。 本手法は, 限界条件が弱い場合に, 最小限の後悔を達成できることを示す。 2つ目の方法は、$tildeOleft(T1-frac(alpha+1)betaalpha+(d+2)beta+T1-betaright)$の期待された後悔を達成する。
• 参考スコア（独自算出の注目度）: 12.299949253960477
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Nonparametric contextual bandit is an important model of sequential decision making problems. Under $\alpha$-Tsybakov margin condition, existing research has established a regret bound of $\tilde{O}\left(T^{1-\frac{\alpha+1}{d+2}}\right)$ for bounded supports. However, the optimal regret with unbounded contexts has not been analyzed. The challenge of solving contextual bandit problems with unbounded support is to achieve both exploration-exploitation tradeoff and bias-variance tradeoff simultaneously. In this paper, we solve the nonparametric contextual bandit problem with unbounded contexts. We propose two nearest neighbor methods combined with UCB exploration. The first method uses a fixed $k$. Our analysis shows that this method achieves minimax optimal regret under a weak margin condition and relatively light-tailed context distributions. The second method uses adaptive $k$. By a proper data-driven selection of $k$, this method achieves an expected regret of $\tilde{O}\left(T^{1-\frac{(\alpha+1)\beta}{\alpha+(d+2)\beta}}+T^{1-\beta}\right)$, in which $\beta$ is a parameter describing the tail strength. This bound matches the minimax lower bound up to logarithm factors, indicating that the second method is approximately optimal.
• Abstract（参考訳）: 非パラメトリックな文脈的包帯は、シーケンシャルな意思決定問題の重要なモデルである。 既存の研究は、$\alpha$-Tsybakovマージン条件の下で、有界サポートに対する$\tilde{O}\left(T^{1-\frac{\alpha+1}{d+2}}\right)の後悔境界を確立している。 しかし、境界のない文脈での最適後悔は分析されていない。 非有界な支援を伴う文脈的帯域幅問題の解決の課題は、探索-探索トレードオフとバイアス-分散トレードオフを同時に達成することである。 本稿では,非パラメトリックな文脈的包帯問題を非有界な文脈で解く。 UCB探査と近接する2つの手法を提案する。 最初のメソッドは固定の$k$を使用する。 本手法は,弱利得条件と比較的軽微な文脈分布の下で,最小限の後悔を達成できることを示す。 第2の方法は、アダプティブ$k$を使用する。 k$の適切なデータ駆動選択により、このメソッドは、$\tilde{O}\left(T^{1-\frac{(\alpha+1)\beta}{\alpha+(d+2)\beta}}+T^{1-\beta}\right)$の期待された後悔を達成する。 この境界は対数因子までのミニマックス下限と一致し、第2の手法がほぼ最適であることを示す。

関連論文リスト

• LC-Tsallis-INF: Generalized Best-of-Both-Worlds Linear Contextual Bandits [38.41164102066483]
  本研究では、独立かつ同一に分散したコンテキストを持つ線形文脈帯域問題について考察する。 提案アルゴリズムは、Tsallisエントロピーを持つFollow-The-Regularized-Leaderに基づいており、$alpha$-textual-Con (LC)-Tsallis-INFと呼ばれている。
  論文  参考訳（メタデータ） (2024-03-05T18:59:47Z)
• Best-of-Both-Worlds Linear Contextual Bandits [45.378265414553226]
  本研究は, 対向汚職下での多武装盗賊問題の事例である$K$腕線形文脈盗賊の問題を考察する。 我々は,理論的保証のもと,双方の敵環境に有効な戦略を開発する。 両体制の理論的保証から,我々の戦略をBest-of-Both-Worlds (BoBW) RealFTRLと呼んでいる。
  論文  参考訳（メタデータ） (2023-12-27T09:32:18Z)
• Variance-Aware Regret Bounds for Stochastic Contextual Dueling Bandits [53.281230333364505]
  本稿では, 一般化線形モデル(GLM)から, デュエルアームのバイナリ比較を生成するコンテキストデュエルバンド問題について検討する。 本稿では,SupLinUCB型アルゴリズムを提案する。このアルゴリズムは,計算効率と分散を意識したリセットバウンド$tilde Obig(dsqrtsum_t=1Tsigma_t2 + dbig)$を提案する。 我々の後悔は、比較が決定論的である場合の直感的な期待と自然に一致し、アルゴリズムは$tilde O(d)$ regretにのみ悩まされる。
  論文  参考訳（メタデータ） (2023-10-02T08:15:52Z)
• First- and Second-Order Bounds for Adversarial Linear Contextual Bandits [22.367921675238318]
  我々は,K$の腕に付随する損失関数を制限なく時間とともに変化させることができる,逆線形文脈帯域設定を考える。 V_T$ または $L_T*$ は$T$ よりもかなり小さい可能性があるため、環境が比較的良心的であれば、最悪の場合の後悔よりも改善される。
  論文  参考訳（メタデータ） (2023-05-01T14:00:15Z)
• Horizon-Free and Variance-Dependent Reinforcement Learning for Latent Markov Decision Processes [62.90204655228324]
  我々は,後期マルコフ決定過程(LMDP)における強化学習(RL)の文脈を考慮した後悔の最小化について検討した。 我々は,モデル最適化と値最適化の両手法でインスタンス化できる,新しいモデルベースアルゴリズムフレームワークを設計する。
  論文  参考訳（メタデータ） (2022-10-20T21:32:01Z)
• Causal Bandits for Linear Structural Equation Models [58.2875460517691]
  本稿では,因果図形モデルにおける最適な介入順序を設計する問題について検討する。 グラフの構造は知られており、ノードは$N$である。 頻繁性(UCBベース)とベイズ的設定に2つのアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2022-08-26T16:21:31Z)
• Variance-Aware Sparse Linear Bandits [64.70681598741417]
  余分な線形包帯に対する最悪のミニマックスは$widetildeThetaleft(sqrtdTright)$である。 ノイズがなく、アクションセットが単位球面である良性設定では、ディビジョン・アンド・コンカーを使用して、$widetildemathcal O(1)$ regretを達成することができる。 我々は,任意の分散対応線形帯域幅アルゴリズムを分散対応線形帯域幅アルゴリズムに変換する汎用フレームワークを開発した。
  論文  参考訳（メタデータ） (2022-05-26T15:55:44Z)
• Regret Lower Bound and Optimal Algorithm for High-Dimensional Contextual Linear Bandit [10.604939762790517]
  我々は、累積後悔に対して、$mathcalObig((log d)fracalpha+12Tfrac1-alpha2+log Tbig)$をミニマックス下界として証明する。 第2に,汎用的なアッパー信頼境界(UCB)戦略に着想を得た,シンプルで効率的なアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-09-23T19:35:38Z)
• Doubly robust Thompson sampling for linear payoffs [12.375561840897742]
  本稿では,Douubly Robust (DR) Thompson Sampling と呼ばれる新しいマルチアームコンテキスト帯域幅アルゴリズムを提案する。 提案アルゴリズムは, 新たな補遺分解を許容し, $tildeO(phi-2sqrtT)$の順序で補遺を改良する。
  論文  参考訳（メタデータ） (2021-02-01T23:31:10Z)
• Stochastic Bandits with Linear Constraints [69.757694218456]
  制約付き文脈線形帯域設定について検討し、エージェントの目標は一連のポリシーを作成することである。 楽観的悲観的線形帯域(OPLB)と呼ばれる,この問題に対する高信頼束縛アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-06-17T22:32:19Z)
• Naive Exploration is Optimal for Online LQR [49.681825576239355]
  最適後悔尺度は$widetildeTheta(sqrtd_mathbfu2 d_mathbfx T)$で、$T$は時間ステップの数、$d_mathbfu$は入力空間の次元、$d_mathbfx$はシステム状態の次元である。 我々の下界は、かつての$mathrmpoly(logT)$-regretアルゴリズムの可能性を排除する。
  論文  参考訳（メタデータ） (2020-01-27T03:44:54Z)

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

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