Estimating model for transition probabilities of a Markov Chain

Question

Suppose that I have a Markov chain with $S$ states evolving over time. I have $S^2\times T$ values of the transition matrix, where $T$ is the number of time periods. I also have $K$ matrices $X$ of $T\times S$ values of (independent) variables, where $K$ is the number of variables that I can use to explain the transition probabilities ($p_{ij}$ are my dependent variables and the matrices $X_k$ are the independent variables).

Remember that $\sum_j p_{ij}=1$ for each $t$.

In the end, I am looking for panel models to explain the transition probabilities, where the parameters are constant over time and (with maybe exception the constant) the parameters are also constant over different transition probabilities.

Just to be clear ... Consider the following example ... Imagine that an animal prefers to stay in places that there are food and water. Let the $T\times S$ matrix $X_F$ the matrix that tells the amount of food in each place $s\in S$ and in each time $t\in T$ and $X_W$ the matrix that tells the amount of water in each place $s\in S$ and in each time $t\in T$.

I want to use $X_F$ and $X_S$ to explain the transition probabilities. I do have the values of the transition probabilities over time and I want to use these matrices to explain their values.

I think I can design a kind of fixed effect logit model for each state in $S$. However, I would have to estimate $S$ logit models. I believe that the probabilities $p_{ij}$ and $p_{ji}$ should not be estimated in different models, since they seem to be related.

Any hints? Are there solutions in the literature of such kind of problem?

Answer 1

As jkm pointed out, this sounds like an inverse reinforcement learning problem.

Reinforcement Learning

If you are familiar with operant conditioning from behaviorist psychology, reinforcement learning is essentially an operationalization of this theory in the form of a stochastic control process. This discrete-time Markov decision process $\mathcal{M} = (S, A, T, P_{t}, R_{t})$ consists of a Markov chain with some extra structure:

• $S$ is a finite set of states
• $A = \underset{s \in S}\bigcup A_{s}$, where $A_{s}$ is a finite set of actions available for state $s$
• $T$ is the (countable cardinality) index set representing time
• $\forall t \in T$, $P_{t}: (S \times A) \times S \to [0, 1]$ is a family of conditional transition probabilities. Considering some fixed time $t \in T$, we can write this more concretely element-wise as $P_{t}(s, a, s') = P_{a_{t}}(s, s') = P(s_{t+1} = s' | s_{t} = s, a_{t} = a)$ (apologies for the notation here)
• $\forall t \in T$, $R_{t}: (S \times A) \times S \to \mathbb{R}$ is the 'reward' function associating transitions between states under available actions. Element-wise for a fixed time $t \in T$ this is a bit more succinctly written as the real-valued function $R_{a_{t}}(s, s')$.

In the standard reinforcement learning problem, the task is to solve for the optimal policy of actions to take at any given state in order to asymptotically maximize the total reward. A policy $\pi$ can be written as a probabilistic decision rule:

• $\pi: A \times S \to [0, 1]$, or element-wise as $\pi(a, s) = P(a_{t} = a | s_{t} = s)$. Note that the policy $\pi$ is no longer indexed by $t$ - in other words, the optimal decision policy is a stationary distribution of the process.

Under the optimal policy (assuming one exists), the value function is the expected reward earned from following the optimal policy. This is usually weighted by an exponential decay in order to place greater emphasis on more recent rewards, but that choice is reflective of how you model rewards. Using this exponentially decaying discount-rate $\gamma$, the value function $V_{\pi}$ has the form:

• $V_{\pi}(s) = E\bigg[\sum\limits_{t=0}^{\infty}\gamma^{t}R_{t}|s_{0} = s\bigg]$, where $s_{0}$ is the starting state and $\gamma \in [0, 1]$ is the discount-rate which exponentially decreases the importance of older rewards.

So in standard reinforcement learning, you want to solve for a policy $\pi$ that lets you achieve $V_{\pi}$, or as close to it after your sub-optimal initial period of time before converging to $\pi$.

Inverse Reinforcement Learning

The inversion here is in terms of which functions you know and which functions you have the goal of solving for. In the inverse problem, you know $\pi$ and you want to solve for $R_{t}$. This sounds pretty much like your problem: you have observed the actual transition probabilities, and some quantities related to the actions taken (the food and water quantities in your example), but you want to solve for the reward associated with these quantities that best explains the observed transitions.

As you might expect, unfortunately the inverse reinforcement problem is a bit more complicated than the (already complicated) forward problem. The most obvious difficulty is that the true reward function is not typically available in practice, so a straightforward loss metric against the 'ground-truth' is unavailable in this case. Another problem is that under most formulations, the reward function is essentially under-determined - there are many reward functions that can generate the observed transitions and optimal policy. So, in order to be soluble, some further constraints are typically imposed. If you check the first reference [1], some of the most well-developed approaches are described starting in section $4$. There are basically four types of approaches as outlined there:

• Maximum-margin methods, which introduce a bias in learning the reward function. The bias is obtained from some prior knowledge. One method in this class is called apprentice learning, and requires the trajectory of an 'expert' through the decision process.
• Information theoretic approaches which seek the least-wrong solution. This is done by way of the principle of maximum entropy, and the methods are formulated in terms of likelihood maximization[3].
• Bayesian approaches, where a posterior distribution over reward functions is the tool used. The form of the posterior function defines the particulars of this method, and there is some overlap with the information theoretic approaches. One posterior update function used before is logistic function[2], which sounds like it may be similar to your fixed-effect method.
• Regression approaches. The dependent variable is either the components of the value function or some transformation of them.

I would definitely read through the first reference, as it gives a nice review of the problem and previously adopted approaches, and also contains a lengthy set of references itself (I'm in the process of going through them myself).

References

1. Arora, S. and Doshi, P., 2018. A survey of inverse reinforcement learning: Challenges, methods and progress. arXiv preprint arXiv:1806.06877.

2. Ramachandran, D. and Amir, E., 2007, January. Bayesian Inverse Reinforcement Learning. In IJCAI (Vol. 7, pp. 2586-2591).

3. Ziebart, B.D., Maas, A.L., Bagnell, J.A. and Dey, A.K., 2008, July. Maximum entropy inverse reinforcement learning. In Aaai (Vol. 8, pp. 1433-1438).