Reinforcement Learning algorithm for Optimized Trade Execution
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.