Does a policy depend on the past?

Question

I am wondering about the mere definition of the word 'policy'. Let us sassume that we have a finite space of states $S$ and a finite set of actions $A$. People tend to write that it is a 'stochastic function'

$$\pi : S \to A$$

i.e. what they mean is that we have a function $\pi^{(d)} : S \times A \to [0,1]$ such that for every $s \in S, \sum_{a \in A} \pi^{(d)}(a) = 1$ and the agent samples its next action according to this distribution, i.e. $P[A_t = a|S_t = s] = \pi^{(d)}(s, a)$ in the Markov process.

One of the first examples given in this area is the N-armed bandit. I.e. there are $N$ one-armed bandits $B_1, ..., B_N$ and every single one $B_i$ gives a reward distributed like $\mathcal{N}(\mu_i, \sigma_i)$ when pulled. The underlying probabilistic state machine (or whatever you want to call it) has just one reflexive state and all actions $B_1, ..., B_N$ lead back into that single state.

The first strategy ones comes up with is the greedy one: Pull some random arms $a_0, ..., a_w$, collect rewards $r_0, ..., r_w$ for a while and then at each time $t$ for each bandit $B_j$ compute

$$ p_j = \frac{\sum_{\substack{i \in \{0,...,t-1\} \\ a_i = B_j}} r_i}{\sum_{\substack{i \in \{0,...,t-1\} \\ a_i = B_j}} 1}$$

(i.e. compute the mean reward in the past that you received from $B_j$) and then pull $B_j$ that has the highest $p_j$.

However, now the action $a_t$ taken at time $t$ does not only depend on the single state in the automata but rather on all the past observations. In fact, that is the whole point in reinforcement learning: For a current state, check which states were similar in the past and check which action the agent took at that past time and from that somehow conclude what would be the smartest thing to do now.

---

So, it appears to me that the policy depends on much more than the current state: it depends on all the past states and all the past rewards ... So how come that one can simplify it like $\pi(s)$ or $\pi(a|s)$ when in fact one should write $\pi(a_t|s_t, ..., s_0, r_{t-1}, ..., r_1)$?

---

NB: It seems to me that there is a hidden concept of 'rounds'/matches involved in here. For example: when one wants the computer to learn to play pong using a neural network then one starts with a neural network and fixes that neural network for the whole round. In that sense, it is feeded the current state $s$ and samples an action $a$ from it. Only after the current match is finished one updates the weights of the neural network (multiplied by a factor depending on whether or not the game was won). So somehow a policy is a weird thing that is like $\pi(a|s)$ during one 'match' but the agent is allowed to change after one 'match' but then one needs to specify and formalize 'match' (i.e. start states and end states and how they are connected, etc). This seems a little complicated.

Answer 1

In think you are conflating the idea of the policy, with how some types of policy are learned.

The two are usually kept separate, and you can either have the concept of a "current policy" $\pi(a|s)$ or you might use a subscript $\pi_t(a|s)$ if you are explaining how policy changes from step to step in an online environment. Not all RL agents work purely online, or have a simple way to express how they change from step to step though. In fact not all policies have anything to do with RL - the existence of a policy function is independent of how that function is arrived at.

The current policy may well be determined through experience of the agent, but that is not usually considered "part of" the policy function. Instead the policy is viewed as a function that can be changed arbitrarily, by changing its parameters. In RL this is usually done either by directly modelling the function (as in policy gradient methods like REINFORCE) or via a learned value function (as in value methods, like Q learning), and then learning through updates based on experience.

There is no requirement for a policy to depend on experience in any particular way, and RL theory does usually not require tracking the dependency of policy on history to the degree where your suggested notation would be useful. To be complete, your suggested notation may also need the history of all the actions, the starting policy and/or its parameters, any hyper-parameters of learning, the type of RL algorithm being used. In addition, the influence of all this history is already summarised in the Q table or estimated q function or parameters of the policy function - reminding yourself of that in the notation is really optional, because how this dependency works is often already captured by shorter notation.

You may see, for policy gradient methods, the notation $\pi(a|s, \theta)$ or $u(s, \theta)$ or similar to represent the policy. The parameters $\theta$ of the function being learned are made explicit in those cases precisely because this is a useful detail to be reminded of. Of course $\theta$ is very likely dependent on the history of the agent etc as before, but there is little benefit from making this explicit, when $\theta$ completely sums up the influence that this history has had.

Answer 2

After thinking about this for a little longer I found the following answer in Puterman, Markov Decision Processes, chapter 6:

Policies can be divided by two 'features' into four categories:

• are they Markovian (yes/no)
• are they stationary (yes/no)

If a policy is non Markovian then it indeed depends on the whole history and we then have two write expressions like $\pi(a_t|r_{t-1},s_{t-1},a_{t-1}, ..., s_0)$.

Stationary refers to whether or not the policy depends on the time $t$, i.e. a olicy could consist of multiple small policies $\pi = (\pi_0, \pi_1, ...)$ and at time $t$, $\pi$ involves $\pi_t$.

Both seem to make policies much more general, i.e. allowing access to the whole past should make the policy better, right? Also, making decisions based on the time should generally improve the quality of the policy, right?

Turns out: No. Under suitable conditions, the optimal policy is a deterministic, Markovian, stationary one, i.e. given a 'general', non Markovian, non stationary policy, you will always find a better one that actually is stationary and Markovian (and even deterministic).

Does that mean we can eliminate history dependent and/or non-stationary policies from our heads and from the theory? No! Why? Because you need these policies as 'intermediate steps' on your way towards the best policy.

Example 1: n-armed Bandits. Given a single state $s$ and actions $A_1, ..., A_N$ (that are the 'arms' of the bandit that you can pull) and attached rewards that only depend on the actions and are normally distributed like $\mathcal{N}(\mu_j, \sigma_j)$ for $j=1,...,N$, the best policiy is obviously to always pull the arm $A_j$ such that $\mu_j$ is maximal. However: given that the agent does not know ad hoc which mean is the best, it needs to figure that out using trial and error and one of the most used strategies actually is to approximate the means for each action $A_j$ empirically, i.e. sum the rewards that you received by pulling $A_j$ and divide by the amount of pulls.

Example 2: RNNs. Another strategy how to solve RL problems is using neural networks. Without going into the details of how RNNs work they have a so-called "hidden state". From a practical perspective, 'hidden' is the wrong word, because you can always see it as the programmer of that neural net, so lets call it 'internal'. This internal state is being updated after an episode and is being dragged along when playing, for example, one session of a game. Hence, RNNs descrivbe non Markovian policies!

Answer 3

It seems you are asking wrong question. How I understood it - you are asking why RL even bothers with markov process because (you think) all processes are non markovian (that much you said). I can't answer that because it's absurd.

However if you have a problem which fits into "RL with non markovian rewards" the answer is yes you have chance to solve it.

One paper I like on this : https://ojs.aaai.org/index.php/AAAI/article/view/5814