Value functions for a given MDP can be learned in at least two ways by experience.

  1. The first way (tabular calculation) is generally used in the case of state spaces that are small enough.

  2. The second way (using parameterized functions) is generally used in the case of large state paces.

It can be understood from the following statement from section 3.7 of the first edition of Sutton and Barto's book.

The value functions $V^{\pi}$ and $Q^{\pi}$ can be estimated from experience. For example, if an agent follows policy $\pi$ and maintains an average, for each state encountered, of the actual returns that have followed that state, then the average will converge to the state's value, $V^{\pi}$(s), as the number of times that state is encountered approaches infinity. If separate averages are kept for each action taken in a state, then these averages will similarly converge to the action values, $Q^{\pi}(s,a)$ . We call estimation methods of this kind Monte Carlo methods because they involve averaging over many random samples of actual returns. Of course, if there are very many states, then it may not be practical to keep separate averages for each state individually. Instead, the agent would have to maintain $V^{\pi}$ and $Q^{\pi}$ as parameterized functions and adjust the parameters to better match the observed returns. This can also produce accurate estimates, although much depends on the nature of the parameterized function approximator.

Is there any thumb rule or strict margin, in the literature, on the cardinality of state space to use the parameterized function to estimate value functions?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.