用图滤波思想加速动态规划,让算法更快收敛。
Unrolling Dynamic Programming via Graph Filters
- 将动态规划迭代过程转化为可学习的图滤波模型
- 在网格环境中仅需少量迭代即可逼近最优策略
- 适合需要快速决策的强化学习场景
动态规划是工程领域常用的基本工具,其核心是求解马尔可夫决策过程中的贝尔曼最优方程。传统方法如策略迭代依赖于方程的不动点性质进行迭代求解,但在状态-动作空间较大或存在长程依赖时计算成本高。本文提出一种新方法,将策略迭代展开并截断为可学习的参数化模型BellNet,从随机值函数初始化出发训练以最小化贝尔曼误差。将MDP的转移概率矩阵视为加权有向图的邻接矩阵,借鉴图信号处理思想,将BellNet解释并紧凑重参数化为一系列非线性图滤波器的级联。这一新视角实现了策略与值迭代的统一、简洁且可迁移表示,并在推理阶段显式控制复杂度。初步实验在网格环境中的结果表明,BellNet可在远少于经典方法所需的迭代次数下有效逼近最优策略。
原文摘要 · Abstract (English)
Dynamic programming (DP) is a fundamental tool used across many engineering fields. The main goal of DP is to solve Bellman's optimality equations for a given Markov decision process (MDP). Standard methods like policy iteration exploit the fixed-point nature of these equations to solve them iteratively. However, these algorithms can be computationally expensive when the state-action space is large or when the problem involves long-term dependencies. Here we propose a new approach that unrolls and truncates policy iterations into a learnable parametric model dubbed BellNet, which we train to minimize the so-termed Bellman error from random value function initializations. Viewing the transition probability matrix of the MDP as the adjacency of a weighted directed graph, we draw insights from graph signal processing to interpret (and compactly re-parameterize) BellNet as a cascade of nonlinear graph filters. This fresh look facilitates a concise, transferable, and unifying representation of policy and value iteration, with an explicit handle on complexity during inference. Preliminary experiments conducted in a grid-like environment demonstrate that BellNet can effectively approximate optimal policies in a fraction of the iterations required by classical methods.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。