Reinforcement Learning algorithm for Optimized Trade Execution

Question

My question deals with the algorithm described in the paper: Reinforcement Learning for Optimized Trade Execution

This paper uses reinforcement learning technique to deal with the problem of optimized trade execution. They divide the data into episodes, and then apply (on page 4 in the link) the following update rule (to the cost function) and algorithm to find an optimal policy:

(T is the total time units, I is the volume, L is the possible number of actions, x represents the state, and c represents the cost function, and c_im is the immediate reward at a certain state and a certain action. n is the number of times that the state-action pair were visited)

Here are my questions:

If I understand correctly, the algorithm is basically a dynamic programming, when we move backwards in time.

1. Why do we need n in the cost function update rule. Aren't we visiting each state exactly once?

2. If I understand correctly, we should run this algorithm on every episode (in the experiment in the paper they had 45000 episodes). In such case, how do we combine the results from all the episodes? That is, each episode provides an optimal policy. How do we combine all these policies to one final policy?

Answer 1

Why do we need n in the cost function update rule. Aren't we visiting each state exactly once?

The update is assuming a static distribution and estimating the average value. As each estimate is made available, it is weighted less of the total each time. The formula means that the first sample is weighted $1$, second $\frac{1}{2}$, third $\frac{1}{3}$ which is what you need to get the mean value when you apply the changes due to the samples serially whilst maintaining the best estimate of the mean at each step.

This is a little odd in my experience of RL, because it assumes the bootstrap values (the max over next step) come from a final distribution to weight everything equally like this. But I think it is OK due to working back from final step, hence each bootstrap value should be fully estimated before going backwards to previous time step.

If I understand correctly, we should run this algorithm on every episode (in the experiment in the paper they had 45000 episodes)

This looks like an algorithm that you run on the whole data set, where each episode is the same length $T$. So you run each timestep (starting with the end time step and working backwards since the ultimate reward is established at the end of the episode, so this is more efficient), and sample from every episode at that timestep in the While (not end of data) loop. The values are therefore combined inside the loop at that stage, and there is no need to add anything to the algorithm to combine episodes.