Online Abstract Dynamic Programming with Contractive Models

Xiuxian Li, Lihua XiearXiv 2021 · DOI · arXiv

Abstract

This paper addresses abstract dynamic programming (DP) in the online scenario, where the abstract DP mapping is time-varying rather than static. In this context, optimal costs and policies at different time instants are generally not the same, and the problem amounts to tracking time-varying optimal costs and policies—a challenge central to many practical applications. This research develops and provides theoretical analysis for several online algorithms, including approximate online value iteration (VI), online policy iteration (PI), approximate online PI, online optimistic PI, and asynchronous online PI and VI algorithms. The study proves that tracking error bounds for all algorithms depend critically on the largest difference between any two consecutive abstract mappings.

Introduction

In classical Dynamic Programming (DP), we typically assume a "stationary" environment. We rely on Bellman’s equation to find a single optimal policy that remains valid indefinitely. However, real-world applications are rarely static. Consider a Unmanned Aerial Vehicle (UAV) tracking a moving target: the cost function, such as the distance to the target, changes at every time step.

If the environment changes faster than a solution can be computed, the "optimal" policy derived from the previous state may already be obsolete. This paper addresses the Online Abstract DP problem: how to track time-varying optimal costs and policies when the underlying mathematical mapping (the Bellman operator) is updated at every step. The authors focus on "contractive models," the most well-behaved class of DP problems (such as discounted Markov Decision Processes), where mathematical operators naturally reduce the distance between functions over time.

Algorithmic Framework

The paper provides a rigorous theoretical analysis of several algorithms adapted for the online setting, moving beyond the static assumptions of traditional reinforcement learning and control theory.

1. Online Value Iteration (VI)

This is an iterative approach where the cost function is updated based on the current environment mapping. The authors analyze an "approximate" version that accounts for limited computational power or noise at each step, ensuring the algorithm remains robust even when calculations are not perfectly precise.

2. Online Policy Iteration (PI)

Policy Iteration is a two-step process of evaluating a policy and then improving it. The paper explores three variants:

  • Exact Online PI: Full evaluation at each step.
  • Approximate Online PI: Evaluation with potential errors.
  • Optimistic Online PI: A more efficient version where the algorithm does not wait for the evaluation step to fully converge before moving to policy improvement. This is particularly useful in high-speed online environments.

3. Asynchronous Online Algorithms

Perhaps the most practical contribution is the analysis of asynchronous updates. This handles scenarios where multiple processors work on different parts of the state space simultaneously, potentially with communication delays and varying update frequencies. This is essential for distributed systems and large-scale robotics.

Key Insights and Theoretical Results

The "Drift" Bound

The most critical insight of the research is that in a time-varying environment, the tracking error does not necessarily go to zero as it would in a static environment. Instead, it converges to a "neighborhood" of the optimal solution. The size of this neighborhood is determined by the maximum difference between consecutive mappings ($H_k$ and $H_{k+1}$). If the environment changes slowly (low drift), the tracking remains highly accurate.

Exponential Convergence

Despite the challenge of a moving target, the authors prove that these algorithms converge to the error neighborhood at an exponential rate. This suggests that the algorithms are highly responsive to changes, provided the underlying model remains contractive.

Efficiency vs. Accuracy

The paper demonstrates that Optimistic PI can be more computationally efficient in online scenarios. While it may carry a slightly larger error bound due to the accumulation of differences between mappings, the reduction in computational overhead often makes it the superior choice for real-time applications.

Robustness to Asynchronicity

The authors prove that even with communication delays ($T_d$) and processors updating at different rates ($T_a$), the system remains stable. The tracking error remains bounded as long as every part of the state space is updated "often enough," quantifying the "speed limits" for hardware and communication infrastructure in autonomous systems.

Conceptual Examples

While the paper is primarily theoretical, it illustrates these results through two conceptual frameworks:

  1. Online Optimal Control: A deterministic nonlinear system with time-varying costs, representing physical systems like robotics.
  2. Online Finite-State Discounted MDPs: A classic reinforcement learning setup where transition probabilities and costs change over time, representing economic or network models.

Limitations and Future Directions

The current findings are limited to contractive models. While these cover many common problems (like discounted MDPs), they do not yet extend to "semicontractive" or "noncontractive" models, where the mathematical properties are more volatile. Additionally, the algorithms assume that the decision-maker knows the current mapping ($H_k$) at time $k$. In "bandit" style problems where the mapping itself must be estimated, further complexities arise.

Future research is expected to investigate the online scenario for these more difficult semicontractive and noncontractive models to broaden the applicability of online dynamic programming.

Summary updated

Abstract

This paper addresses the abstract dynamic programming (DP) in the online scenario, where the abstract DP mapping is time-varying, instead of static. In this case, optimal costs and policies at different time instants are not the same in general, and the problem amounts to tracking time-varying optimal costs and policies, which is of interest to many practical problems. It is thus necessary to analyze the performance of classical value iteration (VI) and policy iteration (PI) algorithms in the online case. In doing so, this paper develops and provides the theoretical analysis for several online algorithms, including approximate online VI, online PI, approximate online PI, online optimistic PI, approximate online optimistic PI, and asynchronous online PI and VI algorithms. It is proved that the tracking error bounds for all algorithms critically depend upon the largest difference between any two consecutive abstract mappings. Meanwhile, examples are presented to illustrate the theoretical results.
BibTeX
@misc{li2021online,
  author = {Xiuxian Li and Lihua Xie},
  title = {{Online Abstract Dynamic Programming with Contractive Models}},
  year = {2021},
  eprint = {2107.01383},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2107.01383},
}
Figure