Book contents
- Frontmatter
- Contents
- 1 Introduction and Overview
- 2 Preface to the Planning Chapters
- 3 Deterministic Decision Processes
- 4 Markov Chains
- 5 Markov Decision Processes and Finite Horizon Dynamic Programming
- 6 Discounted Markov Decision Processes
- 7 Episodic Markov Decision Processes
- 8 Linear Programming Solutions
- 9 Preface to the Learning Chapters
- 10 Reinforcement Learning: Model Based
- 11 Reinforcement Learning: Model Free
- 12 Large State Spaces: Value Function Approximation
- 13 Large State Space: Policy Gradient Methods
- 14 Regret Minimization
- Appendix A Dynamic Programming
- Appendix B Ordinary Differential Equations
- Reference
- Index
5 - Markov Decision Processes and Finite Horizon Dynamic Programming
Published online by Cambridge University Press: 31 July 2026
Book contents
- Frontmatter
- Contents
- 1 Introduction and Overview
- 2 Preface to the Planning Chapters
- 3 Deterministic Decision Processes
- 4 Markov Chains
- 5 Markov Decision Processes and Finite Horizon Dynamic Programming
- 6 Discounted Markov Decision Processes
- 7 Episodic Markov Decision Processes
- 8 Linear Programming Solutions
- 9 Preface to the Learning Chapters
- 10 Reinforcement Learning: Model Based
- 11 Reinforcement Learning: Model Free
- 12 Large State Spaces: Value Function Approximation
- 13 Large State Space: Policy Gradient Methods
- 14 Regret Minimization
- Appendix A Dynamic Programming
- Appendix B Ordinary Differential Equations
- Reference
- Index
Summary
This chapter introduces the fundamental Markov decision process model and develops optimal solution methods for finite-horizon problems. Multiple performance criteria are defined, including finite-horizon return and stochastic shortest-path formulations. A key result establishes that Markov policies are sufficient for optimality. The finite-horizon dynamic programming algorithm is derived from the principle of optimality, computing value functions backwards in time via the Bellman equation. The Q-function representation is introduced.
Keywords
Information
- Type
- Chapter
- Information
- Reinforcement Learning Foundations , pp. 46 - 59Publisher: Cambridge University PressPrint publication year: 2026
Accessibility standard: WCAG 2.2 A
Why this information is here
This section outlines the accessibility features of this content - including support for screen readers, full keyboard navigation and high-contrast display options. This may not be relevant for you.Accessibility Information
The PDF of this chapter
complies with version 2.2 of the
Web Content Accessibility Guidelines
(WCAG), offering more comprehensive accessibility measures for a broad range
of users and meets the basic
(A)
level of WCAG compliance, addressing essential accessibility barriers.
Content Navigation
Table of contents navigation
Allows you to navigate directly to chapters, sections, or non‐text items through a linked table of contents, reducing the need for extensive scrolling.
Allows you to navigate directly to chapters, sections, or non‐text items through a linked table of contents, reducing the need for extensive scrolling.
Index navigation
Provides an interactive index, letting you go straight to where a term or subject appears in the text without manual searching.
Provides an interactive index, letting you go straight to where a term or subject appears in the text without manual searching.
Reading Order & Textual Equivalents
Single logical reading order
You will encounter all content (including footnotes, captions, etc.) in a clear, sequential flow, making it easier to follow with assistive tools like screen readers.
You will encounter all content (including footnotes, captions, etc.) in a clear, sequential flow, making it easier to follow with assistive tools like screen readers.
Short alternative textual descriptions
You get concise descriptions (for images, charts, or media clips), ensuring you do not miss crucial information when visual or audio elements are not accessible.
You get concise descriptions (for images, charts, or media clips), ensuring you do not miss crucial information when visual or audio elements are not accessible.