Preface

Summary

Ergodic is a term appropriated from physics that derives from the Greek words έργον and οόος meaning “work” and “path”. In the context of controlled Markov processes it refers to the problem of minimizing a time averaged penalty, or cost, over an infinite time horizon. It is of interest in situations when transients are fast and therefore relatively unimportant, and one is essentially comparing various possible equilibrium behaviors. One typical situation is in communication networks, where continuous time and space models arise as scaled limits of the underlying discrete state and/or time phenomena.

Ergodic cost differs from the simpler “integral” costs such as finite horizon or infinite horizon discounted costs in several crucial ways. Most importantly, one is looking at a cost averaged over infinite time, whence any finite initial segment is irrelevant as it does not affect the cost. This counterintuitive situation is also the reason for the fundamental difficulty in handling this problem analytically – one cannot use for this problem the naive dynamic programming heuristic because it is perforce based on splitting the time horizon into an initial segment and the rest. One is thus obliged to devise altogether different techniques to handle the ergodic cost. One of them, the more familiar one, is to treat it as a limiting case of the infinite horizon discounted cost control problem as the discount factor tends to zero. This “vanishing discount” approach leads to the correct dynamic programming, or “Hamilton–Jacobi–Bellman” (HJB) equation for the problem, allowing one to characterize optimal control policies at least in the “nicer” situations when convenient technical hypotheses hold.