确定性拟多项式时间内的回合制随机平均收益博弈
Turn-Based Stochastic Mean-Payoff Games in Deterministic Quasipolynomial Time
OpenAI 数学仓库收录的研究手稿。展开查看英文摘要，或标记后让我进一步解释。
具体内容
稿件研究有限回合制随机平均收益博弈的算法求解。摘要表示，作者给出统一的确定性拟多项式时间算法，处理带符号整数收益与以二进制编码的有理转移概率，精确计算路径下极限平均收益期望值非负（含零值）的顶点。算法使用精确有理算术，位运算量为2^{O((log(L+2))^2)}，其中L为完整二进制输入长度。该结果的意义在于为这类随机博弈提供确定性精确算法，但手稿尚未经独立审查或同行评议。
- 针对有限回合制随机平均收益博弈，收益为带符号整数。
- 精确计算非负值顶点，包括值为零的情形。
- 算法为确定性拟多项式时间，使用精确有理算术。
AI 产生的研究手稿；收录不表示已完成独立审查或同行评议。
英文原始摘要
We give a uniform deterministic quasipolynomial-time algorithm for finite turn-based stochastic mean-payoff games with signed integer rewards and rational chance-transition probabilities encoded in binary. It computes exactly the vertices of nonnegative value, including value zero, for the expectation of the pathwise liminf mean payoff. The algorithm uses exact rational arithmetic and $`2^{O((\log(L+2))^2)}`$ bit operations, where L is the complete binary input length.
用户标记：未标记
固定编号：ff8391934dcf0679
原文来源