Source-linked AI summary
Reinforcement Learning in Non-Stationary Environments
Sindhu Padakandla, Prabuchandran K. J, Shalabh Bhatnagar
TL;DR
The paper addresses reinforcement learning when rewards and transition dynamics change over time, a setting in which stationary-environment methods can be suboptimal. It combines experience-based change detection with Context Q-learning to adapt policies across contexts, and reports promising performance across dynamic environments and applications. The approach remains bounded by its assumptions about context-change patterns and future extension to large continuous state spaces.
Problem
Method
Context Q-learning adapts Q-learning with experience-tuple change detection to learn, store, and reuse policies for changing environment contexts.
Source: §1.1 · p. 3, §5.1 · p. 7Results
Context Q-learning performs well in varying operating conditions and gives better return than classical Q-learning and other non-stationary algorithms such as RUQL and RLCD.
Source: §6.4 · p. 18, §7 · p. 19Takeaways & Limitations
The method provides a model-free approach for adapting RL policies across changing environments while retaining information from previously observed contexts.
Source: §7 · pp. 18–19, §6.4 · p. 18The method assumes that context-change patterns are known, and extending it to large continuous state spaces remains future work.
Source: §7 · p. 19
Abstract
from arXiv · showhide
Reinforcement learning (RL) methods learn optimal decisions in the presence of a stationary environment. However, the stationary assumption on the environment is very restrictive. In many real world problems like traffic signal control, robotic applications, one often encounters situations with non-stationary environments and in these scenarios, RL methods yield sub-optimal decisions. In this paper, we thus consider the problem of developing RL methods that obtain optimal decisions in a non-stationary environment. The goal of this problem is to maximize the long-term discounted reward achieved when the underlying model of the environment changes over time. To achieve this, we first adapt a change point algorithm to detect change in the statistics of the environment and then develop an RL algorithm that maximizes the long-run reward accrued. We illustrate that our change point method detects change in the model of the environment effectively and thus facilitates the RL algorithm in maximizing the long-run reward. We further validate the effectiveness of the proposed solution on non-stationary random Markov decision processes, a sensor energy management problem and a traffic signal control problem.
1 Introduction
The paper develops model-free reinforcement learning for environments whose rewards and transition dynamics change over time. Context Q-learning detects changes from experience data, preserves policies across contexts, and is evaluated across standard and real-world applications.
1 Introduction
- The target setting includes unknown changes in rewards and transition probabilities, requiring policies to adapt for long-term cumulative reward.Examples include traffic patterns that vary between peak and off-peak periods and robotic motion that changes across terrains or weather conditions.Source: §1 · pp. 2–3
1.1 Our Contributions –
- Context Q-learning is a continual model-free RL method for dynamically changing environments that learns and stores policies for different contexts.It adapts Q-learning and uses detected changes to estimate a new policy or improve a previously learned one, avoiding catastrophic forgetting.Source: §1.1 · p. 3
- The method detects context changes from state and reward samples rather than requiring model information, making it applicable to model-free RL.Its change detector uses collected experience samples, unlike prior approaches that require transition or reward models.Source: §1.1 · p. 3
- Experiments evaluate Context Q-learning on standard problems, traffic signal control, and sensor networks using reward, detection delay, precision, and recall.The results compare it with recent relevant methods in dynamic environments.Source: §1.1 · p. 3
1.2 Organization of the Paper
- The paper is organized around prior work, MDP foundations, problem formulation, the proposed RL method, numerical experiments, and conclusions.The numerical section analyzes results across different application domains.Source: §1.2 · pp. 3–4
2 Related Work
Prior approaches address changing MDPs through hidden-mode models, concept-drift detection, regret minimization, or model-based change detection, but important practical limitations remain. The paper motivates a model-free method that retains information across recurring contexts without relying on costly model estimation or poorly specified thresholds.
2 Related Work
- Hidden-mode MDP methods require model information and can be computationally intensive, limiting practical implementation.Their contexts share state and action spaces but may differ in transition probabilities or rewards.Source: §2 · p. 4
- RLCD detects contexts using estimated models and heuristic predictors but is memory intensive and difficult to interpret when identifying new contexts.It stores and updates transition and reward estimates for all detected contexts.Source: §2 · p. 4
- Existing regret-oriented methods restart model estimation after environmental changes, discarding information when contexts recur, whereas the proposed objective retains policies for observed environments.This distinction matters in alternating patterns such as A-B-A-B, where previously learned context information can be reused.Source: §2 · p. 4
- Model-based switching methods can detect changes faster but assume complete context models and depend on threshold choices that are not specified by the method.The two-threshold strategy trades a slight reward loss for faster detection, while delayed detection can reduce performance.Source: §2 · pp. 4–5
- Classical Q-learning and RUQL update one shared set of values and lack mechanisms to monitor model changes, so they relearn after a change without retaining the prior policy.RUQL improves learning dynamics in simulations but remains limited to one environment model at a time.Source: §2 · p. 5
- Concept-drift research is established outside RL, but RL environment drift has received limited attention and existing Markov-chain methods mainly detect transition-probability changes.The paper positions its problem as broader because environment changes can affect rewards and transitions.Source: §2 · p. 5
3 Preliminaries
The preliminaries define MDPs, policies, discounted value, and the stationarity assumption underlying classical RL. Because non-stationary environments violate that assumption, standard model-free RL is not sufficient for learning optimal policies in the paper’s setting.
3 Preliminaries
- An MDP consists of states, actions, transition probabilities, and rewards, with transitions and rewards defining the environment model.The agent selects actions and receives the resulting next state and reward or cost.Source: §3 · p. 5
- A stationary deterministic Markovian policy applies the same state-to-action decision rule at every epoch, and its value is expected total discounted reward.The discount factor satisfies 0 ≤ γ < 1.Source: §3 · p. 5
- Classical MDP optimization seeks a stationary policy π* that maximizes the value function over stationary deterministic Markovian policies.Under the stated assumptions, an optimal policy of this form exists.Source: §3 · p. 6
- Stationary transition and reward functions are an explicit assumption for standard dynamic programming and model-free RL guarantees.The assumption requires P and R not to vary over time.Source: §3 · p. 6
- When stationarity fails, classical RL cannot directly learn optimal policies for the changing environment scenario considered by the paper.The paper therefore proceeds to formulate non-stationary environments and develop an adaptive RL algorithm.Source: §3 · p. 6
4 Problem Formulation
The paper formulates non-stationarity as switching among a finite family of MDP models at unknown changepoints. It seeks a policy maximizing long-run discounted reward despite unavailable model information and the resulting need to learn both policies and changes from samples.
4 Problem Formulation
- The environment is modeled as a finite family of MDPs sharing state and action spaces but having context-specific transition kernels and reward functions.The active model changes at an increasing sequence of random changepoints.Source: §4 · p. 6
- At each changepoint, the active environment model changes, switching the transition and reward functions governing subsequent interactions from those associated with one indexed MDP model to another.Source: §4 · p. 6
- The agent may use randomized history-dependent decision rules that map observed histories to action distributions, while state-only rules are Markovian.Deterministic Markovian rules are the degenerate-distribution special case.Source: §4 · p. 6
- The objective is to learn a policy maximizing the long-run expected discounted reward for all initial histories.This objective is posed over the sequence of decision rules used during interaction.Source: §4 · p. 6
- Without stationarity and model information, a stationary deterministic policy may not be optimal, and designing an approximately optimal policy from state and reward samples is difficult.The formulation also leaves open which policy should be followed during learning.Source: §4 · pp. 6–7
- The proposed solutions primarily target model-free RL, while the same framework can also support settings where model information is available.With known models, the agent can compute each context’s optimal policy and only needs to learn when the context changes.Source: §4 · p. 7
5 Our Approach
The approach detects changes in non-stationary MDPs from experience tuples and adapts learning and policies across environment contexts. It combines ODCP change detection, exploration strategies, piecewise-stationary control, and Context Q-learning while retaining knowledge of previously observed models.
5.1 Experience Tuples / 5.2 Change Detection using Experience Tuples
- Experience tuples are state-reward-state triples whose changing distribution is analyzed online with an adapted ODCP changepoint detector.ODCP uses compositional-data transformations and Dirichlet likelihood testing; its sample requirements depend on the state, action, and reward spaces.Source: §5.1 · p. 7, §5.2 · pp. 7–8
5.2 Change Detection using Experience Tuples
- The detector is applied under fast-mixing Markovian dynamics, where stationary randomized policies support identically distributed experience tuples despite temporal dependence.This adaptation addresses ODCP’s i.i.d. requirement through a steady-state justification for the Markov reward process.Source: §5.2 · pp. 7–8
5.3 Sampling Mechanism for Collecting Experience Tuples
- Exploration policies balance change detection with control by selecting non-optimal actions occasionally through ε-policy, ε-greedy, or UCB mechanisms.The ε-policy uses the optimal action with probability 1−ε and a random action with probability ε; model-free learning uses Q-learning with ε-greedy or UCB exploration.Source: §5.3 · pp. 8–9
5.4 Leveraging Knowledge of Context Information
- With known context-change patterns, the agent switches among context-specific stationary policies after detected changepoints, producing a computable piecewise-stationary policy.This avoids searching the infeasible space of general non-stationary, non-Markovian policies.Source: §5.4 · p. 9
5.5 Context Q-learning
- Context Q-learning detects environment changes from experience tuples, updates the relevant context-specific Q-values, and preserves previously learned policies to avoid catastrophic forgetting.The method uses ODCP to identify changes, then updates a new or previously observed model rather than estimating transition and reward functions anew.Source: §5.5 · p. 9
- Context Q-learning takes a known model-change pattern but unknown model parameters, maintains Q-values for all contexts, and increments its active-context counter when ODCP detects a change.The algorithm gathers experience using ε-greedy or UCB exploration, updates the active context’s Q-values, and analyzes samples online or in batches.Source: §5.5 · pp. 9–10
5.6 Performance Evaluation and Policies
- Evaluation uses cumulative rewards for model-free settings rather than regret, because regret requires the optimal policy and model information unavailable to model-free RL.When model information is known, the paper also reports results using regret.Source: §5.6 · pp. 10–11
- The method restricts learning to piecewise-stationary policies, switching after detected changes and reusing additional samples when an environment has been observed before.This restricted policy class is intended to make adaptation computationally tractable in dynamic environments.Source: §5.6 · p. 11
6 Experimental Results
Experiments across random MDPs, sensor energy management, and traffic control show that Context QL detects environment changes and preserves context-specific policies, improving performance in non-stationary settings.
6.1.1 Single Changepoint Detection
- ODCP and ECP detect changes from experience tuples, with ODCP showing better mean performance and lower changepoint variability than ECP.The comparison uses mean, median, and standard deviation over 20 sample trajectories.Source: §6.1.1 · p. 12, Table 1 · p. 12, Table 2 · p. 12
6.1.2 Multiple Changepoints Detection
- The method’s mean detected changepoint locations are 520, 1059, and 1510, while ECP identifies only the first changepoint with mean 855 and fails to detect the second and third.Source: §6.1.2 · p. 15
6.2 Energy Management in a Single Sensor Node with Finite Buffer
- In energy management, Context QL obtains lower long-run discounted cost than QL and RUQL after the energy-harvesting rate changes.The experiment changes the environment once at iteration 2000 during 4000 learning iterations.Source: §6.2 · p. 16, Table 9 · p. 16
6.1.1 Single Changepoint Detection
- Context QL avoids the reward loss caused by QL and RUQL updating one shared value structure across changing contexts.Context QL stores separate Q-values and updates the structure associated with the detected environment.Source: §6.1.1 · pp. 14–15, Table 6 · p. 14, §6.2 · p. 16
6.3 Traffic Signal Control
- Traffic experiments model four incoming lanes with aggregated congestion states and show that changing vehicle inflows changes environment dynamics evaluated through long-run discounted cost.QL and Context QL are trained for 10^6 simulation seconds, with input volumes changed halfway through.Source: §6.3 · p. 17, Table 10 · p. 17
6.1.1 Single Changepoint Detection
- Context QL remains robust as state-action spaces grow, while NP-CDM and two-threshold switching degrade because their prefixed thresholds are not broadly transferable.NP-CDM degrades gradually, whereas the two-threshold strategy shows a drastic decrease for larger spaces.Source: §6.1.1 · p. 14, Table 5 · p. 14, §6.4 · p. 18
6.4 Summary of Results
- The method’s practical scope assumes that context-change patterns are known and that operating conditions remain stable long enough to collect sufficient samples between changes.The paper identifies these assumptions as important for traffic control and sensor energy-management applications.Source: §6.4 · p. 18
7 Conclusions
The paper develops Context QL, a model-free RL method that combines Q-learning with change detection to learn policies for changing environment models. Experiments show promising performance in varying conditions, while larger continuous spaces and unknown context-change sequences remain future extensions.
7 Conclusions
- Context QL combines Q-learning with change detection on experience tuples to learn policies for changing environment models.The method detects model changes and uses them with Q-learning to determine when to estimate a new policy or improve a previously learned one.Source: §7 · p. 18
- Context QL performs well in varying operating conditions and gives better return than classical QL and other non-stationary algorithms such as RUQL and RLCD.The experiments also evaluate its precision and recall for change-point detection.Source: §7 · p. 19
- Future work must address change detection in large continuous state spaces and settings where the sequence of context changes is unknown.The paper identifies these extensions as relevant to robotics and intelligent transportation systems.Source: §7 · p. 19