提出用法向扇形几何分析非平稳强化学习,区分有代价和无代价的环境变化。
Priced Motion Through Optimal Faces: A Normal-Fan Geometry for Non-Stationary Adversarial MDPs
- 构建损失变化的法向扇形几何,以面切换定义代价
- 发现大变动可能不产生后悔,小变动却可能引发巨大损失
- 适合研究动态环境下的鲁棒决策与后悔分解
在变化的决策问题中,传统动态后悔分析常将非平稳性的代价等同于损失的移动距离。然而,损失序列可能移动很远但最优策略不变,或微小损失变化导致最优策略彻底改变。因此,损失、转移或比较路径的变化量描述了对手的运动,却不等于控制问题的代价。本文为具有固定转移的有限时域对抗性马尔可夫决策过程(MDP)发展了一种法向扇形几何:占用测度构成多面体,每个损失向量暴露该多面体的一个最优面。非平稳奖励即为在法向扇形中的路径,路径内一个锥体内的运动不改变最优面,而穿越边界则带来后悔。本文提出“面交叉价格”概念,即在新损失下仍停留在前一最优面所承担的最小后悔。任何跟踪前一最优面的算法,其动态后悔可精确分解为内在定价的面运动与面内选择误差之和。由此理论分离了有后果与无后果的非平稳性:损失变化可无限大而代价为零,相同单坐标变化可能隐藏时间跨度级的后悔差异。
原文摘要 · Abstract (English)
In a changing decision problem, standard dynamic-regret analyses have often equated the cost of non-stationarity to how far loss moves. However, it is simultaneously possible for a loss sequence to travel far and retain the same optimal policy, or for a small movement in loss to force the optimal policy to change completely. Thus, the size of the movement through loss variation, transition variation, or comparator path length describe the adversary's motion, but not the cost of that motion to the control problem. For a more faithful analytic interpretation, this paper develops a normal-fan geometry for finite-horizon adversarial MDPs with fixed transitions. Occupancy measures form a polytope, and each loss vector exposes an optimal face of that polytope. Non-stationarity in rewards is therefore a path through the normal fan, where motion inside one cone leaves the optimal face unchanged, while crossing a wall may carry regret. We pose the notion of a face-crossing price, which is the minimum regret incurred by remaining on the previous optimal face under the new loss. For any learner that tracks the previous face, dynamic regret decomposes exactly into intrinsic priced face motion plus within-face selection error. The resulting theory separates consequential from harmless non-stationarity, where loss variation can be arbitrarily large at zero price, and identical one-coordinate variation can hide horizon-scale differences in regret.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。