提出弱时序耦合近似,突破高维决策问题的计算瓶颈。
Weakly Time-Coupled Approximation of Markov Decision Processes
- 设计弱时序耦合架构,消除跨阶段依赖对时间跨度的敏感性
- 在相同时间内可处理更多样本或基函数,上界更紧
- 适用于期权定价与生产优化等高维动态决策场景
具有高维外生不确定性与内生状态的有限时域马尔可夫决策过程(MDP)广泛存在于运筹与金融领域,如百慕大期权与实物期权的估值与行权问题,但其计算复杂度随规划周期增长而急剧上升。现有方法中,最小二乘蒙特卡洛(LSM)通过逆向递归回归拟合权重,避免联合优化但误差累积;近似线性规划(ALP)与路径优化(PO)虽联合拟合权重并提供上界,却因时序耦合导致复杂度随周期增长。本文指出该耦合是近似结构所致,提出弱时序耦合近似(WTCA),使跨阶段依赖独立于规划周期。对于固定基函数集,WTCA上界介于ALP与PO之间,并随基族扩展收敛至最优策略值。将并行确定性块坐标下降扩展至随机MDP设置,利用弱时序耦合实现与周期无关的计算复杂度。在相同时间预算下,求解WTCA可容纳更多外生样本或基函数,尽管在固定条件下上界略逊于PO,但整体更优。在百慕大期权与乙醇生产实例中,所有测试案例下WTCA均优于PO与LSM,长周期下接近最优策略。
原文摘要 · Abstract (English)
Finite-horizon Markov decision processes (MDPs) with high-dimensional exogenous uncertainty and endogenous states arise in operations and finance, including the valuation and exercise of Bermudan and real options, but face a scalability barrier as computational complexity grows with the horizon. A common approximation represents the value function using basis functions, but methods for fitting weights treat cross-stage optimization differently. Least squares Monte Carlo (LSM) fits weights via backward recursion and regression, avoiding joint optimization but accumulating error over the horizon. Approximate linear programming (ALP) and pathwise optimization (PO) jointly fit weights to produce upper bounds, but temporal coupling causes computational complexity to grow with the horizon. We show this coupling is an artifact of the approximation architecture, and develop a weakly time-coupled approximation (WTCA) where cross-stage dependence is independent of horizon. For any fixed basis function set, the WTCA upper bound is tighter than that of ALP and looser than that of PO, and converges to the optimal policy value as the basis family expands. We extend parallel deterministic block coordinate descent to the stochastic MDP setting exploiting weak temporal coupling. Applied to WTCA, weak coupling yields computational complexity independent of the horizon. Within equal time budget, solving WTCA accommodates more exogenous samples or basis functions than PO, yielding tighter bounds despite PO being tighter for fixed samples and basis functions. On Bermudan option and ethanol production instances, WTCA produces tighter upper bounds than PO and LSM in every instance tested, with near-optimal policies at longer horizons.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。