RPChe_'s Blog

Planning and Deterministic Policies

• Planning means the external environment is completely known. An important fact is that under this circumstance only deterministic policies are needed in achieving optimality. First, it is clear that the structure of state spaces won't matter beacause everything is conditional on states. In RL settings we measure the value of long-term decision processes by returns. At this point of view, if we are at state , we should select the action that maximizes the return, which is exactly the Q-function We assume that the Q-function is completely known. Let , if can be achieved by certain , we know it is absolutely better to choose the action . Otherwise if is not achievable, we can give a brief proof that any stochastic policy can't reach

  Consider any probability measure () over ((A,A)). If then (Q(a)) must be ()-almost surely. In particular, there must exist some (aA) such that (Q(a)=Q'), which contradicts the assumption that (Q') is not attained. Therefore, no such probability measure () exists.

  In other words, the value-function of any stochastic policy , denoted as , must have . While can be approximated by a sequence , stochastic policies won't be any better than deterministic policies.

• So we conclude that deterministic policies are sufficient for planning. By contrast, stochastic policies are useful in learning, since the agent must explore an environment that is not fully known in advance. This gives rise to the exploration-exploitation trade-off: the agent needs to explore in order to acquire information, while also exploiting the information already obtained. In the rest of this installment, we'll only consider deterministic policies.

The Infinite-Horizon Tabular MRP Case

• Consider MRP Let . By definition We expand the probability By Markovian property Note that the state transition kernel is stable, hence Such a form is familiar from dynamic programming. Consider the vectorized version This gives We conclude that in planning problems we can solve for value functions accurately in given invertible.