EDIT: The linked questions do not answer my question. My question is, how is reward incorporated into the following algorithm to make it improve iteratively When the target reward is random.

Following are the steps specified for deep Q learning in the book 'Deep Reinforcement Learning Hands-On' by 'Maxim Lapan'. These steps are based on the original deepmind paper, I think.

  1. Initialize the parameters for 𝑄𝑄(𝑠𝑠, π‘Žπ‘Ž) and 𝑄𝑄̂(𝑠𝑠, π‘Žπ‘Ž) with random weights, πœ€πœ€ ← 1.0, and empty the replay buffer.
  2. With probability πœ€πœ€, select a random action, a; otherwise, π‘Žπ‘Ž = arg maxπ‘Žπ‘Ž 𝑄𝑄(𝑠𝑠, π‘Žπ‘Ž).
  3. Execute action a in an emulator and observe the reward, r, and the next state, s'.
  4. Store transition (s, a, r, sβ€²) in the replay buffer.
  5. Sample a random mini-batch of transitions from the replay buffer.
  6. For every transition in the buffer, calculate target y = r if the episode has ended at this step, or 𝑦𝑦 = π‘Ÿπ‘Ÿ + 𝛾𝛾 max π‘Žπ‘Žβ€²βˆˆπ΄π΄ 𝑄𝑄̂(𝑠𝑠′ , π‘Žπ‘Žβ€² ) otherwise.
  7. Calculate loss: β„’ = (𝑄𝑄(𝑠𝑠, π‘Žπ‘Ž) βˆ’ 𝑦𝑦)2.
  8. Update Q(s, a) using the SGD algorithm by minimizing the loss in respect to the model parameters.
  9. Every N steps, copy weights from Q to 𝑄𝑄̂.
  10. Repeat from step 2 until converged.

Essentially you start with a two random networks Q and Q_hat and use Q_hat to generate labels to train Q. After a while you migrate all params from Q to Q_hat and this continues.

Essentially, you start with random network (say Q_hat_0), so labels (values for each state/action pair) created by that network is probably random. And then you train Q against those random labels. After a while, Q is probably good at creating those 'random' labels at which point you copy params from Q to Q_hat (let's call this q_hat_1). Now Q_hat_1 is no longer random, but it is good at creating labels that were 'probably wrong' in the first place. And then you re-start this cycle.

This looks like cheating, but I know it is not as it works. I like to understand how this works and if possible, some kind of mathematical proof that this system converges to predict correct values for state/action pairs.

  • 1
    $\begingroup$ It is not guaranteed to converge. Q-Learning only converges with tabular MDPs or linear function approximations (assuming some other conditions are met). For a non-linear function approximator, it is not guaranteed to converge (at least, nobody has yet been able to show this). As you say, it does seem to work in practice, so perhaps one day there will be a rigorous proof, if not of absolute convergence then perhaps with some lower bound on performance. $\endgroup$ Jan 19 at 17:21