Efficient reinforcement learning with transition-dependent LMDPs and entropy regularization

Abstract

Reinforcement Learning provides a robust framework for sequential decisionmaking problems, where an agent learns to interact with an environment to maximize long-term reward. While traditional methods involving dynamic programming face performance challenges in large state spaces, the emergence of linearlysolvable Markov Decision Processes (LMDPs) offers a computationally efficient alternative by reformulating the control problem so that the Bellman equation becomes linear. This work explores a novel formulation of LMDPs in which the reward is defined as transition-dependent rather than the conventional statedependent form. This representation is more intuitive for humans who wish to define control problems similarly to how they are specified in the standard nonlinear MDPframework, whileretaining the computational advantages of the linear formulation. Building upon this foundation, we adapt Todorov’s embedding method to transform standard MDPs into this transition-dependent LMDP framework. We also establish a formal equivalence between the transition-dependent formulation and the conventional state-dependent LMDP, demonstrating that both approaches lead to the same optimal control strategies through well-defined transformations. To ensure a fair and consistent comparison between standard MDPs and their linearly solvable version, we integrate entropy regularization into the MDP framework and subsequently extend Todorov’s embedding to accommodate these entropy-regularized MDPs.L’Aprenentatge per Reforc¸ (RL) proporciona un marc teòric i pràctic robust per a problemes de decisió seqüencial, on un agent aprèn a interactuar amb l’entorn per matximitzar la recompensa a llarg termini. Mentre que els mètodes tradicionals que involucren programació dinàmica s’enfronten a reptes de rendiment en espais d’estat grans, l’aparició de Processos de Decisió de Markov amb resolució lineal (LMDPs) ofereixen una alternativa computacionalment eficient mitjançant la reformulació del problema de control de manera que l’equació de Bellman esdevé lineal. Aquest treball explora una nova formulació d’LMDPs en la qual la recompensa es defineix en funció de la transició d’un estat a un altre, en lloc de la forma convencional on la recompensa depèn només de l’estat. Aquesta representació es més intuïtiva per a les persones que volen definir problemes de control de manera similar a com s’especifiquen en el marc MDP no lineal, tot mantenint els avantatges computacionals de la formulació lineal. Apartir d’aquesta base, adaptam el mètode de Todorov per a transformar els MDPaaquest marc de LMDP amb la recompensa definida en funció de les transicions. També establim una equivalència formal entre aquesta formulació i la formulació de LMDPs convencional amb la recompensa depenent de l’estat, demostrant que ambdós enfocaments condueixen a les mateixes estratègies de control òptimes mitjançant unes transformacions ben definides. Per a garantir una comparació justa i coherent entre els MDPs estàndard i la seva versió LMDP, integram la regularització d’entropia en el marc dels MDP i posteriorment ampliem el mètode de Todorov per adaptar-lo a aquests MDPs regularizats per entropia.El Aprendizaje por Refuerzo (RL) proporciona un marco teórico y práctico robusto para problemas de decisión secuencial, donde un agente aprende a interactuar con el entorno para maximizar la recompensa a largo plazo. Mientras que los métodos tradicionales que involucran programación dinámica se enfrentan a retos de rendimiento en espacios de estado grandes, la aparición de Procesos de Decisión de Markov con resolución lineal (LMDPs) ofrecen una alternativa computacionalmente eficiente mediante la reformulación del problema de control de manera que la ecuación de Bellman se convierte en lineal. Este trabajo explora una nueva formulación de LMDPs en la que la recompensa se define en función de la transición de un estado a otro, en lugar de la forma convencional donde la recompensa depende únicamente del estado. Esta representación es más intuitiva para las personas que quieren definir problemas de control de forma similar a como se especifican en el marco MDPnolineal, manteniendolas ventajas computacionales de la formulación lineal. A partir de esta base, adaptamos el método de Todorov para transformar los MDPsaese marco de LMDPs con la recompensa definida en función de las transiciones. También establecemos una equivalencia formal entre esta formulación y la formulación de LMDP convencional con la recompensa dependiendo del estado, demostrando que ambos enfoques conducen a las mismas estrategias de control óptimas mendiante unas transformaciones bien definidas. Para garantizar una comparación justa y coherente entre los MDPs est´andar y su versión linealmente resoluble, integramos la regularización de entropía en el marco de los MDP y posteriormente ampliamos el método de Todorov para adaptarlo a estos MDPs regularizados por entropía.