論文の概要: From Relaxed Indexability to Exact Indexability: A $t$-Step Approach for Partially Observable Restless Bandits
- arxiv url: http://arxiv.org/abs/2608.24167v2
- Date: Thu, 03 Sep 2026 10:04:03 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-09-04 13:51:57.984772
- Title: From Relaxed Indexability to Exact Indexability: A $t$-Step Approach for Partially Observable Restless Bandits
- Title（参考訳）: Relaxed Indexability から Exact Indexability: A $t$-Step Approach for partially Observable Restless Bandits
- Abstract要約: ウィトルインデックスポリシーは、無限水平信念状態問題を解決するスケーラブルな方法を提供する。
我々は、各補助金$m$に対して、emph$t$-step lookahead threshold Policyを提案する。
我々は、$t$-step 近似ウィトル指数が正確なウィトル指数に幾何的に収束することを証明した。
- 参考スコア（独自算出の注目度）: 0.5729426778193399
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Whittle index policies offer a scalable method for restless multi-armed bandits, but under partial observability even determining the indifference subsidy at a single belief requires solving an infinite-horizon belief-state problem with no closed-form value function. Liu [10] addresses this difficulty by linearizing the unknown decision boundary, leading to a linear system and a closed-form approximate Whittle index. However, the resulting threshold uses only a one-step active--passive comparison and does not account for longer-horizon continuation values. We extend this framework to a \emph{$t$-step lookahead threshold policy}. For each subsidy $m$, the threshold is defined by the active-minus-passive advantage under $t$-step finite-horizon value iteration. At $t=1$, the threshold is $m$-independent and recovers the linear threshold of Liu [10]; for $t>1$, it becomes subsidy-dependent through the induced first-crossing structure and tracks the exact decision boundary more closely. The proposed algorithm does not require indexability as an input and includes an indexability verification. Under the original Whittle indexability, we prove that the $t$-step approximate Whittle index converges geometrically to the exact Whittle index, \[ |\widehat W_t(ω)-W(ω)|=O(β^t). \] Numerically, all 2,715 tested three-state instances are verified as indexable according to the proposed criterion. The P95 index error decreases from $2.18\times10^{-2}$ at $t=1$ to $8.93\times10^{-4}$ at $t=8$. In an exact-comparable instance with $β=0.9999$, $t=2$ already recovers the exact Whittle-index ordering. Moderate-depth threshold policies also outperform the one-step baseline and remain close to the optimal dynamic-programming benchmark, while runtime grows mildly with $t$.
- Abstract（参考訳）: ウィットル指数ポリシは、レスレスなマルチアームバンディットのためのスケーラブルな方法を提供するが、一方の信念における無差助成金を決定する部分可観測性の下では、閉形式値関数を持たない無限水平信念状態の問題を解く必要がある。
Liu [10] は未知の決定境界を線形化することでこの問題に対処し、線形系と閉形式近似ウィトル指数に繋がる。
しかし、得られた閾値は1段階のアクティブ-パッシブ比較のみを使用し、長い水平継続値は考慮しない。
このフレームワークを \emph{$t$-step lookahead threshold policy} に拡張します。
それぞれの補助金$m$に対して、閾値は、$t$-step有限水平値反復の下でアクティブ-マイナス-パッシブ・アドバンテージによって定義される。
$t=1$の場合、閾値は$m$非依存で、Liu[10]の線形閾値を回復する。
提案アルゴリズムは、インデクサビリティを入力として必要とせず、インデクサビリティ検証を含む。
元のウィトル指数性の下では、$t$-step 近似ウィトル指数が正確なウィトル指数に幾何的に収束することを証明する。
数値的には、2,715個のテスト済みの3状態インスタンスはすべて、提案基準に従ってインデクサブルとして検証される。
P95のインデックスエラーは$t=1$で$.18\times10^{-2}$から$t=8$で$8.93\times10^{-4}$に減少する。
正確に比較可能な$β=0.9999$のインスタンスでは、$t=2$はすでに正確なWhittle-indexの順序を復元している。
適度なしきい値ポリシーは1ステップのベースラインを上回り、最適な動的プログラミングベンチマークに近づき、ランタイムは$t$で穏やかに成長する。
関連論文リスト
- A Sharp Barrier for Consistent Submodular Maximization: Any Improvement over $2-\sqrt{2}$ Entails Exponential Queries or Linear Recourse [50.69285844345291]
我々は、要素が時間とともに到着する際のソリューションの品質と安定性のトレードオフについて研究する。
我々のアルゴリズムは,有理オラクル$を$O(varepsilon-1)$recourseで実装し,そのアルゴリズムから普遍価格証明書の存在を分離する。
論文 参考訳（メタデータ） (2026-09-09T10:13:43Z) - Adversarial Resilience of Poisson-Process Submodular Maximization over Matroids: From Robust Offline Optimization to Full-Bandit Learning [55.29259818039367]
オフラインアルゴリズムに任意の制御値オラクルが与えられるとき, 一般のマトロイドに対する非負のサブモジュラー対象について検討する。
本アルゴリズムは,非単調な目的に対して1/e$,単調な目的に対して1/e$の制限係数を保持する。
結果として、オフラインからオフラインへの還元は、一般的なマトロイド制約のサブモジュラー報酬に対するシングルバンドCMABアルゴリズムをもたらす。
論文 参考訳（メタデータ） (2026-08-12T14:54:15Z) - 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) - A Spectral Phase Diagram for Binary Few-Shot Classification: Intrinsic Dimensionality, Geometric Saturation, and Representational Diagnosis [0.0]
飽和指数 $S(K) = operatornameerank(widehat_W(K)) / K$ は、プールされたクラス内サンプルの有効ランクとショットカウントとの比を測る。
インデックスはサポート機能だけで$O(d3)$ timeで計算可能で、テストラベルやトレーニングされた分類子を必要としない。
論文 参考訳（メタデータ） (2026-06-12T16:46:24Z) - Optimal Dimension-Free Sampling for Regularized Classification [56.72526267755301]
我々は、リプシッツ連続分類損失関数の幅広いクラスに対して、$(1pmvarepsilon)$-relativeエラーを達成する最適サンプリング境界を証明した。
これにはロジスティックやシグモイドの損失、ヒンジの損失、ReLUの損失といった重要な機能が含まれており、顕著で一般的な例である。
論文 参考訳（メタデータ） (2026-05-22T15:05:33Z) - When Does $\ell_2$-Boosting Overfit Benignly? High-Dimensional Risk Asymptotics and the $\ell_1$ Implicit Bias [15.113649527486276]
良性オーバーフィッティングが線形レートで失敗することを示します。
この局所化機構は信号の存在下で持続するべきであるが、正確な信号-雑音分解は未解決の問題である。
論文 参考訳（メタデータ） (2026-05-07T14:14:09Z) - Complexity of Classical Acceleration for $\ell_1$-Regularized PageRank [14.919427330415608]
FISTAは1/$ローカリティスケーリングを保ちながら$$への依存を改善することができることを示す。
我々はFISTAをわずかに過正規化された目的に基づいて解析し、チェック可能な閉じ込め条件下では、全ての刺激活性化が境界集合内に存在することを示す。
これにより、加速された$(sqrt)-1log(/varepsilon)$項と境界オーバーヘッド$sqrtvol(mathcalB)/(3/2)$からなるバウンダリが得られる。
論文 参考訳（メタデータ） (2026-02-24T17:35:46Z) - Analysis of Schedule-Free Nonconvex Optimization [0.0]
大規模学習アルゴリズムの根底にある一階法であるが、その収束性は慎重にスケジュールされたステップのヒンジを保証し、前例のないスケジュール自由地平線に依存する。
我々の$Oレートが$O(log T)$に束縛されていることを示す。
我々の研究はSFの地平線を拡張し、最適な非滑らかな速度で将来の方向をグラフ化する。
論文 参考訳（メタデータ） (2025-08-08T22:54:35Z) - Beyond likelihood ratio bias: Nested multi-time-scale stochastic approximation for likelihood-free parameter estimation [49.78792404811239]
確率分析形式が不明なシミュレーションベースモデルにおける推論について検討する。
我々は、スコアを同時に追跡し、パラメータ更新を駆動する比率のないネスト型マルチタイムスケール近似(SA)手法を用いる。
我々のアルゴリズムは、オリジナルのバイアス$Obig(sqrtfrac1Nbig)$を排除し、収束率を$Obig(beta_k+sqrtfracalpha_kNbig)$から加速できることを示す。
論文 参考訳（メタデータ） (2024-11-20T02:46:15Z) - Differentially Private Algorithms for the Stochastic Saddle Point
Problem with Optimal Rates for the Strong Gap [12.446156563700482]
凸凹型リプシッツサドル点問題は、$(epsilon,delta)$differential privacyの制約の下で解決可能であることを示す。
また、安定性と精度の間には根本的なトレードオフがあることも示している。
論文 参考訳（メタデータ） (2023-02-24T21:50:02Z) - Adaptive Stochastic Variance Reduction for Non-convex Finite-Sum
Minimization [52.25843977506935]
有限サム構造をもつ$L$-smooth, non-deuction関数に対して, AdaSpider と呼ばれる適応分散法を提案する。
そうすることで、$tildeOleft + st/epsilonコールで$epsilon-stationaryポイントを計算することができます。
論文 参考訳（メタデータ） (2022-11-03T14:41:46Z) - Best Policy Identification in Linear MDPs [70.57916977441262]
縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。
複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
論文 参考訳（メタデータ） (2022-08-11T04:12:50Z) - Towards Painless Policy Optimization for Constrained MDPs [46.12526917024248]
我々は、無限の地平線における政策最適化、$gamma$-discounted constrained Markov decision process (CMDP)について研究する。
我々の目標は、小さな制約違反で大きな期待された報酬を達成する政策を返却することである。
本稿では,任意のアルゴリズムに対して,報酬の準最適性と制約違反を拘束できる汎用的原始双対フレームワークを提案する。
論文 参考訳（メタデータ） (2022-04-11T15:08:09Z) - Optimal and instance-dependent guarantees for Markovian linear stochastic approximation [47.912511426974376]
標準スキームの最後の繰り返しの2乗誤差に対して、$t_mathrmmix tfracdn$の非漸近境界を示す。
マルコフ雑音による政策評価について,これらの結果のまとめを導出する。
論文 参考訳（メタデータ） (2021-12-23T18:47:50Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。