Q-learning works with a 2D SxA table of Q values, where S is the current state and A is the action taken. Is there some model-based variant of Q-learning (or SARSA) that uses a 3D SxAxS' table to store Q values, where S' is the resulting state?

A similar table may be used to learn models in discrete environments, but in this case you don't store Q values, but counts.

I couldn't find anything like this, either because I don't know the correct terms to search for, or because it does not exist. It doesn't matter to me if it is useful or not, I just need to know if it exists, and if it exists, how is it called.

  • $\begingroup$ It might be worth explaining your use case, because there could be something already inherent to existing table you are not understanding that could be clarified. Probably quite critically, the agent doesn't get to choose S', just A, so it generally makes sense to calculate expected return q(S,A) - if you are in a scenario where the agent gets to somehow know probabilities of landing on S', you can address that by modifying S (to include the factors that allow the agent to know). If somehow the agent gets to control which S' to land on, then that should be part of A. $\endgroup$ – Neil Slater Apr 20 '16 at 18:42
  • $\begingroup$ I'm talking about model-based learning, just updated the title and description to clarify. $\endgroup$ – rcpinto Apr 20 '16 at 19:08
  • $\begingroup$ I'm still not sure of your use case. You want the model to use S,A,S' tuples, but to what end? Are you wanting to predict distribution of S' from S,A using the model (and presumably it is non-deterministic and inaccessible whilst the learner is exploiting what it has learned)? $\endgroup$ – Neil Slater Apr 21 '16 at 8:27
  • $\begingroup$ If you are needing to predict S' from the model, then just perhaps you are looking to combine Reinforcement Learning with Planning systems? So this might help: lpis.csd.auth.gr/publications/rlplan.pdf $\endgroup$ – Neil Slater Apr 21 '16 at 8:32

The concept of state-action values $Q$ is to denote how good is to be in a particular state and perform a particular action in terms of expected future reward. From what I understand from your question, you are interested in the problem of model uncertainty (uncertainty on the dynamics of the system). In other words, our artificial agent interacts within an unknown environment (transition dynamics $T(s,a,s')$ and reward dynamics $R(s,a)$ or $R(s,a,s')$ are unknown).

The framework you should take a look at is Bayesian Model-based RL. I outline an approach so you can have an idea:

Modelling Transitions

First assume that we have uncertainty on the transitions of the environment $T(s,a,s')$. To tackle this we will assume that our agent maintains a distribution over possible transitions. Without getting into the theoretical math, I will illustrate this by using a simple Dirchlet-Multinomial model:

The states are sampled from a Multinomial likelihood $s'\sim Mult(p_{ss'}^{a})$ and we assume a prior over the transitions $p_{ss'}\sim Dir(\alpha)$, where $\alpha$ is set to $1/|\cal{S}|$, where is $\cal{S}$ is the state space. The posterior over transitions will be also a Dirichlet because of the conjugacy of the likelihood and prior distributions. To update such a posterior you need to perform simple algebraic calculations and maintaining the counts of each transition.

The Algorithm

The agent does two processes:

  • (Simulation or Planning phase) Samples an MDP from the posterior over transitions (in the first iteration you sample from the prior distribution). Having a 'fixed table of tranistions' solves the sampled MDP (e.g with Value iteration) and selects the optimum action.
  • (Real-world interaction phase) In the real world, you observe the reward of your action and the new state of the environment. You update the posterior counts.

Eventually, and if you have chosen an appropriate distribution for your domain the agent will adapt to the unknown environment. Of course richer priors with non conjugacy will lead to MCMC sampling methods. I refer you to this paper to get an overview of the problem: Model-based Bayesian Exploration and the quite advanced: Bayes-Adaptive MDPs for further research and exploration.


You can take a look at fitted Q iteration (here is the pdf) which is a sort of model based Q learning. I am not sure if this is exactly what you are looking for.


Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.