論文の概要: Improved regret bounds in tabular RL under local differential privacy

• arxiv url: http://arxiv.org/abs/2611.03026v1
• Date: Mon, 02 Nov 2026 12:21:39 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-11-06 13:47:06.921689
• Title: Improved regret bounds in tabular RL under local differential privacy
• Title（参考訳）: 局所差分プライバシー下における表状RLの後悔境界の改善
• Abstract要約: 非インタラクティブな$$-local differential privacy(LDP)の下でのS$状態と$A$アクションを用いた時間同質のエピソード強化学習における後悔の最小化について検討する。 ミニマックスの後悔は$minbigg(K, frac sqrtmax(S, exp() + 1) S A K (exp() + 1bigg)$, 定数と$sqrtlog(A)$ factorであることを証明する。
• 参考スコア（独自算出の注目度）: 4.0381704983691735
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study regret minimization for time-homogeneous episodic tabular reinforcement learning with $S$ states and $A$ actions under non-interactive $ε$-local differential privacy (LDP). In each episode $k \in [K]$, the decision-maker sends a policy to a user, the user executes the policy for $H$ steps, and sends an $ε$-locally differentially private message back to the decision-maker. When $H=1$, the problem reduces to an LDP contextual bandit with $S$ contexts, $A$ arms and horizon $K$. We prove that the minimax regret is $\min\bigg(K, \frac{ \sqrt{\max( S, \exp(ε) + 1) S A K (\exp(ε) + 1)}}{\exp(ε) - 1}\bigg)$, up to constants and a $\sqrt{\log(A)}$ factor. The upper bound is achieved by an adaptation of EXP3 and a unary encoding mechanism. When $H > 1$, and for small $ε$, we show a lower bound in $Ω(HS\frac{\sqrt{A K}}ε)$ and an upper bound in $\tilde{O}(H^2 S^2 \frac{\sqrt{ AK}}ε)$. The upper bound is achieved by an algorithm based on UCBVI and a unary encoding mechanism. For small $ε$, these bounds improve the previously known lower bound by a factor $\sqrt{S}$ and the previously known upper bound by a factor of $H \sqrt{A}$.
• Abstract（参考訳）: 本研究では,非インタラクティブな$ε$-ローカル差分プライバシー(LDP)の下でのS$状態と$A$動作を用いた時間同質な表層強化学習における後悔の最小化について検討した。 各エピソードの$k \in [K]$で、意思決定者はユーザに対してポリシーを送信し、ユーザは$H$ステップのポリシーを実行し、意思決定者に対してε$ローカルに微分されたプライベートメッセージを送信する。 H=1$のとき、問題は、$S$コンテキスト、$A$アーム、地平線$K$で、LDPコンテキストの帯域幅に減少する。 ミニマックスの後悔は$\min\bigg(K, \frac{ \sqrt{\max(S, \exp(ε) + 1) S A K (\exp(ε) + 1)}}{\exp(ε) - 1}\bigg)$であることを証明する。 上界はEXP3の適応と1つの符号化機構によって達成される。 H > 1$ で小さな$ε$ の場合、$Ω(HS\frac{\sqrt{A K}}ε)$ で下界、$\tilde{O}(H^2 S^2 \frac{\sqrt{AK}}ε)$ で上界を示す。 上界は、UCBVIと一意符号化機構に基づくアルゴリズムにより達成される。 小さな$ε$の場合、これらの境界は既知下界を$\sqrt{S}$で改善し、既知上界を$H \sqrt{A}$で改善する。

関連論文リスト

• Nearly Minimax-Optimal Regret for Linear Contextual Bandits with Arbitrary Adaptive Action Sets [10.262827207917585]
  パラメータや相互作用履歴に依存する任意のアクションメニューを持つ線形文脈帯域について検討する。 対数的要因まで,上下境界の一致を確立した。
  論文  参考訳（メタデータ） (2026-09-14T07:57:45Z)
• Asymptotically Optimal Regret for Reinforcement Learning without Horizon Dependence [54.59847568544922]
  有限水平時間同質なマルコフ決定過程に対して、$A$状態、$A$アクション、hoighty $H$、および1ドルで有界なトラジェクティブ当たりの合計報酬について、地平自由な後悔について検討する。 失敗確率$$K$はエピソード数で$tilde O(sqrtSAK+S3K)$ hides $mathsfpolyである。
  論文  参考訳（メタデータ） (2026-07-22T07:42:19Z)
• Tighter Regret Bounds for Contextual Action-Set Reinforcement Learning [17.131069269126776]
  固定報酬と遷移関数を用いて,エピソード依存の許容アクションセットを用いて,エピソード強化学習について検討した。 エピソードごとの最適値に対して累積後悔(sum_k=1K[V*,Mk - Vk,Mk]$)で評価する。 MVPアルゴリズムが自然にこのフレームワークに拡張され、強力な理論的保証を享受していることを示す。
  論文  参考訳（メタデータ） (2026-05-15T07:28:42Z)
• Near-Optimal Convergence of Accelerated Gradient Methods under Generalized and $(L_0, L_1)$-Smoothness [57.93371273485736]
  我々は、最近提案された$ell$-smoothness条件$|nabla2f(x)|| le ellleft(||nabla f(x)||right),$$$L$-smoothnessと$(L_0,L_1)$-smoothnessを一般化する関数を持つ凸最適化問題の一階法について検討する。
  論文  参考訳（メタデータ） (2025-08-09T08:28:06Z)
• Context-lumpable stochastic bandits [49.024050919419366]
  我々は、$S$コンテキストと$K$アクションによる文脈的盗賊問題を考える。 我々は,最大$widetilde O(r (S +K )/epsilon2)$サンプルを用いて,$epsilon$-optimal Policyを出力するアルゴリズムを提案する。 後悔の設定では、T$までの累積後悔を$widetilde O(sqrtr3(S+K)T)$で束縛するアルゴリズムを与える。
  論文  参考訳（メタデータ） (2023-06-22T17:20:30Z)
• 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)
• Near-Minimax-Optimal Risk-Sensitive Reinforcement Learning with CVaR [58.40575099910538]
  本研究は,リスク許容度が$tau$のCVaR(Conditional Value at Risk)の目的に着目し,リスクに敏感な強化学習(RL)について検討する。 ミニマックスCVaRの後悔率は$Omega(sqrttau-1AK)$で、$A$はアクションの数、$K$はエピソード数である。 我々は,このアルゴリズムが連続性仮定の下で$widetilde O(tau-1sqrtSAK)$の最適後悔を達成し,一般に近似することを示す。
  論文  参考訳（メタデータ） (2023-02-07T02:22:31Z)
• Minimal Expected Regret in Linear Quadratic Control [79.81807680370677]
  オンライン学習アルゴリズムを考案し、その期待された後悔を保証します。 当時のこの後悔は、$A$と$B$が未知の場合、$widetildeO((d_u+d_x)sqrtd_xT)$によって上界(i)となる。
  論文  参考訳（メタデータ） (2021-09-29T14:07:21Z)
• Nearly Horizon-Free Offline Reinforcement Learning [97.36751930393245]
  S$状態、$A$アクション、計画的地平$H$で、エピソードな時間同質なMarkov決定プロセスに関するオフライン強化学習を再考する。 経験的MDPを用いた評価と計画のための,約$H$自由なサンプル複雑性境界の最初の集合を得る。
  論文  参考訳（メタデータ） (2021-03-25T18:52:17Z)

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

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