2026-05-17T01:53:18Zhttps://keep.lib.asu.edu/oai/request

oai:keep.lib.asu.edu:node-2012302025-05-05T15:53:02Zoai_pmh:alloai_pmh:repo_items

201230 https://hdl.handle.net/2286/R.2.N.201230 http://rightsstatements.org/vocab/InC/1.0/ All Rights Reserved 2025 66 pages Masters Thesis Academic theses en Clark, Ethan Zhang, Yu Srivastava, Siddharth Gopalan, Nakul Arizona State University Partial requirement for: M.S., Arizona State University, 2025 Field of study: Computer Science Reinforcement learning (RL) is a powerful framework designed for optimizing sequential decision-making processes. However, this sequential nature implicitly assumes order-dependence of actions, making traditional RL methods inefficient for problems where action ordering does not affect outcomes. This research identifies and formalizes the Commutative Markov Decision Process (MDP), a distinct class of reinforcement learning problems where final states and rewards depend only on which actions are taken, not their sequence. In these problems, traditional RL methods inefficiently treat each possible ordering of the same actions as entirely different trajectories despite leading to identical outcomes. To efficiently solve Commutative MDPs, this research introduces Commutative RL—a novel approach that exploits the order-invariance property through algorithmic modifications to Q-learning. Three distinct implementations are developed and evaluated: Super Action, Combined Reward, and Hash Map approaches. Each implementation enforces equivalence between permuted action sequences while preserving the theoretical guarantees of traditional RL. By recognizing that different orderings of the same actions yield equivalent outcomes, these algorithms enable faster convergence to optimal policies through elimination of redundant exploration. The effectiveness of these implementations is evaluated across two domains of increasing complexity. The component selection task provides a controlled environment with mathematically verifiable optimal solutions where Commutative RL demonstrates significant advantages in convergence speed. The second domain introduces Environment Reconfiguration (ER)—a novel meta-optimization problem where "instrumental" actions modify the environment's structure and dynamics. This city planning application demonstrates how ER problems can be reduced to Commutative MDPs, enabling efficient optimization of urban infrastructure through strategic bridge placement despite stochastic outcomes. In domains exhibiting the necessary order-invariant properties, the experimental results show that Commutative RL implementations converge to optimal policies substantially faster than traditional Q-learning approaches. This research establishes a new direction in reinforcement learning by identifying and addressing a specific class of problems with unique structural properties. By formalizing Commutative MDPs and developing initial algorithmic approaches that exploit order-invariance, this work lays theoretical foundations for a promising research area. The experimental results demonstrate the potential for significant sample efficiency improvements in domains where these properties naturally occur, such as resource allocation, inventory management, and infrastructure planning. Artificial Intelligence Computer Science Artificial Intelligence Deep learning Markov Decision Processes Reinforcement Learning Reinforcement Learning for Commutative Markov Decision Processes