{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,3]],"date-time":"2026-05-03T02:36:13Z","timestamp":1777775773549,"version":"3.51.4"},"reference-count":72,"publisher":"Emerald","issue":"4","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2024,8,21]]},"abstract":"<jats:p>Reinforcement Learning (RL) serves as a versatile framework for sequential decision-making, finding applications across diverse domains such as robotics, autonomous driving, recommendation systems, supply chain optimization, biology, mechanics, and finance. The primary objective of these applications is to maximize the average reward. Real-world scenarios often necessitate adherence to specific constraints during the learning process.<\/jats:p>\n                  <jats:p>This monograph focuses on the exploration of various model-based and model-free approaches for Constrained RL within the context of average reward Markov Decision Pro cesses (MDPs). The investigation commences with an examination of model-based strategies, delving into two foundational methods \u2013 optimism in the face of uncertainty and posterior sampling. Subsequently, the discussion transitions to parametrized model-free approaches, where the primal dual policy gradient-based algorithm is explored as a solution for constrained MDPs. The monograph provides regret guarantees and analyzes constraint violation for each of the discussed setups.<\/jats:p>\n                  <jats:p>For the above exploration, we assume the underlying MDP to be ergodic. Further, this monograph extends its discussion to encompass results tailored for weakly communicating MDPs, thereby broadening the scope of its findings and their relevance to a wider range of practical scenarios.<\/jats:p>","DOI":"10.1561\/2400000038","type":"journal-article","created":{"date-parts":[[2024,9,26]],"date-time":"2024-09-26T08:34:36Z","timestamp":1727339676000},"page":"193-298","source":"Crossref","is-referenced-by-count":0,"title":["Constrained Reinforcement Learning with Average Reward Objective: Model-Based and Model-Free Algorithms"],"prefix":"10.1108","volume":"6","author":[{"given":"Vaneet","family":"Aggarwal","sequence":"first","affiliation":[{"name":"Purdue University ,","place":["USA"]}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Washim","family":"Uddin Mondal","sequence":"additional","affiliation":[{"name":"Indian Institute of Technology Kanpur ,","place":["India"]}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Qinbo","family":"Bai","sequence":"additional","affiliation":[{"name":"Purdue University ,","place":["USA"]}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"140","published-online":{"date-parts":[[2024,8,21]]},"reference":[{"issue":"12","key":"2026033014424995400_ref001","doi-asserted-by":"crossref","first-page":"4714","DOI":"10.1109\/TITS.2019.2931830","article-title":"Deeppool: Distributed model-free algorithm for ride-sharing using deep reinforcement learning","volume":"20","author":"Al-Abbasi","year":"2019","journal-title":"IEEE Transactions on Intelligent Transportation Systems"},{"key":"2026033014424995400_ref002","first-page":"64","volume-title":"Optimality and approximation with policy gradient methods in markov decision processes","author":"Agarwal","year":"2020"},{"issue":"1","key":"2026033014424995400_ref003","first-page":"4431","article-title":"On the theory of policy gradient methods: Optimality, approximation, and distribution shift","volume":"22","author":"Agarwal","year":"2021","journal-title":"The Journal of Machine Learning Research"},{"issue":"49","key":"2026033014424995400_ref004","first-page":"1","article-title":"Reinforcement learning for joint optimization of multiple rewards","volume":"24","author":"Agarwal","year":"2023","journal-title":"Journal of Machine Learning Research"},{"key":"2026033014424995400_ref005","first-page":"9","volume-title":"Multi-objective reinforcement learning with non-linear scalarization","author":"Agarwal","year":"2022"},{"key":"2026033014424995400_ref006","article-title":"Concave utility reinforcement learning with zero-constraint violations","volume-title":"Transactions on Machine Learning Research","author":"Agarwal","year":"2022"},{"key":"2026033014424995400_ref007","first-page":"22","volume-title":"Uncertainty in Artificial Intelligence","author":"Agarwal","year":"2022"},{"key":"2026033014424995400_ref008","first-page":"1184","article-title":"Optimistic posterior sampling for reinforcement learning: Worst-case regret bounds","volume-title":"Advances in Neural Information Processing Systems","author":"Agrawal","year":"2017"},{"issue":"4","key":"2026033014424995400_ref009","doi-asserted-by":"publisher","first-page":"454","DOI":"10.1109\/9.75103","article-title":"Adaptive control of constrained markov chains","volume":"36","author":"Altman","year":"1991","journal-title":"IEEE Transactions on Automatic Control"},{"key":"2026033014424995400_ref010","volume-title":"Constrained Markov decision processes","author":"Altman","year":"1999"},{"key":"2026033014424995400_ref011","doi-asserted-by":"crossref","first-page":"1565","DOI":"10.1613\/jair.1.13981","article-title":"Joint optimization of concave scalarized multi-objective reinforcement learning with policy gradient based algorithm","volume":"74","author":"Bai","year":"2022","journal-title":"Journal of Artificial Intelligence Research"},{"issue":"60","key":"2026033014424995400_ref012","first-page":"1","article-title":"Provably sample-efficient model-free algorithm for mdps with peak constraints","volume":"24","author":"Bai","year":"2023","journal-title":"Journal of Machine Learning Research"},{"key":"2026033014424995400_ref013","first-page":"3682","volume-title":"Achieving zero constraint violation for constrained reinforcement learning via primal-dual approach","author":"Bai","year":"2022"},{"key":"2026033014424995400_ref014","first-page":"975","article-title":"Achieving zero constraint violation for concave utility constrained reinforcement learning via primal-dual approach","volume":"78","author":"Bai","year":"2023","journal-title":"Journal of Artificial Intelligence Research"},{"key":"2026033014424995400_ref015","doi-asserted-by":"crossref","DOI":"10.1609\/aaai.v37i6.25826","volume-title":"Achieving zero constraint violation for constrained reinforcement learning via conservative natural policy gradient primal-dual algorithm","author":"Bai","year":"2023"},{"key":"2026033014424995400_ref016","volume-title":"Learning Infinite Horizon Average Reward Constrained Markov Decision Processes with Primal-Dual Policy Gradient Algorithm","author":"Bai","year":"2024"},{"key":"2026033014424995400_ref017","doi-asserted-by":"crossref","DOI":"10.1609\/aaai.v38i10.28973","volume-title":"Regret analysis of policy gradient algorithm for infinite horizon average reward markov decision processes","author":"Bai","year":"2024"},{"key":"2026033014424995400_ref018","first-page":"35","volume-title":"Regal: A regularization based algorithm for reinforcement learning in weakly communicating mdps","author":"Bartlett","year":"2009"},{"key":"2026033014424995400_ref019","first-page":"16315","article-title":"Constrained episodic reinforcement learning in concave-convex and knapsack settings","volume":"33","author":"Brantley","year":"2020","journal-title":"Advances in Neural Information Processing Systems"},{"key":"2026033014424995400_ref020","volume-title":"Two-tiered online optimization of region-wide datacenter resource allocation via deep reinforcement learning","author":"Chen","year":"2023"},{"key":"2026033014424995400_ref021","article-title":"Implicit finite-horizon approximation and efficient optimal algorithms for stochastic shortest path","volume-title":"Advances in Neural Information Processing Systems","author":"Chen","year":"2021"},{"key":"2026033014424995400_ref022","first-page":"3204","volume-title":"Improved no-regret algorithms for stochastic shortest path with linear mdp","author":"Chen","year":"2022"},{"key":"2026033014424995400_ref023","first-page":"3246","volume-title":"Learning infinite-horizon average-reward Markov decision process with constraints","author":"Chen","year":"2022"},{"key":"2026033014424995400_ref024","article-title":"Minimax regret for stochastic shortest path","volume-title":"Advances in Neural Information Processing Systems","author":"Cohen","year":"2021"},{"key":"2026033014424995400_ref025","first-page":"8210","volume-title":"Near-optimal regret bounds for stochastic shortest path","author":"Cohen","year":"2020"},{"key":"2026033014424995400_ref026","first-page":"3304","volume-title":"Provably efficient safe exploration via primal-dual policy optimization","author":"Ding","year":"2021"},{"key":"2026033014424995400_ref027","article-title":"Natural policy gradient primal-dual method for constrained markov decision processes","volume":"33","author":"Ding","year":"2020","journal-title":"Advances in Neural Information Processing Systems"},{"key":"2026033014424995400_ref028","volume-title":"Convergence and sample complexity of natural policy gradient primal-dual methods for constrained mdps","author":"Ding","year":"2023"},{"key":"2026033014424995400_ref029","first-page":"5429","volume-title":"Adapting to mixing time in stochastic optimization with markovian data","author":"Dorfman","year":"2022"},{"issue":"3","key":"2026033014424995400_ref030","first-page":"1","article-title":"A survey on cauchy-bunyakovsky-schwarz type discrete inequalities","volume":"4","author":"Dragomir","year":"2003","journal-title":"J. Inequal. Pure Appl. Math"},{"key":"2026033014424995400_ref031","volume-title":"Exploration-exploitation in constrained mdps","author":"Efroni","year":"2020"},{"key":"2026033014424995400_ref032","first-page":"1578","volume-title":"Efficient bias-span-constrained exploration-exploitation in reinforcement learning","author":"Fruit","year":"2018"},{"key":"2026033014424995400_ref033","volume-title":"An accelerated multi-level monte carlo approach for average reward reinforcement learning with general policy parametrization","author":"Ganesh","year":"2024"},{"key":"2026033014424995400_ref034","volume-title":"Variance-reduced policy gradient approaches for infinite horizon average reward markov decision processes","author":"Ganesh","year":"2024"},{"key":"2026033014424995400_ref035","first-page":"2656","volume-title":"Reinforcement learning for constrained markov decision processes","author":"Gattami","year":"2021"},{"key":"2026033014424995400_ref036","first-page":"1","volume-title":"A multi-agent reinforcement learning perspective on distributed traffic engineering","author":"Geng","year":"2020"},{"key":"2026033014424995400_ref037","volume-title":"Achieving sub-linear regret in infinite horizon average reward constrained mdp with linear function approximation","author":"Ghosh","year":"2023"},{"key":"2026033014424995400_ref038","first-page":"862","volume-title":"Learning for Dynamics and Control","author":"Gong","year":"2020"},{"key":"2026033014424995400_ref039","doi-asserted-by":"crossref","DOI":"10.1109\/TMRB.2023.3239674","article-title":"Asap: A semi-autonomous precise system for telesurgery during communication delays","volume-title":"IEEE Transactions on Medical Robotics and Bionics","author":"Gonzalez","year":"2023"},{"key":"2026033014424995400_ref040","first-page":"1563","article-title":"Near-optimal regret bounds for reinforcement learning","volume":"11","author":"Jaksch","year":"2010","journal-title":"Journal of Machine Learning Research"},{"key":"2026033014424995400_ref041","first-page":"2137","volume-title":"Provably efficient reinforcement learning with linear function approximation","author":"Jin","year":"2020"},{"key":"2026033014424995400_ref042","volume-title":"Approximately optimal approximate reinforcement learning","author":"Langford","year":"2002"},{"key":"2026033014424995400_ref043","doi-asserted-by":"crossref","DOI":"10.1017\/9781108571401","volume-title":"Bandit algorithms","author":"Lattimore","year":"2020"},{"key":"2026033014424995400_ref044","doi-asserted-by":"crossref","DOI":"10.1201\/9781315273600","volume-title":"Introduction to stochastic processes","author":"Lawler","year":"2018"},{"key":"2026033014424995400_ref045","doi-asserted-by":"crossref","DOI":"10.1109\/JBHI.2024.3392436","article-title":"Cooperating graph neural networks with deep reinforcement learning for vaccine prioritization","volume-title":"IEEE Journal of Biomedical and Health Informatics","author":"Ling","year":"2024"},{"key":"2026033014424995400_ref046","first-page":"17183","article-title":"Learning policies with zero or bounded constraint violation for constrained mdps","volume":"34","author":"Liu","year":"2021","journal-title":"Advances in Neural Information Processing Systems"},{"key":"2026033014424995400_ref047","first-page":"7624","article-title":"An improved analysis of (variance-reduced) policy gradient and natural policy gradient methods","volume":"33","author":"Liu","year":"2020","journal-title":"Advances in Neural Information Processing Systems"},{"issue":"4","key":"2026033014424995400_ref048","doi-asserted-by":"crossref","first-page":"3866","DOI":"10.1109\/TITS.2021.3128877","article-title":"Pass-goodpool: Joint passengers and goods fleet management with reinforcement learning aided pricing, matching, and route planning","volume":"23","author":"Manchella","year":"2021","journal-title":"IEEE Transactions on Intelligent Transportation Systems"},{"key":"2026033014424995400_ref049","first-page":"3097","volume-title":"Improved sample complexity analysis of natural policy gradient algorithm with general parameterization for infinite horizon discounted reward markov decision processes","author":"Mondal","year":"2024"},{"key":"2026033014424995400_ref050","volume-title":"Sample-efficient constrained reinforcement learning with general parameterization","author":"Mondal","year":"2024"},{"key":"2026033014424995400_ref051","article-title":"Mean-field control based approximation of multi-agent reinforcement learning in presence of a non-decomposable shared global state","volume-title":"Transactions on Machine Learning Research","author":"Mondal","year":"2023"},{"key":"2026033014424995400_ref052","first-page":"3003","article-title":"(more) efficient reinforcement learning via posterior sampling","volume-title":"Advances in Neural Information Processing Systems","author":"Osband","year":"2013"},{"key":"2026033014424995400_ref053","first-page":"2701","volume-title":"Why is posterior sampling better than optimism for reinforcement learning?","author":"Osband","year":"2017"},{"key":"2026033014424995400_ref054","article-title":"Learning unknown markov decision processes: A Thompson sampling approach","volume":"30","author":"Ouyang","year":"2017","journal-title":"Advances in neural information processing systems"},{"key":"2026033014424995400_ref055","volume-title":"Global optimality without mixing time oracles in average-reward rl via multi-level actor-critic","author":"Patel","year":"2024"},{"key":"2026033014424995400_ref056","volume-title":"Imed-rl: Regret optimal learning of ergodic markov decision processes","author":"Pesquerel","year":"2022"},{"key":"2026033014424995400_ref057","volume-title":"Markov decision processes: discrete stochastic dynamic programming","author":"Puterman","year":"2014"},{"key":"2026033014424995400_ref058","doi-asserted-by":"crossref","DOI":"10.1002\/9780470316887","volume-title":"Markov Decision Processes: Discrete Stochastic Dynamic Programming","author":"Puterman","year":"1994","edition":"1st"},{"issue":"4","key":"2026033014424995400_ref059","doi-asserted-by":"crossref","first-page":"1221","DOI":"10.1287\/moor.2014.0650","article-title":"Learning to optimize via posterior sampling","volume":"39","author":"Russo","year":"2014","journal-title":"Mathematics of Operations Research"},{"issue":"1","key":"2026033014424995400_ref060","doi-asserted-by":"crossref","first-page":"39","DOI":"10.1214\/aos\/1176342611","article-title":"Probability inequalities for the sum in sampling without replacement","volume":"2","author":"Serfling","year":"1974","journal-title":"The Annals of Statistics"},{"key":"2026033014424995400_ref061","first-page":"8604","volume-title":"Optimistic policy optimization with bandit feedback","author":"Shani","year":"2020"},{"key":"2026033014424995400_ref062","volume-title":"Learning in markov decision processes under constraints","author":"Singh","year":"2020"},{"key":"2026033014424995400_ref063","article-title":"Policy gradient methods for reinforcement learning with function approximation","volume":"12","author":"Sutton","year":"1999","journal-title":"Advances in neural information processing systems"},{"key":"2026033014424995400_ref064","volume-title":"Neural policy gradient methods: Global optimality and rates of convergence","author":"Wang","year":"2020"},{"key":"2026033014424995400_ref065","first-page":"10170","volume-title":"Model-free reinforcement learning in infinite-horizon average-reward markov decision processes","author":"Wei","year":"2020"},{"key":"2026033014424995400_ref066","doi-asserted-by":"crossref","DOI":"10.1609\/aaai.v36i4.20302","volume-title":"A provably-efficient model-free algorithm for infinite-horizon average-reward constrained markov decision processes","author":"Wei","year":"2022"},{"key":"2026033014424995400_ref067","first-page":"3274","volume-title":"Triple-q: A model-free algorithm for constrained reinforcement learning with sublinear regret and zero constraint violation","author":"Wei","year":"2022"},{"key":"2026033014424995400_ref068","article-title":"Inequalities for the l1 deviation of the empirical distribution","volume-title":"Hewlett-Packard Labs, Tech. Rep","author":"Weissman","year":"2003"},{"key":"2026033014424995400_ref069","first-page":"12167","volume-title":"Provably efficient algorithms for multi-objective competitive rl","author":"Yu","year":"2021"},{"key":"2026033014424995400_ref070","first-page":"2228","article-title":"On the convergence and sample efficiency of variance-reduced policy gradient method","volume":"34","author":"Zhang","year":"2021","journal-title":"Advances in Neural Information Processing Systems"},{"key":"2026033014424995400_ref071","first-page":"5476","volume-title":"Sharper model-free reinforcement learning for average-reward markov decision processes","author":"Zhang","year":"2023"},{"key":"2026033014424995400_ref072","first-page":"620","volume-title":"Learning for Dynamics and Control","author":"Zheng","year":"2020"}],"container-title":["Foundations and Trends\u00ae in Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.emerald.com\/ftopt\/article-pdf\/6\/4\/193\/11158726\/2400000038en.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/www.emerald.com\/ftopt\/article-pdf\/6\/4\/193\/11158726\/2400000038en.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,29]],"date-time":"2026-04-29T18:14:43Z","timestamp":1777486483000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.emerald.com\/ftopt\/article\/6\/4\/193\/1332648\/Constrained-Reinforcement-Learning-with-Average"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,8,21]]},"references-count":72,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2024,8,21]]}},"URL":"https:\/\/doi.org\/10.1561\/2400000038","relation":{},"ISSN":["2167-3888","2167-3918"],"issn-type":[{"value":"2167-3888","type":"print"},{"value":"2167-3918","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,8,21]]}}}