R. Sebastian, M. Weise, et al.
ECPPM 2022
Value function approximation methods have been successfully used in many applications, but the prevailing techniques often lack useful a priori error bounds. We propose a new approximate bilinear programming formulation of value function approximation, which employs global optimization. The formulation provides strong a priori guarantees on both robust and expected policy loss by minimizing specific norms of the Bellman residual. Solving a bilinear program optimally is NP-hard, but this worst-case complexity is unavoidable because the Bellman-residual minimization itself is NP-hard. We describe and analyze the formulation as well as a simple approximate algorithm for solving bilinear programs. The analysis shows that this algorithm offers a convergent generalization of approximate policy iteration. We also briefly analyze the behavior of bilinear programming algorithms under incomplete samples. Finally, we demonstrate that the proposed approach can consistently minimize the Bellman residual on simple benchmark problems. © 2011 Marek Petrik and Shlomo Zilberstein.
R. Sebastian, M. Weise, et al.
ECPPM 2022
Zhikun Yuen, Paula Branco, et al.
DSAA 2023
Ran Iwamoto, Kyoko Ohara
ICLC 2023
Jehanzeb Mirza, Leonid Karlinsky, et al.
NeurIPS 2023