PaperlayerView exact revision on arXiv

Source-linked AI summary

A Survey of Reinforcement Learning Algorithms for Dynamically Varying Environments

Sindhu Padakandla

arXiv:2005.10619v1cs.LGcs.AIstat.ML

TL;DR

RL agents in real-world applications must adapt to environments whose dynamics change, challenging methods built on stationarity. This paper surveys algorithms, application-specific approaches, and related research for dynamically varying environments, emphasizing their merits, limitations, and future directions. It identifies practical methods for minimizing learning losses or finding effective policies, while noting unresolved scalability, explainability, and generalization issues.

  • Problem

    Real-world RL applications challenge classical methods because agents must react to changing operating conditions rather than assume stationary environment models.

  • Method

    The paper surveys and categorizes RL techniques for dynamically changing environments, reviews application-specific work, and discusses benefits, challenges, and future enhancements.

  • Results

    The survey presents representative methods for minimizing rewards lost during learning or finding policies that support efficient system operation, alongside their merits and demerits.

  • Takeaways & Limitations

    Application-specific non-stationary RL remains limited, while scalable and explainable Deep RL and mature meta-learning approaches remain open needs.

  • Takeaways & Limitations

    Biologically inspired approaches require more experimentation and theoretical justification, and existing approaches are often difficult to generalize beyond their application settings.

Abstract

from arXiv · show

Reinforcement learning (RL) algorithms find applications in inventory control, recommender systems, vehicular traffic management, cloud computing and robotics. The real-world complications of many tasks arising in these domains makes them difficult to solve with the basic assumptions underlying classical RL algorithms. RL agents in these applications often need to react and adapt to changing operating conditions. A significant part of research on single-agent RL techniques focuses on developing algorithms when the underlying assumption of stationary environment model is relaxed. This paper provides a survey of RL methods developed for handling dynamically varying environment models. The goal of methods not limited by the stationarity assumption is to help autonomous agents adapt to varying operating conditions. This is possible either by minimizing the rewards lost during learning by RL agent or by finding a suitable policy for the RL agent which leads to efficient operation of the underlying system. A representative collection of these algorithms is discussed in detail in this work along with their categorization and their relative merits and demerits. Additionally we also review works which are tailored to application domains. Finally, we discuss future enhancements for this field.

I. INTRODUCTION

Real-world RL systems must adapt when environment contexts and dynamics change over time. The paper surveys methods, applications, challenges, and related continual- and meta-learning directions for this setting.

  • Applications: In recommender systems, agent actions influence user behavior and reveal additional information as the state evolves.
  • Motivation: Changing operating conditions require autonomous agents to track environment characteristics and adapt learned actions for efficient system operation.Traffic signal control illustrates how changing inflow rates alter state-evolution distributions.
  • Environment model: An environment context consists of the state-evolution probability distribution and reward function, both of which determine RL interaction.
  • Scope: The survey discusses RL techniques for dynamically changing contexts, including their benefits, challenges, application domains, and future research directions.
  • Related work: Continual learning builds on prior data while retaining previous tasks, whereas meta-learning uses experience across tasks to learn new tasks more efficiently.

II. PRELIMINARIES

The paper frames RL through the Markov decision process, where policies choose actions from states and performance is evaluated through reward-based value criteria.

  • Markov decision processes: A Markov decision process is defined by states, actions, transition probabilities, and rewards that govern state evolution and learning.
  • Policies: A policy comprises decision rules that select actions based on the observed history, with the paper focusing on state-dependent deterministic rules.
  • Performance criteria: For finite horizons, policy quality is measured by expected total reward, and an optimal policy maximizes this value for every state.
  • Performance criteria: For infinite horizons, performance uses either discounted cumulative rewards or average reward per step.
  • Objective: The autonomous agent seeks a policy that maximizes the selected value criterion across all initial states.

D. Algorithms and their Assumptions

Classical RL convergence relies on stationary transition and reward functions, but non-stationary environments require models and policies that account for changing contexts over time.

  • Algorithms and assumptions: RL convergence assumptions include bounded rewards and stationary transition and reward functions.
  • RL algorithms: Model-based RL estimates transition and reward functions, whereas model-free RL directly learns or improves value functions without estimating them.
  • Non-stationarity: Non-stationary environments violate stationarity, motivating methods that autonomous agents can use to handle changing environment models.
  • Problem formulation: A family of MDPs models changing environments by allowing transition kernels and reward functions to vary across contexts.
  • Problem formulation: Environment changes can occur every epoch or never, representing the rapidly changing and stationary extremes of the formulation.
  • Policy search: Because a stationary policy may not remain optimal, the policy search space expands to history-dependent, randomized, time-varying policies.
  • Performance criteria: Regret emphasizes rewards collected relative to the optimal expected finite-horizon reward, while other criteria seek policies that optimize system control.

IV. BENEFITS AND CHALLENGES OF RL IN NON-STATIONARY ENVIRONMENTS

Non-stationary RL addresses changing conditions in single- and multi-agent settings, but adaptation creates challenges in sample efficiency, computation, and theoretical guarantees.

  • Benefits: Handling changing environments can benefit both single-agent and multi-agent RL scenarios.
  • Benefits: In multi-agent RL, each agent observes dynamics that change as other agents learn and explore different state-action regions.
  • Challenges: Changing environments can make learning slower when collected state-reward samples do not clearly reveal the change.
  • Challenges: Detecting changing operating conditions adds computational burden to the curse of dimensionality in large state-action spaces.
  • Challenges: Without stationarity assumptions, convergence results and performance guarantees for model-free RL are difficult to obtain.

V. CURRENT SOLUTION APPROACHES

Current solutions address non-stationary environments through finite- and infinite-horizon formulations, using regret minimization or policy-learning approaches under differing assumptions about model changes and information.

  • Finite Horizon Approaches: Finite-horizon methods study MDPs with changing transition probabilities and rewards, minimizing regret over a horizon T.Because the decision horizon is finite, the environment can change at most T−1 times, and a stationary policy need not be optimal.
  • Finite Horizon Approaches: Finite-horizon works differ in assumptions about the number and pattern of environment changes, including known changes, unrestricted changes, known contexts, and arbitrarily varying costs.They also use different time-dependent optimal-policy criteria, including average-reward, total-reward, and piecewise-stationary policies.
  • Finite Horizon Approaches: Contextual MDPs represent each context as an MDP and use CECE to cluster episodes and explore rewards according to the inferred context.The context is latent to the controller, so the method estimates context-dependent performance from partial trajectories.
  • Finite Horizon Approaches: UCRL2 and variation-aware UCRL2 estimate transitions and rewards with confidence intervals, restarting learning after changes to obtain sublinear regret bounds.Variation-aware UCRL2 additionally makes its bound depend on MDP-context variation.
  • Finite Horizon Approaches: MD2 and related online-learning methods handle varying costs or rewards using Mirror Descent, exponential weights, total-variation measures, and Follow the Leader.MD2 assumes known stationary transitions with adversarially varying costs, while the other approach derives regret bounds depending on reward-function variation.

3) Remarks: •

The surveyed finite-horizon methods have limitations involving regret interpretation, context-distance modeling, restart behavior, and scalability.

  • 3) Remarks: •: Contextual MDP derives a regret bound linear in T, while its trajectory distance considers transition distributions but not reward functions.The paper notes that reward functions are important MDP components and vary with policy.
  • 3) Remarks: •: UCRL2 and variation-aware UCRL2 can restart with large confidence sets when environments alternate between contexts, increasing regret and requiring iterations to rebuild confidence.Their estimation process loses information collected before the restart.
  • 3) Remarks: •: Model-based methods may not scale to large state-action spaces because high MDP diameter values can make regret upper bounds very high.This limitation applies to UCRL2, variation-aware UCRL2, and the cited online-learning approaches.

B. Infinite Horizon Approaches

Infinite-horizon approaches focus on learning effective policies in changing environments through hidden-mode modeling, context detection, model-free updates, online learning, and tree search.

  • B. Infinite Horizon Approaches: Hidden-mode MDPs model each mode as a stationary MDP while hiding transitions between modes from the learning agent.Modes share state and action spaces but differ in transition and reward functions.
  • B. Infinite Horizon Approaches: RLCD tracks active contexts by estimating transition and reward functions, while creating new context models online when existing predictors exceed an error threshold.This approach does not require prior knowledge of the number of contexts or their change pattern.
  • B. Infinite Horizon Approaches: When accumulated transition or reward changes remain bounded and insignificant, value functions across contexts remain sufficiently close.This framework indicates conditions under which pursuing non-stationary RL algorithms is worthwhile.
  • B. Infinite Horizon Approaches: Change-detection methods identify active contexts using error scores or CUSUM statistics, with TTS switching from exploratory to context-specific policies after threshold crossings.TTS uses KL-divergence-based exploration before switching to a policy associated with the detected context.
  • B. Infinite Horizon Approaches: Context QL detects multivariate changes in state-reward samples with ODCP and maintains separate Q-value tables for different contexts.Q-FPL instead partitions iterations into intervals, resets Q-values between intervals, and selects actions with Follow the Perturbed Leader.
  • B. Infinite Horizon Approaches: RATS assumes slowly evolving environments with current-context information and uses tree search to choose actions from the current environmental snapshot.It models these settings as non-stationary MDPs that generalize ordinary MDPs.

2) Remarks:

The infinite-horizon methods trade adaptability, policy retention, model requirements, and computational or memory demands against practical scalability.

  • 2) Remarks:: HM-MDP algorithms are computationally intensive and are described as impractical for direct application.The paper identifies deep RL as a possible route toward greater computational feasibility.
  • 2) Remarks:: RLCD avoids prior knowledge of context counts and change patterns but is memory intensive because it stores estimates for every detected context.Each context retains transition-probability and reward estimates.
  • 2) Remarks:: TTS requires model information, prior knowledge of the change pattern, and threshold choices that affect its change-detection strategy.The paper reports practical concerns with threshold selection and the method’s applicability.
  • 2) Remarks:: When P^πi(st+1|st,πi(at))=1, the CUSUM statistic can grow uncontrollably and cross every fixed threshold, causing detection failure in that case.The paper states that practical use may then require threshold knowledge tied to the changepoint.
  • 2) Remarks:: Q-learning and asynchronous value iteration adapt to new contexts, but updating shared values causes previously learned policies to be lost.The methods therefore lack memory-retaining capability.
  • 2) Remarks:: Context QL retains policies for observed contexts and improves sample efficiency, but storing Q-values for every context makes it non-scalable.The benefit is explicitly coupled to increased memory requirements.
  • 2) Remarks:: RATS approximates a worst-case NSMDP but is not scalable to larger problems because of the planning algorithms required for tree search.The survey summarizes methods by decision horizon, model-information requirements, mathematical tools, and policy retention.

VI. RELATED AREAS

The survey relates dynamically varying-environment RL to continual learning and biologically inspired approaches that retain or reuse policies across tasks.

  • Continual Learning: CHILD combines temporal transition hierarchies with Q-learning to predict event contexts and produce Q values for action selection.Its experiments on grid worlds examine acquiring new skills and retaining learned policies.
  • Continual Learning: Synaptic-plasticity methods model neural connections as capable of storing strengths for multiple tasks.The approach uses a biologically plausible synaptic model for RL function approximators.
  • Continual Learning: Table I compares ODCP and ECP by the changepoints detected when model information is known.The supplied caption identifies the comparison metric but provides no table values.
  • Continual Learning: Policy consolidation records behavioral policies at multiple timescales and feeds them back into the policy network.The approach targets policy-level forgetting using cascaded hidden networks.

1) Remarks:

The survey compares continual-learning and meta-learning approaches for non-stationary RL, highlighting retained policies, reuse of experience, and unresolved theoretical and computational issues.

  • Remarks: Algorithms that restart fixed confidence schedules can suffer catastrophic forgetting because new training erases knowledge from older data.The comparison contrasts these methods with model-specific Q-value storage.
  • Remarks: Separate Q values for each environment model let non-stationary Q-learning retain policies across models.The method has empirical support but raises computational-efficiency issues and requires adaptation to function approximation.
  • Remarks: CHILD may support dynamically varying environments when combined with change detection because it maintains separate data structures for models.The survey relates it to RLCD and Context QL.
  • Remarks: Meta-learning reuses experience and skills from earlier tasks to learn new skills, requiring a definition of useful meta-data.The surveyed prior work primarily targets deep reinforcement learning architectures.
  • Remarks: MAML learns an internal representation suited to varied tasks and adapts task-specific parameters from trajectories using gradient-based losses.A non-stationary extension models tasks as a Markov chain.
  • Remarks: MAESN uses related-task experience to initialize new-task policies and learn directed exploration strategies.This differs from approaches that fine-tune only the policy.

1) Remarks:

Application-specific RL work addresses changing conditions in transportation, cyber-physical systems, wireless scheduling, and related domains, but scalability and generality remain concerns.

  • Remarks: Prior application RL often assumes stationary dynamics, while non-stationary algorithms remain limited despite progress in deep RL and computing infrastructure.The survey identifies scalability to large state-action MDPs as an ongoing issue.
  • Remarks: The survey covers transportation, cyber-physical systems, digital marketing, inventory pricing, recommender systems, and robotics.Most surveyed algorithms are customized to their respective applications.
  • Transportation and Traffic Systems: Soilse combines reward feedback with traffic-pattern change signals from moving-average filters and CUSUM-based detection.The controller targets fluctuating vehicular traffic patterns.
  • Transportation and Traffic Systems: Urban aerial transport must balance information gathering against privacy because human concentration varies with weather, time, and events.The cited setting concerns unmanned aerial systems operating over densely populated areas.
  • Cyber-Physical Systems: CPS security work uses modified Shiryaev-Roberts-Pollak procedures to detect operational changes associated with DDoS and malware attacks.CPS combine physical processes with networking and computation in feedback loops.
  • Cyber-Physical Systems: A wireless scheduling formulation assumes non-stationary channel dynamics and seeks to minimize stale information measured by Age of Information.The associated infinite-state average-reward MDP is infeasible to optimize directly, motivating a heuristic policy.

C. Digital Marketing and Inventory Pricing

The surveyed application studies use RL for changing demand, model retraining, sparse-reward robotics, and adaptive locomotion, while many methods remain application-specific.

  • Digital Marketing and Inventory Pricing: Inventory pricing seeks to sell a fixed inventory before a deadline and maximize revenue under unknown, time-varying demand.The cited method uses Q-learning with eligibility traces to learn a pricing policy.
  • Digital Marketing and Inventory Pricing: Off-policy evaluation for digital marketing models user information as state, promotions as actions, and orders per visit as reward.The proposed method is shown to reduce policy-evaluation errors.
  • Digital Marketing and Inventory Pricing: Recommender-system model management uses an MDP-based RL agent to decide when and how to retrain models after concept drift.Retraining too quickly may waste computation through underfitting, whereas delaying it may sharply reduce prediction performance.
  • Robotics: Sparse-reward robotic manipulation is difficult because reinforcement may be small and arrive only at task completion.The cited work studies robotic arms manipulating objects on fixed table positions under changing surface conditions.
  • Robotics: Hexapod locomotion adapts gait by selecting among deep-RL expert policies conditioned on state history and terrain difficulty distributions.The terrain is represented using N discrete distributions.
  • Remarks: Most surveyed application methods are hard to extend beyond their original settings, although several works are described as adaptable with modifications.Examples include function approximation for [29], model-free extensions for, and actor-critic or policy-gradient extensions for.

VIII. FUTURE DIRECTIONS

The survey identifies practical and methodological gaps in non-stationary reinforcement learning and outlines directions for improving scalability, detection, safety, data efficiency, and adaptation.

  • Algorithmic limitations: Regret-based methods suit multi-armed bandit settings but do not directly establish good policies for control-focused reinforcement learning.Their exploration ideas can still guide initial action exploration in reinforcement learning approaches.
  • Scalability: Most model-based and model-free approaches are not scalable because they require substantial memory for model estimates or computation for detecting changes and building decision trees.These resource requirements limit applicability to practical systems that operate at larger problem sizes.
  • Detection and memory: Future work can incorporate quickest change detection, anomaly detection, and memory retention in deep neural networks to address changing dynamics and catastrophic forgetting.These statistical and architectural tools are identified as potential remedies for non-stationary reinforcement learning challenges.
  • Adaptation: Non-stationary reinforcement learning needs algorithms that detect changes in environment dynamics and adapt seamlessly to changing operating conditions.Such algorithms could also be extended to continual reinforcement learning settings.
  • Deep reinforcement learning: Deep reinforcement learning approaches that scale to non-stationary environments remain scarce, while existing meta-learning work is preliminary, insufficiently analyzed, and not explainable.This leaves scalability, evaluation, utilization, and explainability as open research needs.
  • Application constraints: Robotics may provide only one sample trajectory per environment model, requiring data-efficient learning, while abnormal conditions require maintaining nominal safe behavior during adaptation.These application constraints motivate sample efficiency and safety-aware non-stationary reinforcement learning.
Loading 2005.10619v1…