Dynamic Regret in Time-varying MDPs with Intermittent Information

This paper proposes a skip-update learning and planning framework for time-varying Markov decision processes under intermittent information constraints and establishes a dynamic regret bound that explicitly quantifies how performance degrades as a function of update intervals, temporal variation, and estimation uncertainty.

The Gist

Imagine you are driving a car through a city that is constantly under construction. The roads change, traffic lights shift, and new detours appear every few minutes. This is your Time-Varying World.

Now, imagine you are driving this car, but you have a very specific problem: Your GPS only updates every 10 minutes.

Between those 10-minute updates, your GPS is stuck showing you the map from 10 minutes ago. The roads might have changed, but your GPS doesn't know yet. You have to keep driving using this "stale" map until the next update arrives.

This paper is about figuring out exactly how much worse your trip will be because of these gaps in information.

The Core Problem: The "Stale Map" Dilemma

In the real world, robots, self-driving cars, or even financial trading algorithms often face this exact issue. They can't constantly scan the environment or update their brain because of limited battery, slow internet, or heavy computing loads.

So, they have to make a choice:

1. Update constantly: Expensive and slow (like trying to download a new map every second).
2. Update rarely: Fast and cheap, but you risk driving off a cliff because your map is old.

The authors ask: If we are forced to drive with an old map for long stretches, how much extra time (or "regret") will we lose compared to a driver who has a perfect, live-updating map?

The Solution: The "Skip-Update" Strategy

The authors propose a smart way to handle this. Instead of panicking every time the map is old, they use a "Skip-Update" framework.

Here is how it works, using our driving analogy:

1. The Checkpoint (Update Time): Every 10 minutes, you stop at a gas station (an "update time"). You get a fresh map, look at the current traffic, and plan your route for the next 10 minutes.
2. The Prediction: You don't just look at the current map; you also guess how much the road might change in the next 10 minutes based on how fast construction usually happens. You add a little "safety buffer" to your plan to account for potential surprises.
3. The Drive (Skip Interval): You get back on the road. For the next 10 minutes, you do not check your GPS again. You just follow the plan you made at the gas station, even if the road changes slightly.
4. The Next Checkpoint: You arrive at the next gas station, get a new map, and repeat.

The "Regret" Formula: Why It Matters

The paper's main achievement is a mathematical formula that predicts exactly how much "worse" your trip will be. They call this Dynamic Regret.

Think of Regret as the difference between:

• The Ideal Trip: A driver with a perfect, live-updating map who takes the absolute fastest route.
• Your Trip: You, driving with the "Skip-Update" strategy.

The authors found that your "Regret" (the extra time you lose) comes from two main sources:

1. The "Old Map" Error: The longer you go without an update, the more the real world drifts away from your map. If the city changes fast (high "temporal variation") and you wait a long time to update, your regret grows linearly. It's like driving further and further off course the longer you ignore the traffic report.
2. The "Mixing" Safety Net: Here is the good news. The authors found that if the city has a certain property (called "mixing"), the errors don't pile up forever.
   • Analogy: Imagine you are lost in a forest. If the trees are all identical, getting lost is terrifying. But if the forest has a strong wind that constantly mixes up the leaves and paths, eventually, you might stumble back onto a main road by accident.
   • In their math, this "mixing" means that even if you make a mistake early in your 10-minute drive, the system naturally "contracts" or corrects itself over time, preventing the error from exploding into a disaster.

The Big Takeaway

The paper proves that you don't need to update your model constantly to do well. You can skip updates and save resources, BUT there is a price to pay.

• If the world changes slowly: You can skip updates for a long time with very little penalty.
• If the world changes fast: You must update more often, or your performance will degrade significantly.
• The Sweet Spot: The formula tells you exactly how long you can wait between updates before the "cost of being wrong" outweighs the "cost of updating."

Summary in a Nutshell

This paper gives us a rulebook for how lazy we can afford to be when making decisions in a changing world. It tells us that if we update our plans occasionally (like checking a map every 10 minutes) rather than constantly, we can still do a great job, provided we account for how fast the world is changing and how much our system naturally corrects itself. It turns a scary problem ("I don't have enough data!") into a manageable math equation.

Technical Summary

1. Problem Statement

The paper addresses sequential decision-making in Time-Varying Markov Decision Processes (TVMDPs) under severe information and computational constraints.

• Environment: The system dynamics (transition kernels $P_t$) evolve over time, satisfying a bounded drift condition ($|P_{t+1} - P_t| \leq \varepsilon_t$).
• Constraints: The agent cannot observe the system state or update its model at every time step due to sensing, communication, or computational limitations.
• Intermittent Updates: The agent only receives state observations and performs model estimation/planning at a sparse set of update times ($\mathcal{T}_{upd}$).
• Skip Intervals: Between update times, the agent must act using stale information (the last observed state and the last computed policy) without new data or replanning.
• Objective: To quantify how the performance of an agent degrades as a function of the update rate and the duration of these "skip" intervals, specifically measuring Dynamic Regret against an oracle policy with full knowledge and continuous updates.

2. Methodology

The authors propose a Skip-Update Learning and Planning Framework (Algorithm 1) that operates in two distinct phases:

A. Estimation at Update Times

At each update time $\tau_k$:

1. Data Collection: The agent collects transitions $(s_{\tau_k}, a_{\tau_k}, s_{\tau_k+1})$.
2. Constrained Maximum Likelihood Estimation (MLE): The agent estimates the time-varying transition kernels by maximizing the log-likelihood of observed data subject to:
   • Probability simplex constraints.
   • Drift Constraints: The estimated kernels must satisfy the known bounded drift condition ($|\hat{P}_{\tau_k} - \hat{P}_{\tau_{k-1}}| \leq \sum \varepsilon$).
   • This results in a convex optimization problem where the solution set is a bounded polytope ($P_{D_t}$).
3. Uncertainty Quantification: The agent computes the diameter of the uncertainty set for unobserved state-action pairs to quantify estimation uncertainty ($u_t$).

B. Planning and Execution

1. Finite-Horizon Planning: At update time $\tau_k$, the agent solves a finite-horizon optimal control problem (horizon $H_k$) using the estimated model $\hat{P}_{\tau_k}$.
   • Augmented Reward: The planning objective includes a penalty term for uncertainty: $r^{(\beta)} = r + \beta \cdot u$, where $\beta$ controls the trade-off between exploration and robustness.
   • Forecasting: Since the model is held fixed during the planning horizon (consistent with the lack of updates), the agent forecasts future uncertainty by propagating the solution polytope forward under the drift model.
2. Receding-Horizon Execution (Skip-Update):
   • The agent computes a policy sequence for the horizon.
   • It executes the first policy of the sequence at the current update time.
   • Crucially, for all subsequent time steps until the next update (the "skip interval"), the agent reuses the same policy computed at $\tau_k$ without replanning or state observation. The policy is applied to the last known state (or the internal state estimate), creating a piecewise-constant control strategy.

3. Key Contributions

1. Novel Framework: Introduction of a skip-update framework that explicitly models the trade-off between limited update rates and decision-making performance in non-stationary environments.
2. Dynamic Regret Decomposition: Theoretical derivation of a dynamic regret bound that explicitly separates errors into two distinct sources:
   • Update-time errors: Arising from model estimation mismatch and finite-horizon planning truncation.
   • Skip-interval errors: Arising from acting on stale information (state mismatch) and temporal drift (time mismatch) during periods without updates.
3. Quantification of Degradation: The analysis reveals that the dominant contribution to regret during skip intervals has a linear dependence on the interval length and the rate of temporal variation.
4. Role of Mixing: The paper demonstrates that the negative impact of stale information is mitigated by the mixing-induced contraction of the transition kernels (Assumption 1), which causes errors to decay geometrically over time.

4. Main Results

The primary theoretical result is Theorem 1, which provides an upper bound on the Dynamic Regret $DR(T)$:

$$DR(T) \leq \sum_{t \in \mathcal{T}_{upd}} (\text{Update Errors}) + \sum_{t \in \mathcal{T}_{skip}} (\text{Skip Errors})$$

Key insights from the bound:

• Update Errors: Depend on the estimation error ($\hat{\varepsilon}$) and planning horizon truncation. These are attenuated by the contraction property of the system.
• Skip Errors: Depend on:
  • Temporal Drift: The cumulative difference between the true dynamics at time $t$ and the last update time $\tau_k$ ($\bar{\varepsilon}$).
  • State Mismatch: The error introduced by applying a policy derived from a stale state.
  • Interval Length: The regret accumulates linearly with the length of the skip interval before being dampened by the system's mixing rate ($\alpha$).
• Contraction Factor: The bound includes a term $\alpha^{\lfloor (T-t)/m \rfloor}$, where $\alpha < 1$ is derived from the overlap coefficient (mixing rate). This shows that while errors accumulate during skip intervals, the system's inherent stability limits their long-term impact.

5. Significance

• Bridging Theory and Practice: This work moves beyond standard stationary MDP assumptions and continuous-update models to address realistic scenarios (e.g., bandwidth-limited networks, energy-constrained robots) where continuous adaptation is impossible.
• Resource Allocation: The results provide a theoretical basis for determining optimal update frequencies. They quantify the "cost" of skipping updates, allowing system designers to balance communication/computation costs against performance degradation.
• Robustness to Drift: By incorporating drift bounds into the estimation and planning, the framework ensures robustness even when the environment changes faster than the update rate, provided the mixing condition holds.
• Foundational Insight: It establishes that in time-varying systems, performance is not just a function of model accuracy, but critically depends on the temporal alignment between information acquisition and the rate of environmental change.