Learning optimal policies from event logs through reinforcement learning: a comparison of deep and MDP-based approaches

In plain words

A loan application involves two parties. The bank controls some steps, such as making an offer, and the customer controls others, such as accepting or declining it. The bank wants to choose its next step so that its profit per case goes up. The authors ask whether a good policy for this can be learned directly from the history of past cases in an event log, without a hand-written model of the process or of the customer.

They try two learning approaches. The first builds a map of the process from the log. It groups the history of each case into a limited number of groups, and treats "the last step plus its group" as a state. It then counts how often one state leads to another, and how much profit follows, and runs a standard planning calculation on that map. Transitions seen only a few times can look better than they really are, so the method shrinks their weight in the calculation. The second approach trains a neural network with a memory layer on the same log, using an offline method that is cautious about values the log supports poorly.

Both approaches were tested in simulations of the process, where a simulated customer responds to the bank's choices, and on two real logs. Both improved the profit compared with the behaviour recorded in the logs. The map-based method was much faster to train.

TL;DR

• Learns which activity the process owner should trigger next, to maximise a per-case profit KPI, from a loan-process event log in which the owner controls only some activities §1 §6.2.
• Method 1 (MDP-based): clusters event prefixes with k-means, builds an MDP over (last activity, cluster) states, and solves it by value iteration with a Q-value factor h that damps rarely seen state-action pairs §5.1.
• Method 2 (offline deep RL): Conservative Q-Learning (DiscreteCQL) on an LSTM that reads the last 20 events, with a mask from the directly-follows graph at inference §5.2.
• Author-reported: both methods beat the customary policy on synthetic and real logs. Training took 30 to 364 s for the MDP method, against 1,670 to 1,924 s per CQL epoch tab. 8 §7.2 §7.3.
• The official code differs from the paper in the MDP reward, the cluster counts, the place where h is applied and some CQL settings. See Paper vs code.

Problem

Prescriptive process monitoring usually triggers predefined interventions. Methods that recommend the next activity in general are rarer §1. In multi-actor processes the policy controls only part of the activities, while others are driven by external actors §1 §6.2. Hand-built MDPs need domain knowledge that is often unavailable. The authors aim to use only two inputs: which activities the owner controls, and the KPI §1 §8.

Two assumptions make the problem hard. The first is that policies cannot be tested on live customers, so the evaluation uses business process simulation (BPS) §6.3. The second is that the learner sees only logged behaviour and cannot interact with the environment during training. Offline RL addresses this, but value estimates for actions the log rarely shows are unreliable §4.2 §5.1.2.

The state uses control flow only. Data payloads, such as the loan amount, enter only through the reward, so the method cannot condition on them §8.

Method

Setting and notation

• An event log is a set of traces. A trace is an ordered sequence of events, each with an activity label. The prefix σ_k holds the first k events §4.1.
• f_a(σ) counts the occurrences of activity a in the trace; p_a(σ) is the position of its last occurrence, counting from 1 (zero if absent) §4.1.
• Activities are split into agent (bank) activities and environment (customer) activities. Environment activities cannot be chosen, but they are part of the state §5.1.1 tab. 2.
• The KPI is the profit of a trace: 15% interest on the requested amount if the offer is accepted, minus a cost of 36 euros per hour of work. Activities without a duration get 10 minutes §6.2 and fn..

Method 1: MDP-based RL (§5.1)

Preprocessing, in three steps §5.1.1:

1. Enrich the log. Label each activity as agent or environment. Compute the trace KPI r(σ) and set r(σ_k) = 0 for every proper prefix.
2. Encode and cluster prefixes. Each prefix becomes one vector: activity counts divided by a global maximum f_max, last positions divided by the maximum trace length p_max, and the normalised reward r̃, which is zero for proper prefixes eq. 4 eq. 5 eq. 6. Run k-means on these vectors. The cluster count comes from an elbow rule applied to the within-cluster sum of squares, using the KneeLocator method with sensitivity 1 §5.1.1 fn..
3. Build the MDP. The state after event e_k is the pair of its activity and the cluster of the prefix before it eq. 7. For each edge (s, a, s'), P(s, a, s') is the share of traces that reach s' among traces that are in s and take a. R(s, a, s') is the mean of r(σ_k) over the prefixes that produce that edge §5.1.1 step 3 and fn..

Learning §5.1.2:

• The Q-function is scaled by h(s, a), which depends on the count n(s, a) of the pair in the log eq. 8. Three choices are compared: h^0 = 1, which is the standard case; a step function with threshold n_T eq. 9; and a sigmoid with scale λ eq. 10. The thresholds are the first, second and third quartiles Q1, Q2, Q3 of n(s, a) over the state-action pairs of each MDP §7.1 tab. 4.
• Value iteration applies the Bellman optimality update eq. 3, with discount γ = 1 and a stopping threshold of 10^-5 on the largest change §5.1.2 fn..
• The policy is greedy in q: each state gets the action with the highest q §4.2.

Runtime: a new prefix is mapped to a state by the same steps, and the policy returns the best next activity for that state §5.1.2 fn..

Method 2: offline Conservative Q-Learning (§5.2)

• The Q-network is the DiscreteCQL algorithm from the d3rlpy library, with a custom LSTM encoder §5.2. The paper's footnote names version 2.2.0 §5.2 fn., and the released requirements pin the same version requirements.txt. CQL estimates values that act as a lower bound on the policy value §4.2.
• Each training transition has four parts: the observation, the action, the reward and a terminal flag. The observation is the last 20 events before the action, left-padded and one-hot encoded. The action is the next event, and the reward is the instantaneous reward of that event §5.2.
• Transitions whose action is an environment activity are removed. Their reward is added to the previous transition, and the terminal flag moves there §5.2 fig. 4.
• Training runs for 100 epochs of 150,000 steps, with batch size 64, LSTM hidden size 128, target update interval 32,000 and γ = 1. The other parameters are described as default values §5.2 and fn..
• At inference, a mask removes successor activities that are rare in the training log. The directly-follows graph is built from the training log, and successors below the 20th percentile of counts are removed §5.2, last paragraph.
• Policies were kept at 50 and 100 epochs §7.2.

Equations (as numbered in the paper)

Q-value of a policy eq. 1:

q^{\pi}(s,a) := \mathbb{E}_{\pi}\Big(\sum_{k=0}^{\infty} \gamma^{k} r_{k+t+1} \,\Big|\, s_t = s,\ a_t = a\Big)

Bellman equation for a deterministic policy π eq. 2:

q^{\pi}(s,a) = \sum_{s'} P(s,a,s')\big(\mathcal{R}(s,a,s') + \gamma\, q^{\pi}(s',a')\big), \qquad a' = \pi(s')

Bellman optimality equation eq. 3:

q^{*}(s,a) = \sum_{s'} P(s,a,s')\big(\mathcal{R}(s,a,s') + \gamma \max_{a'} q^{*}(s',a')\big)

Prefix encoding eq. 4:

\mathbf{v}_{\sigma_k} = \Big(\tfrac{f_{a_1}(\sigma_k)}{f_{\max}}, \dots, \tfrac{f_{a_n}(\sigma_k)}{f_{\max}},\ \tfrac{p_{a_1}(\sigma_k)}{p_{\max}}, \dots, \tfrac{p_{a_n}(\sigma_k)}{p_{\max}},\ \tilde r(\sigma_k) \Big)

Normalisation constants eq. 5:

f_{\max} = \max_{a \in A,\ \sigma \in \mathcal{L},\ 0 < k \le \mathrm{len}(\sigma)} f_a(\sigma_k), \qquad p_{\max} = \max_{\sigma \in \mathcal{L}} \mathrm{len}(\sigma)

Normalised reward eq. 6:

\tilde r(\sigma_k) = \begin{cases} 0 & k < \mathrm{len}(\sigma) \\ \dfrac{r(\sigma) - \min_{\sigma'} r(\sigma')}{\max_{\sigma'} r(\sigma') - \min_{\sigma'} r(\sigma')} & k = \mathrm{len}(\sigma) \end{cases}

State of a prefix eq. 7:

s_{\sigma_k} = \big(a_{i_k},\ c_{\sigma_{k-1}}\big)

Scaled Q-value eq. 8:

\tilde q(s,a) = q(s,a)\, h(s,a)

Step scale factor eq. 9:

h^{\text{step}}_{n_T}(s,a) = \begin{cases} 0 & n(s,a) \le n_T \\ 1 & n(s,a) > n_T \end{cases}

Sigmoid scale factor eq. 10:

h^{\text{sig}}_{\lambda}(s,a) = 1 - \frac{2\, e^{-n(s,a)/\lambda}}{1 + e^{-n(s,a)/\lambda}}

Pseudocode

Prefix encoding for clustering, following eq. 4 to eq. 6:

# Prefix encoding for clustering  [§5.1.1] [eq. 4] [eq. 5] [eq. 6]
# Input: log of traces; activity set A; KPI value per complete trace
# Output: one vector per prefix

def encode_prefixes(log, activities):
    # Global maxima for normalisation  [eq. 5]
    f_max = largest activity count over all prefixes in the log
    p_max = largest trace length in the log
    vectors = []
    for trace in log:
        for k in range(1, len(trace) + 1):
            prefix = trace[:k]
            # Activity counts scaled by f_max  [eq. 4]
            freq = [count(a, prefix) / f_max for a in activities]
            # Last position of each activity scaled by p_max  [eq. 4]
            last = [last_position(a, prefix) / p_max for a in activities]
            # Reward is zero for proper prefixes  [eq. 6]
            reward = scaled_kpi(trace) if k == len(trace) else 0.0
            vectors.append(freq + last + [reward])
    return vectors

MDP construction after clustering, following eq. 7 and §5.1.1:

# MDP construction from clustered prefixes  [§5.1.1] [eq. 7]
# Input: log; cluster label for each proper prefix; r(σ_k) per prefix
# Output: table of (s, a, s') with probability P and reward R

def build_mdp(log, labels):
    counts = {}
    for trace in log:
        state = START_STATE
        for k in range(1, len(trace)):
            action = activity(trace[k])
            # State after e_k: its activity plus the cluster of σ_{k-1}
            # [eq. 7]
            next_state = (action, labels[prefix_before(trace, k)])
            # Record the edge and the reward of the prefix that ends here
            # [§5.1.1 step 3]
            record(counts, state, action, next_state, r_of_prefix(trace, k))
            state = next_state
    # P = edge count / count of (state, action); R = mean reward on the edge
    return normalise(counts)

Scaled value iteration, following eq. 3 and eq. 8:

# Scaled value iteration  [§5.1.2] [eq. 3] [eq. 8]
# Input: table of P, R and counts; scale h(s, a); gamma = 1; threshold 1e-5
# Output: greedy policy

def learn_policy(table, h, gamma, threshold):
    # Start with zero values for every state-action pair
    q = {(s, a): 0.0 for (s, a) in table.state_actions}
    while True:
        new_q = {}
        for (s, a) in table.state_actions:
            backup = 0.0
            for s_next, p, r in table.outcomes(s, a):
                # Zero continuation after the END state  [eq. 3]
                if s_next is END:
                    best_next = 0.0
                else:
                    best_next = max(q[(s_next, b)]
                                    for b in table.actions(s_next))
                backup += p * (r + gamma * best_next)
            # Scale the backup by h(s, a)  [eq. 8]; see Paper vs code
            new_q[(s, a)] = h(s, a) * backup
        delta = max(abs(new_q[key] - q[key]) for key in q)
        q = new_q
        if delta <= threshold:
            break
    # Greedy policy: best action in each state  [§4.2] [§5.1.2]
    return {s: argmax_a q[(s, a)] for s in table.states}

Offline dataset for DiscreteCQL, following §5.2 and fig. 4:

# Offline transitions for Conservative Q-Learning  [§5.2] [fig. 4]
# Input: traces with an instantaneous reward per event; window W = 20
# Output: transitions (observation, action, reward, terminal)

def build_transitions(traces, env_activities, window=20):
    transitions = []
    for trace in traces:
        for k in range(1, len(trace)):
            # Last W events before the action, left-padded, one-hot
            # [§5.2]
            window_events = trace[max(0, k - window):k]
            observation = one_hot(pad_left(window_events, window))
            action = one_hot(activity(trace[k]))
            reward = reward_of(trace[k])
            done = (k == len(trace) - 1)
            transitions.append((observation, action, reward, done))
    # Remove environment actions; add their reward to the previous
    # transition and move the terminal flag there  [§5.2] [fig. 4]
    return absorb_env_actions(transitions, env_activities)

Recommendation with masking at inference, following §5.2:

# Recommendation with action mask  [§5.2] (mask: last paragraph)
# Input: activities so far; trained Q-network; mask from the training DFG
# Output: one activity

def recommend(prefix, q_network, mask, window=20):
    # Training windows begin with the START event  [§5.2]
    events = ["START"] + prefix
    observation = one_hot(pad_left(events[-window:], window))
    values = q_network.predict_values(observation)
    # Keep only successors that the mask allows after the last event
    allowed = mask[events[-1]]
    return max(allowed, key=lambda a: values[a])

Hyperparameters

Datasets

Table 2 lists the activities that the environment controls for each log tab. 2:

Table 3 lists the logs tab. 3. BPIC2017 is filtered to new-credit applications §6.2 fn..

Table 4 gives the quartiles of n(s, a) per dataset, used as thresholds tab. 4:

Results

Author-reported. Setup: synthetic logs come from a simulation model whose customer behaviour is fixed; each learned policy is evaluated on 2000 simulated traces §6.3. Real logs are BPIC2012 and BPIC2017 (New credit). Their simulation models come from an Inductive Miner spaghetti model and Simod, with a decision-tree version of the customer as a second model §6.3 §7.2. Hardware for the timings is not stated. The paper's comparison baselines are the customary policy of the simulator and an informed heuristic that knows the customer rules (synthetic logs only) §6.3 app. C.

Real logs: average KPI over 20 simulations tab. 7

The observed average KPI on the test logs is 328 for BPIC2012 and 1299 for BPIC2017. Simulations of the customary policy stay close to these values §7.2. Marks: U means underlined in the paper, a significant gain over the customary policy; B means bold, not significantly different from the best policy in that model §7.2.

Simulation traces per run equal the test set: 2617 (BPIC2012) and 5623 (BPIC2017) §7.2 fn..

Computation time, seconds tab. 8

The MDP column is the largest time among the MDP policies. The CQL columns give time per epoch and the total for 50 and 100 epochs §7.3.

Trace outcomes on L2000,rare tab. 5

Percentages of traces by outcome. Outcomes: accepted, rejected by customer, rejected by bank, error. Average trace length is in the last row tab. 5.

Synthetic logs (text summary; values are in figures only)

The bar values for the eight synthetic logs appear only in fig. 6 and fig. 7, not in the text. The paper reports the following, with figure-level values not reproduced here:

• For the synthetic logs, the customary policy is almost always beaten by the learned policies §7.1.
• The informed heuristic is among the best policies on every synthetic log. Except for L16000,rare, at least one learned policy is statistically indistinguishable from it §7.1.
• With h^0 = 1, performance is unstable. On L16000, L8000,rare and L16000,rare it is worse than the customary policy §7.1.
• Non-trivial scale factors improve on h^0 in general. The exception is sigQ3 on L2000,rare, which gives a negative KPI §7.1.
• sigQ1, stepQ1 and stepQ2 are the most robust choices, each among the best policies on 4 of 8 logs §7.1.
• Both methods more than double the customary KPI on the L_i logs, and more than triple it on most L_i,rare logs §7.2.
• The paper states that CQL policies never appear among the best on the synthetic logs, while each of the selected MDP policies appears among the best on 4 of 8 §7.2.
• Appendix B: when the learned policy starts after 5 to 25 events of the trace, the informed heuristic is beaten by learned policies in some cases between prefix lengths 5 and 20. The sigQ1 policy stays among the best, and CQL is among the best from prefix length 15 on app. B.
• Appendix A: sigQ1, sigQ2, stepQ1 and stepQ2 change little across cluster counts near the reference value. h^0 and sigQ3 are sensitive app. A.

Headline claims (author-reported)

• Both methods improve the target KPI on real and synthetic logs, with similar effectiveness [abstract] §7.2.
• The MDP method is much faster to train than CQL §7.3 tab. 8.
• The authors describe the MDP method's performance edge over CQL as consistent but not overwhelming §7.2.

Paper vs code

Code: official repository rgraziosi-fbk/rl-optimal-policy-pm, linked by the paper in its results section §7. The owner's name matches an author. The repository has no LICENSE file, so the code is cite-only. Commit: eaceef763fded694867da92c9ec961bacf7cf6be. Paths below are relative to the repository root.

• Cluster counts. The paper's footnote gives 140 for BPIC2012, 100 for BPIC2017, L2000, L4000, L8000, L2000,rare, L4000,rare and L16000,rare, 80 for L16000 and L8000,rare §7.1 fn.. Appendix A uses 100 for L4000 and L4000,rare app. A. The released driver sets 140 for L4000, 120 for L8000, L16000, L2000,rare and L4000,rare, and 100 for L8000,rare and L16000,rare Training_mdp_policy.py MDPCreator_BPI_cluster.py. The shipped model folders match the footnote for L16000 (80) and L8000,rare (80) main_with_batch.py. The two code sources disagree with each other.
• MDP reward source. The paper defines the edge reward as the mean of the prefix rewards r(σ_k) §5.1.1 step 3 and fn.. The code stores on each event the reward of the k-means centre it belongs to, inverse-transformed to KPI units Clusterer_splitted_without_last_act.py. The MDP builder reads that attribute for training MDPCreator_BPI_cluster.py MDPCreator_BPI_cluster.py. So an edge reward is an average of centre rewards, not of the trace rewards on that edge.
• Extra min-max scaling of rewards. The MDP builder rescales edge rewards by min-max by default MDPCreator_BPI_cluster.py MDPCreator_BPI_cluster.py. Value iteration rescales them again DP_methods.py with normalize_reward=True Training_mdp_policy.py. The paper mentions neither scaling §5.1.1 §5.1.2.
• Reward for proper prefixes. Equation 6 sets r̃ to zero for proper prefixes eq. 6. The code writes 0.0 for those rows Clusterer_splitted_without_last_act.py, then min-max scales the whole column Clusterer_splitted_without_last_act.py. Those rows therefore get (0 − min) / (max − min), which is positive whenever the smallest trace reward is negative. The KPI charges a cost for every timed activity utils.py, so this is the usual case.
• Where h applies. The paper defines q̃ = q · h eq. 8 and does not say whether the scaled values feed the Bellman backup. The code multiplies every backup by h DP_methods.py DP_methods.py DP_methods.py. The scaled values then feed the maximum over next actions in later sweeps, so h changes the values, not only the final ranking.
• Elbow criterion. The paper calls the criterion the within-cluster sum of squares §5.1.1 step 2. The elbow script adds the distance to the nearest centre, not its square Clusterer_Silhouette_analysis.py. It searches K from 20 to 300 in steps of 20 with one run each Clusterer_Silhouette_analysis.py. The paper gives no search range.
• K-means settings. The paper gives no seed or initialisation details. The code sets random_state=0 and leaves the other settings at library defaults Clusterer_splitted_without_last_act.py.
• CQL learning rate and reward scaling. The paper says other CQL parameters are at their default values §5.2 fn.. The code sets a learning rate of 0.0000625 and a StandardRewardScaler explicitly train.py. The paper does not mention a reward scaler.
• CQL training data. The released training script builds its dataset from one log, event_log_rare_2000, using single rewards train.py. The paper does not say which log each CQL policy was trained on. The shipped synthetic evaluation model is in the log_rare_8000 folder . So the released script does not reproduce every CQL model in the paper.
• Observation window. The paper says the state is the trace truncated at the current event §5.2. The code's observation holds the events before the action event, not including it dataset.py. The paper wording allows both readings.
• Duration cap. The KPI cost caps each activity's duration at 3600 seconds utils.py utils.py. The paper does not mention a cap.
• Driver script. The __main__ block of DP_methods.py calls DP_training_main with three arguments, while the function takes seven DP_methods.py DP_methods.py. Use Training_mdp_policy.py as the entry point Training_mdp_policy.py.

Pitfalls

• Stated only for code. Several settings that the paper leaves out are fixed in the code: the CQL learning rate, the reward scaler and the seed train.py train.py. The LSTM encoder returns the output at the last time step model.py. An implementer who uses other defaults will get a different model.
• Zeroed values from the step factor. Where h^step is 0, the backup is 0 for that pair DP_methods.py DP_methods.py. Because the KPI is mostly negative, a zero value can beat a genuinely negative action. The paper reports unstable results with h^0 and sigQ3 §7.1.
• Quartile thresholds. The code uses NumPy's default quantile method DP_methods.py. The paper does not name a method, and different interpolation rules give different Q1, Q2 and Q3 on small tables.
• Ties in the policy. Ties in q produce several actions per state, and the extraction keeps the last one DP_methods.py DP_methods.py. Break ties explicitly.
• Zero rewards after scaling. Rewards equal to zero before scaling are kept at zero, even when that is not their scaled value DP_methods.py. A terminal transition whose KPI is exactly zero is treated like a non-terminal one.
• Possible index wrap in CQL dataset collapse. When removing environment actions, the code writes the reward into index i − 1 dataset.py. If the first transition is an environment action, index −1 wraps to the last transition. Check the first transition of the dataset.
• Mask percentile. The paper says successors below the 20th percentile are removed §5.2. The code computes the percentile over each source activity's successor counts, not over all edges dataset.py. The paper's wording allows this reading, but a global percentile would remove different successors.
• Empty masks. If an activity has no allowed successor, the released agent raises an exception cql_agent.py. Handle it in your own code.
• Environment merging. Each environment event is merged into the event before it, which is then deleted MDPCreator_BPI_cluster.py. The paper describes this in one sentence §5.1.1 step 1. Repeated events are kept by default MDPCreator_BPI_cluster.py, which the paper does not discuss.
• KPI shapes behaviour. The KPI ignores repayment, risk and processing capacity. The best learned policy accepts all applications §7.1. The paper says rejections are never rewarded, and that the choice of KPI determines the policy §8.
• Costs and scaling. Clustering and MDP construction both grow with log size. Value iteration takes seconds. CQL costs about 30 minutes per epoch, and the paper reports no clear dependence on log size §7.3.
• Inference start token. Inference prepends START cql_agent.py. Make sure training windows also start with START, which the logs contain utils.py.
• Real-log results depend on the simulator. The real-log numbers come from simulation models discovered from the test split. The decision-tree variant changes the ranking of policies §7.2. Read the two simulation columns separately.

Lineage

• Builds on: the authors' earlier MDP-from-logs work, cited as us@BPM22. This paper generalises its scaling to end-of-trace rewards §5.1.2. The CQL method is taken from the offline-RL literature §4.2.
• Compared against: the customary policy and the informed heuristic in simulation §6.3. The MDP and CQL methods are compared with each other §7.2.
• Superseded by: not stated.