# Estimating model for transition probabilities of a Markov Chain

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?

• Is the number of Xs known, or are they just some function of the states and hidden variables? – jkm Feb 19 '20 at 14:14
• Yes, if I understand your question, I have $K$ matrices $X$. Each one gives one caracteristica associated with of a state s in a time t. In the example, the matrix $X_F$ gives the amount of food in each state. So, each matrix $X$ is associated with one explicative variable that I want to use to build a model for transition probabilities. – DanielTheRocketMan Feb 19 '20 at 14:45
• To make sure I've understood correctly...it sounds like your Markov chain obeys a different transition matrix at each timepoint. You want to express the transition matrix at each time $t$ as a function of some regressors at time $t$. The parameters of this function are constant across time. You somehow know the 'true' transition matrices at every timepoint, which will be used as targets to fit the function (rather than an observed series of states generated by the system). Is this correct? – user20160 Feb 19 '20 at 14:50
• Correct. That is exacly the model I am looking for. Furthermore, I am assuming that the parameters of the regressors are also the same for each state. I mean the regressors affect the same way all states, but maybe the parameter (coeficient) associated with the constant may be different for each state (like a fixed effect). – DanielTheRocketMan Feb 19 '20 at 14:55
• In a Markov Decision Process, you'd be adjusting the S->S' transition weights subject to optimize for some loss function, here you're using S->S' data to regress the weights and kinda-sorta infer the original loss function. – jkm Feb 19 '20 at 22:27

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).