Reinforcement Learning with Discrete Diffusion Policies for Combinatorial Action Spaces

Haitong Ma, Ofir Nabati, Aviv Rosenberg, Bo Dai, Oran Lang, Craig Boutilier, Na Li, Shie Mannor, Lior Shani, Guy Tennenholtz
Proceedings of the 43rd International Conference on Machine Learning, PMLR 306:84780-84806, 2026.

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 and . 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 comparable or superior performance compared to other baselines. Crucially, our extensive empirical analysis reveals a key trade-off: FKL demonstrates superior sample efficiency and faster initial convergence, whereas RKL ensures stable training and higher asymptotic performance on challenging tasks.

Cite this Paper


BibTeX
@InProceedings{pmlr-v306-ma26aa, title = {Reinforcement Learning with Discrete Diffusion Policies for Combinatorial Action Spaces}, author = {Ma, Haitong and Nabati, Ofir and Rosenberg, Aviv and Dai, Bo and Lang, Oran and Boutilier, Craig and Li, Na and Mannor, Shie and Shani, Lior and Tennenholtz, Guy}, booktitle = {Proceedings of the 43rd International Conference on Machine Learning}, pages = {84780--84806}, year = {2026}, editor = {Zhang, Tong and Dudik, Miroslav and Jaggi, Martin and Agarwal, Alekh and Li, Sharon and Schuurmans, Dale and Zhu, Jerry and Berkenkamp, Felix and Dong, Hanze and Bietti, Alberto}, volume = {306}, series = {Proceedings of Machine Learning Research}, month = {06--11 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v306/main/assets/ma26aa/ma26aa.pdf}, url = {https://proceedings.mlr.press/v306/ma26aa.html}, 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 and . 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 comparable or superior performance compared to other baselines. Crucially, our extensive empirical analysis reveals a key trade-off: FKL demonstrates superior sample efficiency and faster initial convergence, whereas RKL ensures stable training and higher asymptotic performance on challenging tasks.} }
Endnote
%0 Conference Paper %T Reinforcement Learning with Discrete Diffusion Policies for Combinatorial Action Spaces %A Haitong Ma %A Ofir Nabati %A Aviv Rosenberg %A Bo Dai %A Oran Lang %A Craig Boutilier %A Na Li %A Shie Mannor %A Lior Shani %A Guy Tennenholtz %B Proceedings of the 43rd International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2026 %E Tong Zhang %E Miroslav Dudik %E Martin Jaggi %E Alekh Agarwal %E Sharon Li %E Dale Schuurmans %E Jerry Zhu %E Felix Berkenkamp %E Hanze Dong %E Alberto Bietti %F pmlr-v306-ma26aa %I PMLR %P 84780--84806 %U https://proceedings.mlr.press/v306/ma26aa.html %V 306 %X 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 and . 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 comparable or superior performance compared to other baselines. Crucially, our extensive empirical analysis reveals a key trade-off: FKL demonstrates superior sample efficiency and faster initial convergence, whereas RKL ensures stable training and higher asymptotic performance on challenging tasks.
APA
Ma, H., Nabati, O., Rosenberg, A., Dai, B., Lang, O., Boutilier, C., Li, N., Mannor, S., Shani, L. & Tennenholtz, G.. (2026). Reinforcement Learning with Discrete Diffusion Policies for Combinatorial Action Spaces. Proceedings of the 43rd International Conference on Machine Learning, in Proceedings of Machine Learning Research 306:84780-84806 Available from https://proceedings.mlr.press/v306/ma26aa.html.

Related Material