Resource allocation plays a critical role in minimizing cycle time and improving the efficiency of business processes. Recently, Deep Reinforcement Learning (DRL) has emerged as a powerful technique to optimize resource allocation policies in business processes. In the DRL framework, an agent learns a policy through interaction with the environment, guided solely by reward signals that indicate the quality of its decisions. However, existing algorithms are not suitable for dynamic environments such as business processes. Furthermore, existing DRL-based methods rely on engineered reward functions that approximate the desired objective, but a misalignment between reward and objective can lead to undesired decisions or suboptimal policies. To address these issues, we propose a rollout-based DRL algorithm and a reward function to optimize the objective directly. Our algorithm iteratively improves the policy by evaluating execution trajectories following different actions. Our reward function directly decomposes the objective function of minimizing the cycle time, such that trial-and-error reward engineering becomes unnecessary. We evaluated our method in six scenarios, for which the optimal policy can be computed, and on a set of increasingly complex, realistically sized process models. The results show that our algorithm can learn the optimal policy for the scenarios and outperform or match the best heuristics on the realistically sized business processes.

The expected regret of any reinforcement learning algorithm is lower bounded by $\Omega\left(\sqrt{DXAT}\right)$ for undiscounted returns, where $D$ is the diameter of the Markov decision process, $X$ the size of the state space, $A$ the size of the action space and $T$ the number of time steps. However, this lower bound is general. A smaller regret can be obtained by taking into account some specific knowledge of the problem structure. In this article, we consider an admission control problem to an $M/M/c/S$ queue with $m$ job classes and class-dependent rewards and holding costs. Queuing systems often have a diameter that is exponential in the buffer size $S$, making the previous lower bound prohibitive for any practical use. We propose an algorithm inspired by UCRL2, and use the structure of the problem to upper bound the expected total regret by $O(S\log T + \sqrt{mT \log T})$ in the finite server case. In the infinite server case, we prove that the dependence of the regret on $S$ disappears.

Reinforcement learning (RL) studies the problem of sequential decision making in an unknown environment by carefully balancing between exploration (learning) and exploitation (optimizing) (Sutton and Barto 2018). While the RL study has a relatively long history, it has received considerable attention in the past decades due to the explosion of available data and rapid improvement of computing power. A hitherto default mathematical framework for RL is Markov decision process (MDP), where the agent does not know the transition probabilities and can observe a reward resulting from an action but does not know the reward function itself. There has been extensive research on RL for discrete-time MDPs (DTMDPs); see, e.g., Jaksch et al. (2010), Osband and Van Roy (2017), Azar et al. (2017), Jin et al. (2018). However, much less attention has been paid to RL for continuous-time MDPs, whereas there are many real-world applications where one needs to interact with the unknown environment and learn the optimal strategies continuously in time. Examples include autonomous driving, control of queueing systems, control of infectious diseases, preventive maintenance and robot navigation; see, e.g., Guo and Hernández-Lerma (2009), Piunovskiy and Zhang (2020), Chapter 11 of Puterman (2014) and the references therein. In this paper we study RL for tabular continuous-time Markov decision processes (CTMDPs) in the finite-horizon, episodic setting, where an agent interacts with the unknown environment in episodes of a fixed length with finite state and action spaces. The study of model-based (i.e. the underlying models are assumed to be known) finite-horizon CTMDPs has a very long history, probably dating back to Miller (1968), with vast applications including queueing optimization (Lippman 1976), dynamic pricing (Gallego and Van Ryzin 1994), and finance and insurance (Bäuerle and

Reinforcement learning (RL) is the problem of an agent learning how to map states to actions in order to maximize the reward over time in an unknown environment. It has received significant attention in the past decades, and the key challenge is in balancing the trade-off between exploration and exploitation (Sutton and Barto 2018). The common model for RL is a Markov Decision Process (MDP), which provides a mathematical framework for modeling sequential decision making problems under uncertainty. Most of the current studies on RL focus on developing algorithms and analysis for discrete-time MDPs. In contrast, less attention has been paid to continuous-time MDPs. However, there are many real-world applications where one needs to consider continuous-time MDPs. Examples include control of queueing systems, control of infectious diseases, preventive maintenance and high frequency trading; see, e.g., Guo and Hernández-Lerma (2009), Piunovskiy and Zhang (2020), Chapter 11 of Puterman (2014) and the references therein. One may propose discretizing time upfront to turn a continuous-time MDP into a discrete-time one and then apply the existing results and algorithms. However, it is well known in the RL community that this approach is very sensitive to time discretization and may perform poorly with small time steps; see e.g.

Continuous-time Markov decision processes (CTMDPs) are canonical models to express sequential decision-making under dense-time and stochastic environments. When the stochastic evolution of the environment is only available via sampling, model-free reinforcement learning (RL) is the algorithm-of-choice to compute optimal decision sequence. RL, on the other hand, requires the learning objective to be encoded as scalar reward signals. Since doing such translations manually is both tedious and error-prone, a number of techniques have been proposed to translate high-level objectives (expressed in logic or automata formalism) to scalar rewards for discrete-time Markov decision processes (MDPs). Unfortunately, no automatic translation exists for CTMDPs. We consider CTMDP environments against the learning objectives expressed as omega-regular languages. Omega-regular languages generalize regular languages to infinite-horizon specifications and can express properties given in popular linear-time logic LTL. To accommodate the dense-time nature of CTMDPs, we consider two different semantics of omega-regular objectives: 1) satisfaction semantics where the goal of the learner is to maximize the probability of spending positive time in the good states, and 2) expectation semantics where the goal of the learner is to optimize the long-run expected average time spent in the ``good states" of the automaton. We present an approach enabling correct translation to scalar reward signals that can be readily used by off-the-shelf RL algorithms for CTMDPs. We demonstrate the effectiveness of the proposed algorithms by evaluating it on some popular CTMDP benchmarks with omega-regular objectives.