
| (a) L∞ error of the Bellman residual   | (b) L2 error of the Bellman residual   |             |          |     |     |
|----------------------------------------|----------------------------------------|-------------|----------|-----|-----|
| Features                               | 100                                    | 144         |          |     |     |
| OAPI                                   | 0.21 (0.23)                            | 0.13 (0.1)  |          |     |     |
| ALP                                    | 13. (13.)                              | 3.6 (4.3)   |          |     |     |
| LSPI                                   | 9. (14.)                               | 3.9 (7.7)   |          |     |     |
| API                                    | 0.46 (0.08)                            | 0.86 (1.18) | Features | 100 | 144 |
| OAPI                                   | 0.2 (0.3)                              | 0.1 (1.9)   |          |     |     |
| ALP                                    | 9.5 (18.)                              | 0.3 (0.4)   |          |     |     |
| LSPI                                   | 1.2 (1.5)                              | 0.9 (0.1)   |          |     |     |
| API                                    | 0.04 (0.01)                            | 0.08 (0.08) |          |     |     |

Table 1: Bellman residual of the final value function. The values are averages over 5 executions, with the standard deviations shown in parentheses.

solving a bilinear program are both NP-complete problems. Finally, the formulation leads to the development of OAPI, a new convergent form of API which monotonically improves the objective value function.

While we only discussed approximate solutions of the ABP, a deeper study of bilinear solvers may render optimal solution methods feasible. ABPs have a small number of essential variables (that determine the value function) and a large number of constraints, which can be leveraged by the solvers (Petrik and Zilberstein, 2007). The L∞ error bound provides good theoretical guarantees, but it may be too conservative in practice. A similar formulation based on L2 norm minimization may be more practical.

We believe that the proposed formulation will help to deepen the understanding of value function approximation and the characteristics of existing solution methods, and potentially lead to the development of more robust and widely-applicable reinforcement learning algorithms.