# Fast algorithms to solve Markov Decision Processes

In my master thesis I used an Algorithm called Approximative Dynamic Programming [1] to solve equations of the form

$$\max_{\pi}\mathbb{E}^{\pi}\left\{\sum_{t=0}^{T}\gamma^tC_t^{\pi}(S_t,A_t^{\pi}(S_t))\right\}.$$

It uses Monte-Carlo sampling and an approximation $\overline{V}_t$ of the value function to come around the curse of dimensionality. As a decision function serves a convex linear program

$$\hat{v}_t^n=\max_{a_t\in A_t^n}\left(C_t(S_t^n,a_t)+\gamma \overline{V}_{t+1}^{n-1}(S^M(S_t^n,a_t))\right),$$

and the update is done by using a stepsize $\alpha$

$$\overline{V}_t^n(S_t^n)=(1-\alpha_{n-1})\overline{V}_t^{n-1}(S_t^n)+\alpha_{n-1}\hat{v}_t^n.$$ I wondered now if they exists similar algorithms, despite the many flavours of this algorithm, to deliver high quality solutions in reasonable time or if the used principle is the only one to solve such kind of problems?

Cheers, Reza

[1] POWELL, W. : Approximate Dynamic Programming: Solving the curses of dimensionality. Bd. 703. Wiley-Blackwell, 2007