3
$\begingroup$

A Markov decision process is typically described as a tuple $\langle A,U,T,R \rangle $ where

  • $A$ is the state space
  • $U$ is the action space
  • $T: A \times U \times A \mapsto [0,\infty) $ is the state transition probability function
  • $R:A \times U \times A \mapsto \mathbb{R}$ is the reward function

What does this $A \times U \times A$ actually mean in terms of the MDP? It is written in all the papers, but never explained. Does it mean that all the states $a \in A$ are multiplied with all the action $u \in U$? Or something completely different?

$\endgroup$
  • $\begingroup$ This seems to be a pure mathematics question. Unless there is an explicit connection to computer science topics, such questions are better suited to Mathematics. $\endgroup$ – Raphael May 21 '16 at 19:32
  • 1
    $\begingroup$ Pedantic comment: $\mapsto$ (the symbol for the function itself) is the wrong symbol here. You want to use $\to$ here, which is the symbol for specifying the domain and codomain. $\endgroup$ – Mehrdad May 22 '16 at 1:13
  • $\begingroup$ @Mehrdad that I did not know. Thanks. $\endgroup$ – Astrid May 22 '16 at 13:05
4
$\begingroup$

The notation $T\colon A\times U\times A\to[0,\infty)$ means a function with three parameters, the first from $A$, the second from $U$, and the third from $A$, which outputs a non-negative real.

It is somewhat strange that the range is stated as $[0,\infty)$ rather than $[0,1]$. In fact, a perhaps better way of thinking of $T$ is as a function from $A \times U$ to the set of distributions over $A$. That is, $T$ gets a state and an action, and outputs a distribution over the set of states.

The semantics of $T$ are as follows: when at state $a$ and performing action $u$, the probability of moving to state $b$ is $T(a,u,b)$. Thus for all $a \in A$ and $u \in U$ we must have $\sum_{b \in A} T(a,u,b) = 1$.

$\endgroup$
4
$\begingroup$

Elements of $A\times U\times A$ are triples $(a_1,u,a_2)$, where $a_1$ and $ a_2$ are elements of $A$ and $u$ is an element of $U$. The $\times$ gives the Cartesian product of its arguments.

$\endgroup$

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.