論文の概要: Nearly Minimax-Optimal Regret for Linear Contextual Bandits with Arbitrary Adaptive Action Sets

• arxiv url: http://arxiv.org/abs/2609.15170v1
• Date: Mon, 14 Sep 2026 07:57:45 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-09-16 07:15:06.174555
• Title: Nearly Minimax-Optimal Regret for Linear Contextual Bandits with Arbitrary Adaptive Action Sets
• Title（参考訳）: 任意アダプティブ・アクション・セットを持つ線形コンテキスト帯域に対する極小最小レグレ
• Abstract要約: パラメータや相互作用履歴に依存する任意のアクションメニューを持つ線形文脈帯域について検討する。 対数的要因まで,上下境界の一致を確立した。
• 参考スコア（独自算出の注目度）: 10.262827207917585
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study stochastic linear contextual bandits with arbitrary action menus that may depend on the fixed parameter and the interaction history. We establish matching upper and lower bounds, up to logarithmic factors. Let $d$ be the dimension, $K$ be the menu size, and $T$ the time horizon. For $2\le K\le d$, we prove an upper bound $\widetilde O(K^{1/4}\sqrt{dT})$. When $T\ge d^2$, we further prove a lower bound $Ω(K^{1/4}\sqrt{dT})$. Thus, for $T\ge d^2$ and $2\le K\le d$, the upper and lower bounds match up to logarithmic factors, and the polynomial dependence on $K$ is optimal. Compared with the previous $\widetilde O(\sqrt{dKT})$ bound, our upper bound improves the dependence on $K$ by a factor of $K^{1/4}$. For $K\ge d$, we prove an upper bound $\widetilde O_{d,T}\left(\sqrt{dT}\min\{\sqrt d,(d\log K)^{1/4}\}\right)$ and a lower bound $Ω\left(\sqrt{dT}\min\left\{\sqrt d,\left(\frac{d\log K}{\log(2d)}\right)^{1/4}\right\}\right)$. Here, $\widetilde O_{d,T}$ omits logarithmic factors only in $d$ and $T$. In particular, for polynomially large $K\ge d$, the upper and lower bounds both scale as $d^{3/4}\sqrt T$ up to logarithmic factors, improving the standard $\widetilde O(d\sqrt T)$ rate by a factor of $d^{1/4}$. As $K$ grows further, the regret smoothly recovers the $d\sqrt T$ scale once $\log K$ reaches order $d$.
• Abstract（参考訳）: 本稿では,パラメータや相互作用履歴に依存する任意のアクションメニューを持つ確率線形コンテキストバンドレットについて検討する。 対数的要因まで,上下境界の一致を確立した。 $d$を次元とし、$K$をメニューサイズとし、$T$を時間軸とする。 2ドル K\le d$ に対して、上界の$\widetilde O(K^{1/4}\sqrt{dT})$ を証明する。 T が d^2$ であるとき、より下界の $Ω(K^{1/4}\sqrt{dT})$ が証明される。 したがって、$T\ge d^2$ および $2\le K\le d$ の場合、上と下の境界は対数的因子に一致し、$K$ の多項式依存は最適である。 以前の$\widetilde O(\sqrt{dKT})$boundと比較すると、上界は$K$への依存を$K^{1/4}$の係数で改善する。 K\ge d$ に対して、上界 $\widetilde O_{d,T}\left(\sqrt{dT}\min\{\sqrt d,(d\log K)^{1/4}\right)$ と下界 $Ω\left(\sqrt{dT}\min\left\{\sqrt d,\left(\frac{d\log K}{\log(2d)}\right)^{1/4}\right\right)$ を証明します。 ここで、$\widetilde O_{d,T}$は対数係数を$d$と$T$で省略する。 特に多項式的に大きい$K\ge d$の場合、上界と下界はともに$d^{3/4}\sqrt T$として対数因子までスケールし、標準の$\widetilde O(d\sqrt T)$ rateを$d^{1/4}$で改善する。 K$がさらに大きくなると、後悔は$d\sqrt T$スケールを円滑に回復する。

関連論文リスト

• Sharp Minimax Regret for Infinite-Memory Logistic Prediction [55.29259818039367]
  Lag $j$はスケール$r_j$の予測に影響を与え、$n_T,j=T-j+1$の予測ラウンドに入る。 すべての要約可能なエンベロープに対して、局所化された混合は$cR_T(r)leq C_T(r)$を証明する。 指数関数やエンベロープの場合、有限サンプル条件の下では、トープリッツ・デサインの逆は$cR_T(r)geq c_T(r)$である。
  論文  参考訳（メタデータ） (2026-08-27T01:31:46Z)
• Toward Optimal Second-Order Path-Length Guarantee for Adversarial Multi-Armed Bandits [13.08870048693199]
  本研究は, 敵の損失列に対するK$武器帯の2次パス長後悔について検討する。 我々のアルゴリズムは$mathcalOleft(Klog(KT)+sqrtKlog(KT)bigl (1+Q_infty,2bigr)right)$ expected regret if $Q_infty,2$ is known, where $T$ is the horizon。
  論文  参考訳（メタデータ） (2026-08-17T01:17:42Z)
• Shallow ReLU$^s$ Networks in $L^p$-Type and Sobolev Spaces: Approximation and Path-Norm Controlled Generalization [12.871748162999062]
  特に、$_d$が均一測度で$1le p2$のとき、近似率は$O!left(m-fracp(2s+2d+1)-2d2dpright)$ for $1le p*$と$O!left(m-fracp(4s+3d-1)-2d+24dpright)$ for $p*p2$である。 non (複数形 nons)
  論文  参考訳（メタデータ） (2026-05-18T14:27:49Z)
• Sharp Gap-Dependent Variance-Aware Regret Bounds for Tabular MDPs [54.28273395444243]
  我々は,モノトニック値 Omega (MVP) アルゴリズムが,差分を考慮した差分依存残差境界を$tildeOleft(left(sum_Delta_h(s,a)>0 fracH2 log K land MathttVar_maxtextc$。
  論文  参考訳（メタデータ） (2025-06-06T20:33:57Z)
• On the $O(\frac{\sqrt{d}}{T^{1/4}})$ Convergence Rate of RMSProp and Its Momentum Extension Measured by $\ell_1$ Norm [54.28350823319057]
  本稿では、RMSPropとその運動量拡張を考察し、$frac1Tsum_k=1Tの収束速度を確立する。 我々の収束率は、次元$d$を除くすべての係数に関して下界と一致する。 収束率は$frac1Tsum_k=1Tと類似していると考えられる。
  論文  参考訳（メタデータ） (2024-02-01T07:21:32Z)
• $\ell_p$-Regression in the Arbitrary Partition Model of Communication [59.89387020011663]
  コーディネータモデルにおける分散$ell_p$-regression問題のランダム化通信複雑性について考察する。 p = 2$、すなわち最小二乗回帰の場合、$tildeTheta(sd2 + sd/epsilon)$ bitsの最初の最適境界を与える。 p in (1,2)$ に対して、$tildeO(sd2/epsilon + sd/mathrmpoly(epsilon)$ upper bound を得る。
  論文  参考訳（メタデータ） (2023-07-11T08:51:53Z)
• On the Minimax Regret for Online Learning with Feedback Graphs [5.721380617450645]
  強く観察可能な無向フィードバックグラフを用いて,オンライン学習を後悔する上で,上層と下層の境界を改善した。 改良された上界$mathcalObigl(sqrtalpha T(ln K)/(lnalpha)bigr)$ hold for any $alpha$ and the lower bounds for bandits and experts。
  論文  参考訳（メタデータ） (2023-05-24T17:40:57Z)
• Nearly Horizon-Free Offline Reinforcement Learning [97.36751930393245]
  S$状態、$A$アクション、計画的地平$H$で、エピソードな時間同質なMarkov決定プロセスに関するオフライン強化学習を再考する。 経験的MDPを用いた評価と計画のための,約$H$自由なサンプル複雑性境界の最初の集合を得る。
  論文  参考訳（メタデータ） (2021-03-25T18:52:17Z)
• $Q$-learning with Logarithmic Regret [60.24952657636464]
  楽観的な$Q$は$mathcalOleft(fracSAcdot mathrmpolyleft(Hright)Delta_minlogleft(SATright)right)$ cumulative regret bound, where $S$ is the number of state, $A$ is the number of action, $H$ is the planning horizon, $T$ is the total number of steps, $Delta_min$ is the least sub-Optitimality gap。
  論文  参考訳（メタデータ） (2020-06-16T13:01:33Z)

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

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