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

| cite | improve this question | | | | |

Your Answer

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

Browse other questions tagged or ask your own question.