Non-stationary and Varying-discounting Markov Decision Processes for Reinforcement Learning

AI summary

Overview

Research area: Reinforcement learning theory; Markov Decision Processes (MDPs); non-stationary sequential decision-making.

Technical level: Advanced. The paper is primarily a theoretical treatment with formal assumptions, lemmas, theorems, corollaries, and convergence proofs, supported by a gridworld experiment.

Scope: The paper introduces the Non-stationary and Varying-discounting Markov Decision Process (NVMDP) framework, develops its theoretical foundations, adapts dynamic programming and Q-learning to it, extends policy gradient and TRPO results, and tests it in a non-stationary gridworld.

What This Paper Is About

Most reinforcement learning algorithms are designed for stationary MDPs, where the environment's transition–reward distribution does not change over time and a single fixed discount rate is used. These assumptions break down in non-stationary environments and in finite-horizon episodic tasks, where an optimal policy need not be time-consistent. The paper's goal is to define a more general MDP framework in which dynamics change over time and discount rates may vary with both time and individual transitions — including rates above 1 — while still supporting valid value functions, optimality conditions, learning algorithms, and convergence guarantees.

Key Contributions

1. A new framework. The authors introduce NVMDPs, which extend Non-stationary MDPs (NSMDPs, the term adopted from Lecarpentier et al.) with discount rates that depend on time and on the transition, written as γ_{t+1}(s_t, a_t, s_{t+1}). Assumptions 2.1 through 2.4 make the framework well-defined and permit some discount rates to exceed 1. The paper formalizes the dynamic programming recursion (Lemma 2.1) and a value-consistency guarantee (Lemma 2.3).

2. Matrix formulations. The paper extends the matrix representation of classic MDPs by Agarwal et al. to NVMDPs, making V_t^π and Q_t^π explicitly time-dependent and introducing matrices Π_t^π and U for policy operations, plus J_t, K_t, and L_t for discounting.

3. Optimality, policy improvement, and special cases. The authors prove the existence of a deterministic optimal policy in every NVMDP (Theorem 2.4), extend the Bellman optimality equation (Theorem 2.6), adapt reward shaping from Ng et al. (Corollary 2.7), and adapt the policy improvement theorem (Theorem 2.8). They also show that classic MDPs are special cases of NVMDPs for the purpose of finding an optimal policy, and that finite-horizon MDPs are subsumed, with the discount rate requirement relaxed to mere non-negativity.

4. Algorithms and convergence. The paper discusses time treatment in tabular solutions, extends policy evaluation and value iteration to NVMDPs with convergence guarantees, adapts the generalized Q-learning framework of Lan et al. (building on extensions of Tsitsiklis) with convergence guaranteed by Theorem 3.3, and extends the policy gradient theorem (Theorem 4.1), the performance difference lemma (Lemma 4.2), and the TRPO policy improvement bound (Theorem 4.4), each proved in both scalar and matrix form. It also introduces "Tricky Gridworld," a non-stationary gridworld environment.

Main Findings

• Discounting can be generalized beyond a fixed rate below 1. Classic MDPs and NSMDPs require a fixed γ < 1 for value convergence. NVMDPs allow some discount rates greater than 1, provided Assumption 2.3 (a bounded accumulated discounting sum Γ_B) holds. Under Assumptions 2.2 and 2.3, all state- and action-values are bounded in absolute value by Γ_B·R_B = V_B.

• Value consistency holds under Assumption 2.4. If two policies are identical from time step n onward, their state-values coincide for all t ≥ n and their action-values coincide for all t ≥ n−1 (Lemma 2.3). This is the paper's replacement for the time-consistency assumption used in stationary MDPs.

• Deterministic optimal policies exist. For Π = {(π_0, π_1, π_2, …) | π_i: S → Dist(A), ∀ i ≥ 0}, there exists a deterministic policy π* attaining the optimal state- and action-values for all t ≥ 0 (Theorem 2.4), and V_t*(s) = max_a Q_t*(s,a) (Corollary 2.5).

• The discount rate moves inside the expectation in the Bellman optimality equation. Because the rate depends on time and transition, the NVMDP Bellman optimality equation is Q_t^π(s,a) = r̄_t(s,a) + E_{s'∼p_t(·|s,a)}[γ_{t+1}(s,a,s') max_{a'} Q_{t+1}^π(s',a')] (Theorem 2.6). Policies satisfying it are optimal, and action-values of optimal policies satisfy it.

• Reward shaping preserves optimal policies. Adding a differential term of the form γ_{t+1}(s,a,s')Φ_{t+1}(s') − Φ_t(s) to the reward, bounded in absolute value, leaves the set of optimal policies unchanged (Corollary 2.7).

• Policy improvement applies with time-indexed comparisons. Under a stated condition for t < n, Theorem 2.8 shows state-values are equal for t ≥ n and non-decreasing for t ≤ n−1, and action-values are equal for t ≥ n−1 and non-decreasing for t < n−1.

• Empirical demonstration in Tricky Gridworld. In a non-stationary gridworld, NVMDP-based algorithms successfully recover optimal trajectories under multiple reward and discounting schemes, whereas original Q-learning fails. The paper states that different discount rate settings shape the optimal trajectories learned. The truncated content does not report specific numerical results, table values, or environment sizes for this experiment.

Methodology in Plain English

The researchers begin by taking an existing formulation for non-stationary MDPs, in which the environment's rules change over time but the discount rate stays fixed, and loosen the discounting part. Instead of one number γ, they let the discount applied between two time steps depend on the time step and on the specific state, action, and next state. They then state four assumptions that keep the math well-behaved: the discount starts at 1 and never goes negative, rewards are bounded, the infinite sum of accumulated discount factors is bounded, and the product of the largest successive discount factors shrinks to zero. With these in place, they rebuild the standard machinery of MDP theory — definitions of value and advantage, recursive relationships, matrix notation, existence of optimal deterministic policies, Bellman optimality, reward shaping, and policy improvement — adapting each result to the time-varying, transition-dependent setting and giving proofs. They then translate two tabular solution methods (policy evaluation and value iteration) and a generalized Q-learning algorithm into this framework and prove convergence. For settings where a table of values is impractical, they extend the policy gradient theorem, the performance difference lemma, and the TRPO improvement bound, providing both scalar and matrix proofs. Finally, they construct a non-stationary gridworld called Tricky Gridworld and compare NVMDP-based algorithms against original Q-learning.

Why This Matters

Impact on research. The work provides a formal foundation for two things the RL literature usually treats separately: non-stationarity and flexible discounting. It shows that classic MDPs and finite-horizon MDPs are special cases, which means the framework is a strict generalization rather than an alternative. The paper also argues that discount rates can act as a policy-shaping mechanism without changing the state space, action space, or reward structure — a new lever for influencing what an optimal policy looks like.

Real-world applications (as motivated or implied by the paper):

• Finance and asset pricing, where time-dependent spot rates are used instead of a single yield to discount future cash flows, as the paper notes via Lyuu's work on bond pricing.
• Economies or accounts facing unusual interest rate regimes, illustrated by Japan's negative interest rates over eight years starting February 2016, which the authors interpret as γ > 1 for some time steps.
• Portfolio optimization, where the authors previously showed PPO — a variant of TRPO — works with time-varying discount rates.
• Environments whose dynamics change over time, such as the non-stationary gridworld used in the experiments, standing in for settings where a stationary assumption fails.

Industry relevance. The paper emphasizes that NVMDP-based methods require only minor algorithmic modifications, which lowers the practical barrier to adopting them in existing RL pipelines. Because discount rates can be tuned to shape optimal behavior without redesigning rewards, practitioners gain an additional control knob for steering learned policies.

Future Directions

• Scaling beyond tabular and gridworld settings. The theoretical results cover finite state and action spaces, and the empirical demonstration is a single non-stationary gridworld. Extending the empirical validation to larger environments and high-dimensional function approximation remains open.
• Deep RL implementations. The paper extends the policy gradient theorem and the TRPO improvement bound, but the truncated content does not report deep RL experiments. Building and benchmarking such implementations would test the matrix-form results in practice.
• How to choose varying discount rates. The paper demonstrates that discount rate settings shape optimal trajectories, but does not report a method for selecting them for a given task. A principled design procedure is a natural next question.
• Relationship to existing non-stationary methods. The paper positions NVMDPs against NSMDPs, implicit time-augmentation approaches such as Pardo et al., and risk-averse planning by Lecarpentier et al. Systematic comparisons of predictive accuracy and computational cost across these approaches are not reported.

Target Audience

This paper is best suited to reinforcement learning researchers and graduate students with a background in MDP theory, dynamic programming, and policy gradient methods, particularly those working on non-stationary environments, finite-horizon episodic tasks, or discounting design. It is also relevant to quantitatively trained practitioners in finance and operations research — the authors are in the Department of Integrated Systems Engineering at the Ohio State University — who want to connect discounting practice from finance to RL value functions. Beginners will likely find the assumptions, matrix notation, and proofs demanding.

Authors’ abstract

Algorithms developed under stationary Markov Decision Processes (MDPs) often face challenges in non-stationary environments, and infinite-horizon formulations may not directly apply to finite-horizon tasks. To address these limitations, we introduce the Non-stationary and Varying-discounting MDP (NVMDP) framework, which naturally accommodates non-stationarity and allows discount rates to vary with time and transitions. Infinite-horizon, stationary MDPs emerge as special…