Performance Guarantees for Data-Driven Sequential Decision-Making
This provides theoretical guarantees for data-driven decision-making in domains like robotics and multi-agent systems, though it is incremental as it builds on existing ADP frameworks.
The paper tackles the problem of quantifying the performance gap between approximate dynamic programming (ADP) schemes and optimal solutions in sequential decision-making, showing that ADP schemes achieve objective values at least a computable fraction of the optimal value, with applications in robot path planning and sensor coverage.
The solutions to many sequential decision-making problems are characterized by dynamic programming and Bellman's principle of optimality. However, due to the inherent complexity of solving Bellman's equation exactly, there has been significant interest in developing various approximate dynamic programming (ADP) schemes to obtain near-optimal solutions. A fundamental question that arises is: how close are the objective values produced by ADP schemes relative to the true optimal objective values? In this paper, we develop a general framework that provides performance guarantees for ADP schemes in the form of ratio bounds. Specifically, we show that the objective value under an ADP scheme is at least a computable fraction of the optimal value. We further demonstrate the applicability of our theoretical framework through two applications: data-driven robot path planning and multi-agent sensor coverage.