Reproduce “Smoothed analysis of policy iteration and value iteration for deterministic discounted and mean-payoff games played on any graph” on OpenResearch
Turn your favorite coding agents into research agents that review literature, develop hypotheses, and run experiments.
Universal app for Apple silicon and Intel. Requires macOS 11 or later.
About this paper
Bruno Loff, Mateusz Skomra
The authors extend smoothed polynomial-time policy iteration from ergodic to arbitrary graphs and give three value-iteration methods for deterministic mean-payoff games. Their combined Zwick–Paterson/Halpern method separates states of different values before recovering optimal policies. Under independent Gaussian edge-weight perturbations, it finds optimal policies with probability at least 1−ε in smoothed polynomially many iterations, not with a worst-case polynomial-time guarantee.
Summary by alphaXiv.
Tip: change arxiv.org to autoarxiv.org in any arXiv abstract link to open the paper here.