BMETE95MM34

Nyomtatóbarát változatNyomtatóbarát változat
Tantárgy azonosító adatok
A tárgy címe: 
Markov döntési folyamatok és megerősítéses tanulás
A tárgy angol címe: 
Markov Decision Processes and Reinforcement Learning
A tárgy rövid címe: 
MarkovDöntésiFolyamatok
2
0
0
v
Kredit: 
3
A tantárgy felelős tanszéke: 
Sztochasztika Tanszék
A tantárgy felelős oktatója: 
Dr. Simon Károly
A tantárgy felelős oktatójának beosztása: 
egyetemi tanár
Akkreditációs adatok
Akkreditációra benyújtás időpontja: 
2018.11.20.
Akkreditációs bizottság döntési időpontja: 
2018.11.27.
Tematika
A tantárgy szerepe a képzés céljának megvalósításában: 
Alkalmazott Matematikus és Matematikus MSc szabadon választható tárgya
A tantárgy részletes tematikája magyarul és angolul: 

General theory of MDPs:

Basic concepts of Markov Decision Processes (MDPs), main types such, as stochastic shortest path, total discounted and average (ergodic) cost problems. Control policies, value functions, Bellman operators and their core properties, monotonicity, contraction, optimality equations, greedy policies and approximation possibilities. Existence and properties of optimal control policies.

Standard RL methods for MDPs:

Main solution directions of MDPs: iterative approximations of value functions (e.g., value iteration, Q-learning, SARSA); direct search in the space of policies (e.g., policy iteration, policy gradient); linear programming formulation, complexity. Generalizations: unbounded costs, partial observability.

Temporal difference (TD) learning based policy evaluations: Monte Carlo methods, eligibility traces, TD(0), TD(1) and TD(lambda): online, offline, first-visit, every-visit variants, convergence theorems, optimistic policy improvements. Examples, like Q-learning for SSPs. Off-policy policy evaluations.

Small-sample theory for RL:

Multi-armed bandit problems, exploration-vs-exploitation, regret, Hannan consistency, canonical bandit model, subgaussian bandits, explore-then-commit algorithm, upper confidence bound (UCB) algorithm, the optimism principle, regret bounds for UCB, asymptotic optimality of UCB, contextual bandits, stochastic linear bandits, confidence regions for bandit problems, online confidence sets.

Large-sample theory for RL:

General adaptive algorithms and stochastic approximation (SA), fixed point and root finding problems. Examples of classical SA algorithms with analogous methods in RL: Robbins-Monro (e.g., Q-learning), Kiefer-Wolfowitz (e.g., policy gradient), SPSA (simultaneous perturbation stochastic approximation), stochastic gradient descent (SGD) and its acceleration methods (e.g., momentum).

Asymptotic analysis of general adaptive algorithms assuming martingale difference noise sequences. Convergence results based on Lyapunov (potential) functions. Applications to classical examples: SGD with Lipschitz continuous gradient and Euclidean norm pseudo-contractions. Convergence analysis based on contraction and monotonicity properties, and their illustration through RL examples.

Recommended literature:

  • Bertsekas D. P. & Tsitsiklis J. N.: Neuro-Dynamic Programming, Athena Scientific, 1996.
  • Lattimore, T. & Szepesvári, Cs.: Bandit Algorithms, Cambridge University Press, 2018.
  • Feinberg, A. E. & Shwartz, A. (eds.): Handbook of Markov Decision Processes, Kluwer Academic Publishers, 2002.
  • Kushner, H. & Yin, G.: Stochastic Approximation and Recursive Algorithms and Applications, 2nd edition, Springer, 2003.
  • Sutton, R. S. & Barto, A. G: Reinforcement Learning: An Introduction, 2nd edition, MIT Press, 2018.
Követelmények vizsgaidőszakban: 
vizsga
Pótlási lehetőségek: 
TVSZ szerint
Konzultációs lehetőségek: 
oktatóval történő megegyezés szerint
Jegyzet, tankönyv, felhasználható irodalom: 
Bertsekas D. P. & Tsitsiklis J. N.: Neuro-Dynamic Programming, Athena Scientific, 1996.
Lattimore, T. & Szepesvári, Cs.: Bandit Algorithms, Cambridge University Press, 2018.
Feinberg, A. E. & Shwartz, A. (eds.): Handbook of Markov Decision Processes, Kluwer Academic Publishers, 2002
A tárgy elvégzéséhez átlagosan szükséges tanulmányi munka mennyisége órákban (a teljes szemeszterre számítva)
Kontakt óra: 
28
Félévközi felkészülés órákra: 
28
Felkészülés zárthelyire: 
0
Zárthelyik megírása: 
0
Házi feladat elkészítése: 
0
Kijelölt írásos tananyag elsajátítása (beszámoló): 
0
Egyéb elfoglaltság: 
0
Vizsgafelkészülés: 
34
Összesen: 
90
Ellenőrző adat: 
90
A tárgy tematikáját kidolgozta
Név: 
Dr. Csáji Balázs Csanád
Beosztás: 
tudományos főmunkatárs
Munkahely (tanszék, kutatóintézet, stb.): 
MTA SZTAKI
A tanszékvezető neve: 
Dr. Simon Károly