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