論文の概要: Efficient Computation of Blackwell Optimal Policies using Rational Functions

• arxiv url: http://arxiv.org/abs/2508.18252v1
• Date: Mon, 25 Aug 2025 17:41:30 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-08-26 18:43:45.899334
• Title: Efficient Computation of Blackwell Optimal Policies using Rational Functions
• Title（参考訳）: 合理的関数を用いたブラックウェル最適政策の効率的な計算法
• Authors: Dibyangshu Mukherjee, Shivaram Kalyanakrishnan,
• Abstract要約: 決定問題(MDPs)は、様々な領域にわたるシーケンシャルな意思決定をモデル化するための基礎的な枠組みを提供する。 割引された最適性は短期的な報酬を過度に優先し、一方平均最適性は強い構造的仮定に依存する。 Blackwellの最適性はこれらの課題に対処し、ディスカウントおよび平均報酬フレームワークの両方で最適性を保証する堅牢で包括的な基準を提供する。
• 参考スコア（独自算出の注目度）: 3.0529230554642752
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• Abstract: Markov Decision Problems (MDPs) provide a foundational framework for modelling sequential decision-making across diverse domains, guided by optimality criteria such as discounted and average rewards. However, these criteria have inherent limitations: discounted optimality may overly prioritise short-term rewards, while average optimality relies on strong structural assumptions. Blackwell optimality addresses these challenges, offering a robust and comprehensive criterion that ensures optimality under both discounted and average reward frameworks. Despite its theoretical appeal, existing algorithms for computing Blackwell Optimal (BO) policies are computationally expensive or hard to implement. In this paper we describe procedures for computing BO policies using an ordering of rational functions in the vicinity of $1$. We adapt state-of-the-art algorithms for deterministic and general MDPs, replacing numerical evaluations with symbolic operations on rational functions to derive bounds independent of bit complexity. For deterministic MDPs, we give the first strongly polynomial-time algorithms for computing BO policies, and for general MDPs we obtain the first subexponential-time algorithm. We further generalise several policy iteration algorithms, extending the best known upper bounds from the discounted to the Blackwell criterion.
• Abstract（参考訳）: マルコフ決定問題(MDPs)は、割引や平均報酬などの最適基準によって導かれる、様々な領域にわたるシーケンシャルな意思決定をモデル化するための基礎的な枠組みを提供する。 しかしながら、これらの基準には固有の制限がある: 割引された最適性は短期的な報酬を過度に優先し、平均最適性は強い構造的仮定に依存する。 Blackwellの最適性はこれらの課題に対処し、ディスカウントおよび平均報酬フレームワークの両方で最適性を保証する堅牢で包括的な基準を提供する。 理論上の魅力にもかかわらず、既存のBlackwell Optimal (BO) ポリシーの計算アルゴリズムは計算コストがかかるか実装が難しい。 本稿では,論理関数の順序付けによるBOポリシーの計算手順について述べる。 我々は、決定論的および一般のMDPに対して最先端のアルゴリズムを適用し、数値的な評価を有理関数の記号演算に置き換え、ビット複雑性に依存しない境界を導出する。 決定論的 MDP に対して、BO ポリシーを計算するための最初の強い多項式時間アルゴリズムを与え、一般 MDP に対して、最初の指数時間アルゴリズムを得る。 さらにいくつかのポリシー反復アルゴリズムを一般化し、最もよく知られた上限を割引からブラックウェル基準まで拡張する。

関連論文リスト

• Convergence and Sample Complexity of First-Order Methods for Agnostic Reinforcement Learning [66.4260157478436]
  政策学習における強化学習について検討する。 目的は、特定の種類の利害関係において最高の政策と競争力のある政策を見つけることである。
  論文  参考訳（メタデータ） (2025-07-06T14:40:05Z)
• A Principled Approach to Randomized Selection under Uncertainty: Applications to Peer Review and Grant Funding [68.43987626137512]
  本稿では,各項目の品質の間隔推定に基づくランダム化意思決定の枠組みを提案する。 最適化に基づく最適化手法であるMERITを導入する。 MERITが既存のアプローチで保証されていない望ましい公理特性を満たすことを証明している。
  論文  参考訳（メタデータ） (2025-06-23T19:59:30Z)
• Best-of-Both-Worlds Policy Optimization for CMDPs with Bandit Feedback [34.7178680288326]
  Stradi et al.(2024) は、マルコフ決定過程に制約のある最初のベスト・オブ・ボス・ワールドズ・アルゴリズムを提案した。 本稿では,CMDPにおける帯域幅フィードバックを用いたベスト・オブ・ワールドズ・アルゴリズムを提案する。 本アルゴリズムは政策最適化手法に基づいており, 占有率に基づく手法よりも効率的である。
  論文  参考訳（メタデータ） (2024-10-03T07:44:40Z)
• Model-Free, Regret-Optimal Best Policy Identification in Online CMDPs [17.62509045102346]
  本稿では,CMDP(Constrained Markov Decision Processs)における最適ポリシー識別問題について考察する。 私たちは、モデルフリーで、後悔の少ないアルゴリズムに興味を持ち、確率の高いほぼ最適なポリシーを特定しています。 オンラインCMDPのサブ線形後悔と制約違反を伴う既存のモデルフリーアルゴリズムでは、最適ポリシーに対する収束保証は提供されない。
  論文  参考訳（メタデータ） (2023-09-27T04:33:09Z)
• ACPO: A Policy Optimization Algorithm for Average MDPs with Constraints [36.16736392624796]
  平均基準付き制約付きMDPに対する関数近似アルゴリズムを用いた新しいポリシー最適化を提案する。 我々は,平均CMDPに対する基本感度理論を開発し,それに対応する境界をアルゴリズムの設計に用いた。 ACMDPに適応した他の最先端アルゴリズムと比較して,実験性能が優れていることを示す。
  論文  参考訳（メタデータ） (2023-02-02T00:23:36Z)
• Efficient Policy Iteration for Robust Markov Decision Processes via Regularization [49.05403412954533]
  ロバストな意思決定プロセス(MDP)は、システムのダイナミクスが変化している、あるいは部分的にしか知られていない決定問題をモデル化するためのフレームワークを提供する。 最近の研究は、長方形長方形の$L_p$頑健なMDPと正規化されたMDPの等価性を確立し、標準MDPと同じレベルの効率を享受する規則化されたポリシー反復スキームを導出した。 本研究では、政策改善のステップに焦点をあて、欲求政策と最適なロバストなベルマン作用素のための具体的な形式を導出する。
  論文  参考訳（メタデータ） (2022-05-28T04:05:20Z)
• Optimistic Policy Optimization is Provably Efficient in Non-stationary MDPs [113.8752163061151]
  非定常線形カーネルマルコフ決定過程(MDP)におけるエピソード強化学習(RL)の研究 線形最適化アンダーライン最適化アルゴリズム(PROPO)を提案する。 PROPOはスライディングウィンドウベースのポリシー評価と周期的リスタートベースのポリシー改善の2つのメカニズムを特徴としている。
  論文  参考訳（メタデータ） (2021-10-18T02:33:20Z)
• On the Optimality of Batch Policy Optimization Algorithms [106.89498352537682]
  バッチポリシー最適化は、環境と対話する前に既存のデータをポリシー構築に活用することを検討する。 信頼調整インデックスアルゴリズムは楽観的,悲観的,中立的いずれであってもミニマックス最適であることを示す。 最適値予測の本来の難易度を考慮した新しい重み付き最小値基準を提案する。
  論文  参考訳（メタデータ） (2021-04-06T05:23:20Z)

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

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