Reinforcement Learning algorithm for Optimized Trade Execution

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?

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.

• Great Answer! So when averaging in the update rule, are we averaging over episodes? That is, if there was only one episode, we would just always take n=0? In addition, just to make sure I understand correctly: At t=T, for a specific triple (t,v,a), would the value of c(t,v,a) be just the average of the rewards that I get from the all the episodes? – Miriam Farber Aug 20 '17 at 1:25
• And more generally, there is no randomness in the process right? This is just a usual backward dynamic programming. That is, if I run the algorithm several times on the same data I would get exactly the same results, right? – Miriam Farber Aug 20 '17 at 1:29
• @MiriamFarber We are averaging for each action-state value samples over all visits; $n$ should be a count of how many times the state action pair has been seen so far in the training data, regardless of timestep or episode. I agree that I don't see any randomness, unless there is any in the Simulate transition x -> y line – Neil Slater Aug 20 '17 at 8:53
• Timestep is part of the state definition (in the most basic case x=(t,v)), so if we have N episodes, aren't we visiting every state action pair exactly N times? That is, isn't the row "update c(t,v,a)" visited once per episode? Are there any additional visits of the action pair state besides the update row? (also I think there is a typo in the algorithm from the paper and i should be replaced by v). – Miriam Farber Aug 20 '17 at 9:39
• @MiriamFarber: Yes in this specific case, each state/action is visited max once per episode because the state includes time step. That is not true in general for reinforcement learning though. – Neil Slater Aug 20 '17 at 9:45