Dynamic programming and heuristic search are at the core of state-of-the-art solvers for sequential decision-making problems. In partially observable or collaborative settings (\eg, POMDPs and Dec-POMDPs), this requires introducing an appropriate statistic that induces a fully observable problem as well as bounding (convex) approximators of the optimal value function. This approach has succeeded in some subclasses of 2-player zero-sum partially observable stochastic games (zs-POSGs) as well, but failed in the general case despite known concavity and convexity properties, which only led to heuristic algorithms with poor convergence guarantees. We overcome this issue, leveraging on these properties to derive bounding approximators and efficient update and selection operators, before deriving a prototypical solver inspired by HSVI that provably converges to an $\epsilon$-optimal solution in finite time, and which we empirically evaluate. This opens the door to a novel family of promising approaches complementing those relying on linear programming or iterative methods.

翻译：动态编程和超速搜索是连续决策问题最先进的解决方案的核心。 在部分可见或协作的环境下( 如, POMDPs 和 Dec- POMDPs), 这需要引入适当的统计数据, 从而引发完全可见的问题, 以及最佳价值功能的捆绑( convex) 。 这种方法在一些小类中取得了成功, 包括2Player零和部分可见的随机游戏( zs- POSGs), 但一般情况下却失败了, 尽管已知的混和性特性, 只导致超速算法, 且没有很好的趋同保证。 我们克服了这一问题, 利用这些特性来获得匹配器和高效更新与选择操作器, 在产生由 HSVI 启发的半典型的解答器之前, 这在有限的时间里可以与 $\ perslon$- 最优的解决方案相匹配, 并且我们从经验上加以评估。 这打开了一个充满希望的方法的大门。