Chapter 1: The Prerequisite Bridge

Chapter 0 ended with a three-dimensional ODE on the state space in which every quantity was computable. The system had a compact set that trajectories could not leave (or entered in finite time), and we found at least three equilibria: two on the boundary of the actor box and one in the interior.

Several questions were visible but not answered.

• Does the system generate a well-defined forward-time evolution for every initial condition in , and is that evolution continuous in its initial data?
• What does it mean for the absorbing set to “attract” trajectories, and is there a smaller set that captures the ultimate behavior?
• Are the three equilibria all there is, or can the system exhibit more complicated recurrence — periodic orbits, heteroclinic connections (orbits that leave one equilibrium and converge to another), or chaotic invariant sets?
• If we change the model parameters, do the equilibria survive in some sense, or does the long-time picture change discontinuously?

In reinforcement learning, the practical question is whether the algorithm converges, where it converges to, and whether the answer is robust to perturbations, so we want a language that addresses all three at once rather than treating each equilibrium as a separate convergence problem. The dynamical-systems toolkit provides exactly such a language.

This chapter introduces that language.

Chapter 0 (Section 0.2) explained why the object we study is a deterministic ODE rather than the stochastic algorithm itself — the ODE is the mean-field limit obtained by averaging out the noise in individual updates — and deferred to this chapter the question of what that ODE does and does not tell us about the algorithm. We take up that question now. Classical stochastic approximation theory (Robbins-Monro, Ljung, Kushner-Yin, Borkar, Benaim) guarantees that the stochastic iterates track the mean ODE over finite time horizons; the ODE’s attractors constrain the algorithm’s limit sets, while fluctuations, convergence times, and basin selection require the full stochastic theory.

Beyond the finite-horizon tracking statement, the stochastic-approximation transfer has a sharper asymptotic form: in the language of Benaim (1999, Theorem 5.7), the limit set of the stochastic iterates is an internally chain-transitive set of the ODE flow. In particular, if the ODE has a compact global attractor , then every stochastic limit set must lie inside , which means the iterates eventually remain in every neighborhood of . The richer the attractor structure we can establish for the ODE, the more precise the conclusions we can draw about the algorithm.

This is why the present chapter introduces the dynamical-systems vocabulary for the ODE: semiflows, absorbing sets, omega-limit sets, and global attractors. These are the objects that the transfer theorems translate into statements about the stochastic algorithm. Our project proves that the mean dynamics has a well-behaved attractor structure; the stochastic-approximation theory then carries that structure back to the algorithm.

For the RL reader. If you are used to asking “does the algorithm converge?”, the mean-dynamics viewpoint reformulates the question as: “what does the flow of the mean ODE do in the long run?” That reformulation has real content, since the mean ODE may have multiple equilibria, its trajectories may spiral toward a periodic orbit, or the long-time behavior may depend on initial conditions. The concept of a global attractor captures all of these possibilities in a single compact invariant set.

For the dynamical-systems reader. If you are used to studying ODEs given by an explicit vector field, the novelty here is what the state coordinates are. The actor and critic variables are standard finite-dimensional parameters, but the state distribution is itself evolving, and its evolution is driven by a generator that depends on the other coordinates, from which it follows that the correct state space for the mean dynamics is the enlarged state space that includes the distribution.

The first definition makes precise what it means for a system to run forward in time from any initial condition. We package the solution map into a semiflow, rather than just noting that the ODE has solutions, since the semigroup property and joint continuity are the two hypotheses the attractor existence theorem (Theorem 1.6 below) needs; without them, we cannot pass from “the system has an absorbing set” to “the system has a global attractor.”

Definition 1.1 (Semiflow). Let be a metric space. A continuous semiflow on is a family of maps , indexed by , satisfying:

1. .
2. for all (the semigroup property).
3. The map is continuous from to .

The semigroup property says that running for time and then for time is the same as running for time in one step, and together with continuity it ensures that the system has a well-defined deterministic forward evolution.

We call this a semiflow rather than a flow because we only require , so the system runs forward in time but not necessarily backward. This is natural for dissipative systems, where backward-time solutions may fail to exist or may leave the domain.

Verification in the Chapter 0 example. In Chapter 0, the state space is and the system is the three-dimensional ODE

If the vector field on the right-hand side is locally Lipschitz on and if trajectories starting in remain in for all forward time, then the standard ODE existence and uniqueness theorem (Picard-Lindelof) gives a unique maximal solution for each initial condition, from which it follows that these solutions assemble into a continuous semiflow on . We observed in Chapter 0 that the actor box is forward invariant (the damping function vanishes at ), that the simplex is forward invariant, and that the critic equation is globally well-posed, so the system does generate a semiflow on .

We did not check the Lipschitz condition or the continuity in initial data explicitly; those are the tasks of Chapters 2—3, where we prove them for the general model.

A set is forward invariant if the flow cannot escape from it.

Definition 1.2 (Forward Invariance). A subset is forward invariant under a semiflow if

This is the semiflow language for what we already saw in Chapter 0: the actor box was forward invariant because , the simplex was forward invariant because the distribution equation preserves nonnegativity and total mass, and the critic equation stayed bounded because the drift was coercive.

Forward invariance is useful because it confines trajectories to a known region, but by itself it says nothing about what happens within that region in the long run: a trajectory might settle down to an equilibrium, oscillate periodically, or wander densely. To say something about the long-time picture, we need the next two concepts.

An absorbing set strengthens forward invariance from “trajectories cannot leave” to “every trajectory must eventually arrive and then stay”: a single compact region that swallows every bounded set of initial conditions in finite time.

Definition 1.3 (Absorbing Set). A compact, forward-invariant set is called an absorbing set for the semiflow if every bounded subset eventually enters : there exists such that

We have bundled three properties into this definition: compactness, forward invariance, and the absorption property. Some references define “absorbing” only by the absorption property and treat compactness and forward invariance as separate conditions; we use the combined definition because in these notes the absorbing set will always be compact and forward invariant, and the combined set of hypotheses is what the attractor theorem requires.

The absorbing set is the first quantitative sign that the system is dissipative. In classical mechanics, “dissipative” means the system loses energy; here the analogue is concrete: the critic’s coercivity drives toward a bounded ball, and the actor’s damping function pins inside its box. These are the mechanisms that pull every bounded set of initial conditions into a common compact region — and once there, it stays.

In the recommendation system of Chapter 0, dissipativity means that no matter how the platform starts — even with an absurdly large critic estimate or an extreme initial policy — the system’s own feedback eventually confines it to a reasonable operating region.

Verification in the Chapter 0 example. The set played this role. The actor box and the simplex are immediately confining. For the critic, coercivity of the drift gave an exponential decay estimate: any initial condition with satisfies after a finite time that depends only on and the coercivity constant (Exercise 0.8 asked you to estimate this entry time explicitly), and once the critic stays bounded because the critic ball is forward invariant.

The triple product is therefore compact (a closed bounded subset of ), forward invariant (each factor is), and absorbing (the actor and distribution factors are immediately absorbing, while the critic factor absorbs in finite time), so these three properties together make an absorbing set.

An absorbing set captures where trajectories end up eventually, but it is usually much larger than it needs to be, since it captures the transient bound rather than the permanent behavior. The next concept extracts the tightest possible description of the long-time behavior.

Definition 1.4 (Omega-Limit Set). Let be a nonempty set. A point belongs to the omega-limit set if and only if there exist sequences and such that . In other words, is the set of all possible accumulation points of the flow starting from as time goes to infinity.

The equivalent set-theoretic formula is The inner union collects all states visited after time ; the closure captures limits; the intersection over all keeps only points that are approached arbitrarily late.

Key properties. When is bounded and the semiflow has a compact absorbing set, compactness of that absorbing set together with continuity of yield three properties of that we will reference by name in later chapters:

• is nonempty and compact.
• is invariant: for all . (Note the equality, not just inclusion — the flow maps onto itself.)
• attracts : as , where is the one-sided Hausdorff distance, — the worst-case distance from a point of to the set ; note it is not symmetric in its arguments.

If, in addition, is connected, then is connected as well; this extra hypothesis will matter in Chapter 5, where the starting set is the connected absorber .

These properties are standard results in the theory of dissipative dynamical systems. The nonemptiness, compactness, invariance, and attraction statements follow from compactness of the absorbing set and continuity of the semiflow, while connectedness requires the extra assumption that the starting set is connected. We will prove the needed version for our specific system in Chapters 4—5; for now we record them as the properties that make omega-limit sets useful.

Verification in the Chapter 0 example. We did not compute explicitly in Chapter 0, but we can already say something about it. The absorbing set is compact and forward invariant, so , and since the omega-limit set is invariant it must be a union of complete orbits. We found three equilibria in Chapter 0; if the system has no periodic orbits or more complicated recurrence, then might consist of precisely those three equilibria together with any heteroclinic orbits connecting them, but whether this is the case requires more analysis than we have done so far.

The omega-limit set of the absorbing set is the right candidate for the smallest set that captures all long-time behavior.

Definition 1.5 (Global Attractor). A compact set is a global attractor for the semiflow if:

1. is invariant: for all .
2. attracts every bounded subset of : for every bounded ,

If a global attractor exists, it is unique.

Theorem 1.6 (Existence of the Global Attractor). Let be a continuous semiflow on a metric space . Suppose there exists a compact absorbing set . Then the omega-limit set is the unique compact global attractor.

This is the central structural result we will use. The proof strategy proceeds in three connected steps. First, compactness of and continuity of together imply that is nonempty, compact, and invariant. Then the absorbing property promotes this into global attraction: any bounded eventually enters , and attracts by construction, so attracts . Finally, uniqueness follows by double inclusion–if also satisfies the definition, then because is bounded and invariant while attracts it, and because is invariant while attracts it. We will carry out this proof in full generality in Chapters 4—5 for the finite-dimensional case relevant to our model.

In infinite-dimensional settings, the attractor existence theorem needs an extra hypothesis — asymptotic compactness — to extract convergent subsequences, but in our finite-dimensional setting this is automatic: once trajectories enter a compact absorbing set, sequential compactness is free. We mention this only because the concept appears in general references; for finite-state models it is never a separate concern.

In the recommendation system of Chapter 0, the global attractor is the set of all long-run operating regimes the platform can reach. In that example the evidence so far points to the specialist equilibrium, the anti-specialist equilibrium, the interior moderate equilibrium, and connecting trajectories between them; the numerics of Chapter 0 support this picture, though we have not ruled out other recurrence. Knowing the attractor means knowing every possible steady state of the recommendation policy at once — the complete menu, rather than one equilibrium at a time.

For the RL reader. The global attractor is a compact invariant set that every trajectory in approaches, and it is the tightest possible answer to the question “where does the algorithm end up?” If the attractor is a single point, the system converges to a unique equilibrium; if it is larger, the system may exhibit multiple equilibria, periodic orbits, or more complex recurrence, but all of that behavior is confined to a single compact set.

This is stronger than proving convergence to a particular equilibrium, since it captures all possible long-time behaviors simultaneously. It also behaves well under the timescale limit that Chapter 7 studies. There the distribution coordinate is sped up by a factor (the population mixes fast relative to the policy update), and as the exact attractor of the full three-variable system is shown to converge to the lifted attractor of the simpler two-variable invariant-law reduction. The mechanism is not that the absorbing set moves– does not depend on at all–but a finite-time tracking estimate: trajectories of the exact and reduced flows stay close on every bounded time interval (a Gronwall comparison), and closeness of trajectories forces closeness of attractors. This is the upper-semicontinuity statement that Chapter 7 makes precise; individual equilibria may appear or disappear in the limit, but the exact attractor cannot develop pieces far from the reduced one. The statement is deliberately one-sided: upper semicontinuity does not rule out the attractor shrinking abruptly.

For the dynamical-systems reader. The global attractor is a standard object from the theory of dissipative dynamical systems; the unusual feature here is the structure of the vector field on the distribution coordinate. In a standard ODE textbook, the vector field is a fixed map , whereas in our setting the dynamics of are driven by a generator that is parametrized by the actor coordinate (Chapter 2 constructs this generator family explicitly from the base transition kernel and the policy), so the vector field for is not a single object but a family of generators indexed by ; the closure map makes this family-of-generators structure tractable by collapsing it to a Lipschitz target. The attractor lives in the enlarged space because excising would amount to choosing one slice from this family and losing the actor’s effect on the distribution dynamics.

We now arrive at the central conceptual point of these notes. Return to the recommendation platform of Chapter 0: the platform adjusts its policy , updates its reward estimate , and the user population shifts in response. These three feedback loops are not separable — the population responds to the policy, and the policy’s gradient depends on the population. Any analysis that fixes one while studying the others misses the coupling that drives the system’s actual behavior.

In many treatments of RL convergence, the analysis proceeds in two steps: first assume the distribution has converged (or treat it as a fixed parameter), then study the actor or critic update. This is the two-timescale informal argument: the distribution is “fast” and the parameters are “slow,” so on the slow timescale the distribution has already reached its stationary value.

This argument is fine as an informal guide, but it skips a key step. The distribution is not an external input; it is a state variable driven by the same system, so the correct ODE for the mean dynamics has the distribution as one of its coordinates, and the vector field for the distribution depends on the actor parameter.

The resulting coupling is invisible if you project the system onto the actor-critic coordinates alone, since the actor drift depends on the occupancy and hence on the distribution , while the distribution dynamics depend on because the policy determines which state transitions occur.

Closure failure. If we try to write a self-contained ODE for alone, we need to express as a function of ; but on the exact coupled flow, depends on the entire history of , not just its current value, from which it follows that the system is not closed.

The remedy is to enlarge the state space to , where is the actor parameter space, is the critic space, and is the simplex of state distributions. On this enlarged space, the coupled system has three components:

• : actor drift depending on , , and .
• : critic drift depending on , , and .
• .

This system is closed, since the right-hand side depends only on the current state . This is what makes it a genuine autonomous dynamical system, and therefore the subject of attractor theory.

Verification in the Chapter 0 example. In Chapter 0, the state space was with coordinates , and the asymmetric variant of the example exhibits the coupling explicitly: the actor drift there is and the critic drift is , so both contain . Dropping from the state space would leave the actor drift as a function of , , and an unspecified time-dependent quantity — exactly the closure failure described above. The symmetric variant gives the simpler formula , with no dependence at all: there the subsystem genuinely closes on its own, and is merely slaved to . That decoupling is a special-case artifact of the antisymmetric features combined with symmetric rewards (Chapter 0, Section 0.15), not a license to drop the distribution in general. The asymmetric variant restores the generic situation, and the general theory (Chapters 2—5) treats the coupled system without relying on either symmetry.

Chapter 0 sidestepped the coupling between the distribution and the exact chain dynamics by using a prescribed closure map . Instead of evolving by the exact generator dynamics of the controlled chain, the distribution equation was replaced by a relaxation toward the prescribed target: .

This is a modeling choice rather than an approximation error. In Chapters 2—5 we take as given data and study the resulting autonomous system on the full state space . The occupancy that enters the actor and critic drifts is still the product of the dynamic and the policy ; what changes is how evolves, not how it is used. In effect, the prescribed closure determines the target that relaxes toward, replacing the exact chain dynamics with a simpler relaxation law.

Why do this? Because it separates two problems:

1. Does the system with a prescribed Lipschitz closure have a well-behaved global attractor? This is a self-contained ODE question about dissipative dynamics.
2. Can the prescribed closure be identified with the frozen invariant-law map? More concretely: can be identified with ? This requires analyzing the controlled Markov chain independently.

Separating these problems keeps the argument modular: Chapters 2—5 prove attractor existence for any Lipschitz closure map, Chapter 6 identifies with the invariant-law map under a mixing condition, and Chapter 7 studies what happens as the timescale separation parameter .

Verification in the Chapter 0 example. The closure map was , which is Lipschitz with constant in the -norm on (each component moves by at most , and the two components contribute equally). The distribution equation was , a relaxation toward the prescribed target. The full state space was , and the actor, critic, and distribution equations were all needed to close the system.

We can now state precisely what the remaining chapters will prove.

Chapters 2—5 (The Stationary Finite-Dimensional Theory).

Given:

• a finite state space with states,
• an action space with actions,
• a -dimensional actor parameter ,
• an -dimensional critic parameter ,
• a softmax policy ,
• a uniformly coercive linear critic equation,
• a Lipschitz closure map ,
• a boundary-damped actor drift,

we will prove:

1. The vector field is locally Lipschitz on , and the system generates a continuous semiflow on . (Well-posedness.)
2. The actor box is forward invariant. The simplex is forward invariant. The critic admits a uniform absorbing ball. Therefore the set is a compact absorbing set. (A priori estimates.)
3. The omega-limit set is the unique compact global attractor. (Attractor existence.)

This is the attractor theorem of the companion research article (Prytula, “Global attractors and fast-slow reduction for finite-state actor-critic mean dynamics”), which we refer to throughout these notes as the short note; there it is Theorem 2.

Chapter 6 (The Bridge Theorem).

Under a uniform exponential mixing condition on the frozen generators (the adjoint of the chain generator , acting on distributions; Chapter 2 defines it precisely), we will prove that:

4. For each , there exists a unique invariant law , and the map is Lipschitz.

This is the invariant-law proposition of the short note (its Proposition 5). Since the invariant-law map is Lipschitz, it satisfies the requirements of the closure map , so the bridge theorem provides a concrete, model-based choice for .

Chapter 7 (Fast-Slow Reduction). Under a pathwise contraction hypothesis on the fast state dynamics, Chapter 7 establishes a finite-time tracking estimate (controlled by the timescale ratio and the contraction rate) and the upper semicontinuity of the family of attractors as . Detailed statements are reserved for Chapter 7; here it suffices to record that the attractor theorem and the invariant-law proposition above feed directly into a quantitative reduction theorem.

For reference, here is the dictionary that this chapter has built.

• Forward evolution. Informally: “Run the system from this initial condition.” Formally: a continuous semiflow .
• Can’t escape. Informally: “Trajectories stay in this set.” Formally: forward invariance, .
• Eventual confinement. Informally: “Everything eventually enters the same compact region.” Formally: an absorbing set, meaning bounded sets enter in finite time.
• Ultimate behavior. Informally: “Where does the system go as time tends to infinity?” Formally: the omega-limit set .
• Global summary. Informally: “The tightest description of all long-time behavior.” Formally: the global attractor .
• Closed system. Informally: “The right-hand side depends only on the current state.” Formally: an autonomous ODE on the enlarged state space .
• Prescribed closure. Informally: “Set the distribution target as a function of the actor parameter.” Formally: a Lipschitz map .

Exercise 1.1 (Semigroup property in the Chapter 0 example). The Chapter 0 system is an autonomous ODE with a locally Lipschitz right-hand side on a forward-invariant domain. Using the uniqueness part of Picard-Lindelof, verify that the solution map satisfies for all . Identify the step where uniqueness is needed. (Hint: consider the two solutions and , and check that they satisfy the same ODE with the same initial condition at .)

Exercise 1.2 (Omega-limit set of a single trajectory). Consider the one-dimensional ODE on . First check that is forward invariant by evaluating the sign of the vector field at . Compute the equilibria. For each initial condition , determine . What is ? Is it the same as the global attractor?

Exercise 1.3 (The absorbing set is not the attractor). In the Chapter 0 example, the absorbing set was . Explain why the global attractor must be strictly smaller than . (Hint: consider the fate of an initial condition with and argue that after some time, the trajectory is in a strictly smaller critic ball.)

Exercise 1.4 (Closure failure without the distribution). Write the Chapter 0 asymmetric-variant actor equation (Section 0.15, with ), with , and suppose you try to eliminate by setting it to the constant . Compare the equilibria of the resulting two-dimensional system with the equilibria of the full three-dimensional system. What goes wrong? Explain why nothing would change in the symmetric variant , and why this is consistent with Section 1.8.

Exercise 1.5 (Forward invariance from the vector field). Let and let be locally Lipschitz (so solutions of are unique) with and . Prove that is forward invariant for by using the intermediate value theorem and uniqueness. Generalize: for locally Lipschitz , if and whenever , show that is forward invariant. Connect this to the damping function in the Chapter 0 actor equation.

Exercise 1.6 (Uniqueness of the global attractor). Suppose and are both global attractors for the same semiflow. Show that . (Hint: is bounded and invariant, so it is attracted to . But invariance means for all , so the set distance cannot shrink unless the sets already agree.)

Exercise 1.7 (Why not just study equilibria?). Construct a two-dimensional autonomous ODE on a bounded forward-invariant set that has a compact absorbing set but no stable equilibrium. (Hint: consider the standard example of a limit cycle — for instance, the polar-coordinate system , — and check that the global attractor is the closed unit disk: the limit cycle together with the unstable equilibrium at the origin and the spiral orbits connecting them, and in particular not a single point. The unit circle is the omega-limit set of every individual trajectory starting away from the origin, but it does not attract bounded sets containing the origin.)

Exercise 1.8 (The invariant-law map is not always well-defined). Consider a two-state Markov chain with generator where for and . Compute the invariant law for . What happens at ? Explain informally why the chain cannot converge to a unique invariant law at — this is the failure of the uniform exponential mixing condition that Chapter 6 will define precisely — and why this matters for the bridge theorem of Chapter 6.