Reinforcement Learning with Discrete Diffusion Policies for Combinatorial Action Spaces
Haitong Ma, Ofir Nabati, Aviv Rosenberg, Bo Dai, Oran Lang, Idan Szpektor, Craig Boutilier, Na Li, Shie Mannor, Lior Shani, Guy Tenneholtz · 2025
Read Reinforcement Learning with Discrete Diffusion Policies for Combinatorial Action Spaces by Haitong Ma, Ofir Nabati, Aviv Rosenberg, Bo Dai, Oran Lang, Idan Szpektor, Craig Boutilier, Na Li, Shie Mannor, Lior Shani, Guy Tenneholtz (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2509-22963.txt.
Introduction
Reinforcement learning breaks down when each step offers a huge mix of possible actions. Haitong Ma and 9 co-authors train discrete diffusion models to act as policies in such spaces. Diffusion models build outputs step by step, which suits rich action mixes. Their key move is a stable online training loop. A mirror descent step first sets an ideal, regularized target policy.
Training then becomes a matching task: the diffusion model learns to copy that target. Splitting the two steps keeps learning steady and boosts results. Tests covered DNA sequence design, macro-actions, and multi-agent setups. The method set new best scores and used fewer samples than rivals.
Catalog record
| CREATOR | Haitong Ma, Ofir Nabati, Aviv Rosenberg, Bo Dai, Oran Lang, Idan Szpektor, Craig Boutilier, Na Li, Shie Mannor, Lior Shani, Guy Tenneholtz |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 65 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2509-22963
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Reinforcement Learning with Discrete Diffusion Policies for Combinatorial Action Spaces Haitong Ma, Ofir Nabati, Aviv Rosenberg, Bo Dai, Oran Lang, Idan Szpektor, Craig Boutilier, Na Li, Shie Mannor, Lior Shani, Guy Tenneholtz Abstract Reinforcement learning (RL) struggles to scale to large, combinatorial action spaces common in many real-world problems. This paper introduces a novel framework for training discrete diffusion models as highly effective policies in these complex settings. Our key innovation is an efficient online training process that ensures stable and effective policy improvement. By leveraging policy mirror descent (PMD) to define an ideal, regularized target policy distribution, we frame the policy update as a distributional matching problem, training the expressive diffusion model to replicate this stable target. This decoupled approach stabilizes learning and significantly enhances training performance. Our method achieves state-of-the-art results and superior sample efficiency across a diverse set of challenging combinatorial benchmarks, including DNA sequence generation, RL with macro-actions, and multi-agent systems. Experiments demonstrate that our diffusion policies attain superior performance compared to other baselines. 1 Introduction Reinforcement learning (RL) has been instrumental in pushing the boundaries of autonomous decision-making, achieving superhuman performance in a diverse range of complex sequential tasks Silver et al. 2016 ; Vinyals et al. 2019 ; Schrittwieser et al. 2020 . However, a significant frontier remains: scaling these successes to problems with vast, combinatorial discrete action spaces. Such challenges are not niche; they are central to many real-world applications, including planning with macro-actions in hierarchical RL Sutton et al. 1999a ; Durugkar et al. 2016 , coordinating strategies in multi-agent systems Hernandez-Leal et al. 2019 , and generating slates in recommender systems Ie et al. 2019 . The sheer scale of these action spaces poses a fundamental challenge to standard RL algorithms, demanding highly efficient policy parameterizations and effective exploration strategies. Prior approaches have attempted to mitigate this complexity by mapping actions to lower-dimensional subspaces Stulp et al. 2012 ; Tennenholtz & Mannor 2019 , employing hierarchical training schemes Nachum et al. 2018 , or assuming specific structural properties of the action space Carrara et al. 2019 . While effective in certain contexts, these methods often rely on structural assumptions or inductive biases that may not hold in more general and complex problem settings. More recently, the success of autoregressive models Vaswani et al. 2017 has inspired their use for policies over combinatorial actions Chen et al. 2021 ; Wen et al. 2022b . Yet, these models suffer from two key limitations: high computational cost during inference due to their sequential generation process and the imposition of a causal action ordering, which is often an artificial and restrictive constraint. Diffusion models have emerged as a powerful class of generative models, renowned for their ability to capture highly complex probability distributions without imposing a causal structure Sohl-Dickstein et al. 2015 ; Ho et al. 2020 . Recent extensions to discrete spaces have further broadened their applicability Austin et al. 2021 ; Sun et al. 2022 ; Campbell et al. 2022 ; Shi et al. 2024 . This inherent flexibility and expressiveness make them an ideal candidate for modeling policies in large, unstructured discrete action spaces. While diffusion models have been actively explored for synthesizing policies in continuous control Wang et al. 2022 ; Ding et al. 2024 ; Ren et al. 2024 ; Ma et al. 2025 , a principled and efficient framework for training discrete diffusion policies with RL remains unexplored. In this work, we introduce a novel framework for training discrete diffusion models as highly effective policies for combinatorial action spaces. Our key innovation is an efficient online training process that ensures stable and effective policy improvement. We leverage policy mirror descent (PMD, Shani et al. 2020 ; Tomar et al. 2021 ; Lan 2023 ) to define the ideal target policy distribution based on the PMD optimization objective. This reframes the policy update as a distributional matching problem, where we train our expressive diffusion model to replicate this stable target. This decoupled approach is critical: it separates the RL objective optimization from the complex task of representation learning, which we delegate to the diffusion model, thereby stabilizing the entire learning process and significantly enhancing performance. Our core contributions are as follows: (1) We introduce RL-D 2 , a new and efficient online training framework for using discrete diffusion models as policies in RL for combinatorial action spaces. Our core mechanism reframes the policy update as a distributional matching problem by using policy mirror descent (PMD) to define a stable target distribution, which significantly stabilizes learning. (2) We derive and analyze two practical policy improvement methods based on minimizing the forward and reverse Kullback-Leibler (KL) divergence to the PMD target. (3) Finally, we conduct extensive experiments across three distinct and challenging domains: DNA sequence generation Gosai et al. 2023 , long-horizon RL with macro-actions in Atari Bellemare et al. 2013 , and cooperative multi-agent RL in the challenging Google Research Football domain Kurach et al. 2020 . In all settings, our method achieves state-of-the-art results, demonstrating superior performance, scalability, and efficiency. 2 Related Work Discrete Diffusion Models. Diffusion models for generating continuous data, such as images, typically rely on the gradual addition and removal of Gaussian noise to learn and synthesize complex probability distributions ( Sohl-Dickstein et al. 2015 ; Ho et al. 2020 ) . However, this paradigm is ill-suited for discrete data like text or biological sequences, where values are categorical and adding small amounts of continuous noise is not meaningful. To address this, discrete diffusion models extend the iterative refinement idea to discrete state spaces, with forward and backward processes using Markov chains where the each transition in a sequence is sampled independently. Various approaches have explored different transition mechanisms and training objectives ( Austin et al. 2021 ; Campbell et al. 2022 ; Sun et al. 2022 ; Lou et al. 2023 ; Shi et al. 2024 ) . Among these, absorbing (or masked) diffusion has proven to be particularly effective ( Sahoo et al. 2024 ; Ou et al. 2024 ) . The success of these models has led to their application in a range of domains. In natural language processing, they have been adapted for complex generation tasks ( Arriola et al. 2025 ; Ye et al. 2025 ; Nie et al. 2025 ) . More relevant to our work, discrete diffusion has shown significant promise in bio-sequence modeling for generating novel proteins and DNA sequences with desired properties ( Gruver et al. 2023 ; Wang et al. 2024a ) . Reward-based Fine-tuning and RL for Discrete Diffusion. A key challenge, beyond unconditional generation, is adapting discrete diffusion to optimize for specific objectives. This has primarily been approached through reward-based fine-tuning, which adjusts the model’s parameters to increase the likelihood of generating high-reward samples. For instance, Wang et al. 2024a enable direct reward backpropagation by leveraging the Gumbel-softmax trick, while ( ) zekri2025fine optimize the model by manipulating the score entropy ( Lou et al. 2023 ) . While effective, these methods can be viewed as forms of a single-step policy optimization. By contrast, the application of online RL to discrete diffusion is unexplored, and faces challenges such as exploration-exploitation trade-offs, computational efficiency, horizon-complexity trade-off.