First of all, do we really need to iterate over every state in the state space? We have an environment that can be used as a source of real-life samples of states. If some state in the state space is not shown to us by the environment, why should we care about its value? We can use states obtained from the environment to update values of states, which can save us lots of work.
This modification of the Value iteration method is known as Q-learning, as mentioned earlier, and for cases with explicit state-to-value mappings, has the following steps:
Start with an empty table, mapping states to values of actions.
By interacting with the environment, obtain the tuple s, a, r, s′ (state, action, reward, and the new state). In this step, we need to decide which action to take, and there is no single proper way to make this decision. We discussed this problem as exploration versus exploitation and will talk a lot about this.
- Update the Q(s, a) value using the Bellman approximation...