Paper: arXiv 2405.13609

Abstract

Markov decision processes (MDPs) are used to model a wide variety of applications ranging from game playing over robotics to finance. Their optimal policy typically maximizes the expected sum of rewards given at each step of the decision process. However, a large class of problems does not fit straightforwardly into this framework: Non-cumulative Markov decision processes (NCMDPs), where instead of the expected sum of rewards, the expected value of an arbitrary function of the rewards is maximized. Example functions include the maximum of the rewards or their mean divided by their standard deviation. In this work, we introduce a general mapping of NCMDPs to standard MDPs. This allows all techniques developed to find optimal policies for MDPs, such as reinforcement learning or dynamic programming, to be directly applied to the larger class of NCMDPs. Focusing on reinforcement learning, we show applications in a diverse set of tasks, including classical control, portfolio optimization in finance, and discrete optimization problems. Given our approach, we can improve both final performance and training time compared to relying on standard MDPs.

Complexity vs Empirical Score

  • Math Complexity: 8.5/10
  • Empirical Rigor: 4.0/10
  • Quadrant: Lab Rats — theoretically deep, empirically untested

Why this score: The paper presents a sophisticated theoretical framework mapping NCMDPs to MDPs using auxiliary state variables and reward transformations, supported by heavy mathematical notation and proofs. While it includes numerical experiments on finance portfolio optimization and control tasks, the summary focuses on the theoretical mapping and lacks specific implementation details, backtest results, or statistical metrics needed for high empirical rigor.

Research Flowchart

  flowchart TD
  Goal["Research Goal: Solve Non-Cumulative Markov Decision Processes (NCMDPs)"] --> Methodology["Methodology: Map NCMDPs to Standard MDPs"]
  Methodology --> Inputs["Inputs: Diverse Domains<br>(Control, Finance, Optimization)"]
  Inputs --> Process["Computational Process:<br>Reinforcement Learning on Mapped MDPs"]
  Process --> Outcome1["Outcome: Improved Final Performance"]
  Process --> Outcome2["Outcome: Faster Training Time"]
  Process --> Outcome3["Outcome: Unified Framework for NCMDPs"]

Cited References (45)

  1. Deep Reinforcement Learning for Optimal Portfolio Allocation: A Comparative Study with Mean-Variance Optimization — → 2602.17098
  2. Quantum Circuit Discovery for Fault-Tolerant Logical State Preparation with Reinforcement Learning (2024) — link
  3. To the Max: Reinventing Reward in Reinforcement Learning (2024) — link
  4. Reinforcement Learning Based Quantum Circuit Optimization via ZX-Calculus (2023) — link
  5. Optimizing ZX-diagrams with deep reinforcement learning (2023) — link
  6. Cost Explosion for Efficient Reinforcement Learning Optimisation of Quantum Circuits (2023) — link
  7. Simultaneous discovery of quantum error correction codes and encoders with a noise-aware reinforcement learning agent (2023) — link
  8. Reinforcement Learning With Non-Cumulative Objective (2023) — link
and 37 more
  1. Faster sorting algorithms discovered using deep reinforcement learning (2023) — link
  2. Discovered Policy Optimisation (2022) — link
  3. Variance Reduction for Policy-Gradient Methods via Empirical Variance Minimization (2022) — link
  4. Reachability Constrained Reinforcement Learning (2022) — link
  5. Application Placement in Fog Environments using Multi-Objective Reinforcement Learning with Maximum Reward Formulation (2022) — link
  6. Safety and Liveness Guarantees through Reach-Avoid Reinforcement Learning (2021) — link
  7. Quantum circuit optimization with deep reinforcement learning (2021) — link
  8. Maximum Reward Formulation In Reinforcement Learning (2020) — link
  9. Generating Realistic Stock Market Order Streams (2020) — link
  10. Bridging Hamilton-Jacobi Safety Analysis and Reinforcement Learning (2019) — link
  11. Graph-theoretic Simplification of Quantum Circuits with the ZX-calculus (2019) — link
  12. Optimization of Molecules via Deep Reinforcement Learning (2018) — link
  13. Learning dexterous in-hand manipulation (2018) — link
  14. Proximal Policy Optimization Algorithms (2017) — link
  15. Picturing Quantum Processes: A First Course in Quantum Theory and Diagrammatic Reasoning (2017) — link
  16. Human-level control through deep reinforcement learning (2015) — link
  17. Reach-avoid problems with time-varying dynamics, targets and constraints (2014) — link
  18. Quantum error correction for quantum memories (2013) — link
  19. Decision-Theoretic Planning with non-Markovian Rewards (2011) — link
  20. Maximum reward reinforcement learning: A non-cumulative reward criterion (2006) — link
  21. Learning to trade via direct reinforcement (2001) — link
  22. Policy Gradient Methods for Reinforcement Learning with Function Approximation (1999)
  23. Performance functions and reinforcement learning for trading systems and portfolios (1998) — link
  24. Structured Solution Methods for Non-Markovian Decision Processes (1997)
  25. Rewarding Behaviors (1996)
  26. Technical Note: Q-Learning (1992) — link
  27. Stable-Baselines3: Reliable Reinforcement Learning Implementations (2021)
  28. What Matters for On-Policy Deep Actor-Critic Methods? A Large-Scale Study (2021)
  29. Planning with General Objective Functions: Going Beyond Total Rewards (2020)
  30. Antonin Raffin (2020)
  31. Reinforcement learning - an introduction, 2nd Edition (2018)
  32. MUTUAL FUND PERFORMANCE* (2007) — link
  33. Simple Statistical Gradient-Following Algorithms for Connectionist Reinforcement Learning (2004) — link
  34. Code for quantum error correction code discovery
  35. Remmy Zen. Code for logical state preparation
  36. Code for ZX-diagrams
  37. Code for classical control, portfolio optimization, and peak environment

1 of 45 cited works are in the corpus; resolved via arXiv source bundles, Semantic Scholar and OpenAlex. Corpus-wide: 2518 linked papers.