提出可学习率的不动点迭代法，用于高维定量系统求解。
Computing Fixpoints of Learned Functions: Chaotic Iteration and Simple Stochastic Games
- 改进曼迭代法，允许学习率趋于零或不收敛
- 支持混沌迭代，仅更新部分变量，适合高维问题
- 直接应用于简单随机博弈的期望收益计算
在具有定量语义的系统中，求解非负实数上高维函数的（最小）不动点问题频繁出现。本文关注函数无法精确已知，只能通过近似获取的情况。首先，我们推广了近期提出的阻尼曼迭代方法，放宽了参数序列的约束，使学习率可趋于零或不收敛。这一灵活性对实现混沌迭代至关重要——每步仅更新部分分量，从而应对高维挑战。同时，允许学习率趋于零，也降低了对函数近似收敛速度的要求，提升方法适应性。此外，我们证明该方法可直接用于计算多种概率模型中的期望收益，包括此前文献未覆盖的简单随机博弈。
原文摘要 · Abstract (English)
The problem of determining the (least) fixpoint of (higher-dimensional) functions over the non-negative reals frequently occurs when dealing with systems endowed with a quantitative semantics. We focus on the situation in which the functions of interest are not known precisely but can only be approximated. As a first contribution we generalize an iteration scheme called dampened Mann iteration, recently introduced in the literature. The improved scheme relaxes previous constraints on parameter sequences, allowing learning rates to converge to zero or not converge at all. While seemingly minor, this flexibility is essential to enable the implementation of chaotic iterations, where only a subset of components is updated in each step, allowing to tackle higher-dimensional problems. Additionally, by allowing learning rates to converge to zero, we can relax conditions on the convergence speed of function approximations, making the method more adaptable to various scenarios. We also show that dampened Mann iteration applies immediately to compute the expected payoff in various probabilistic models, including simple stochastic games, not covered by previous work.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。