Methods of Machine Learning and their Application. The Basics of Markov Decision Processes and Reinforcement Learning

Table of Contents

1 Introduction

1.1 Outline

2 Basics of MDPs and RL

2.1 Markov Decision Processes

2.1.1 Markov Process

2.2 Value Function

2.3 Policy Iteration

2.4 Reinforcement Learning

2.4.1 Monte Carlo Learning

2.4.2 Temporal difference Learning

3 Cleaning Robot Application

3.1 Introduction

3.2 Solving via Value Iteration

3.3 Solving via Monte Carlo Learning

3.4 Solving via Q-Learning

3.5 Comparison of Results

4 Discussion

Research Objectives and Key Themes

This thesis investigates the mathematical foundations of Markov Decision Processes (MDPs) and Reinforcement Learning (RL) algorithms. The primary goal is to evaluate different learning strategies—specifically Value Iteration, Monte Carlo Learning, and Q-Learning—by applying them to a practical simulation of a cleaning robot navigating an apartment to locate dust accumulation.

• Mathematical formalization of Markov Decision Processes (MDPs)
• Comparative analysis of model-based vs. model-free learning
• Implementation of Value Iteration for optimal policy derivation
• Evaluation of Monte Carlo and Q-Learning algorithms
• Performance benchmarking in a simulated spatial environment

Extract from the Thesis

Summary of Chapters

Introduction: Provides a high-level motivation for reinforcement learning using a simple maze analogy and outlines the two-part structure of the thesis.

Basics of MDPs and RL: Establishes the theoretical framework including Markov processes, the Bellman equation, and foundational learning algorithms.

Cleaning Robot Application: Demonstrates the practical implementation and comparison of Value Iteration, Monte Carlo Learning, and Q-Learning in a simulated home environment.

Discussion: Reviews the findings, highlights the commonalities between the algorithms, and identifies future directions such as Deep Q-Learning.

Keywords

Reinforcement Learning, Markov Decision Processes, Value Iteration, Monte Carlo Learning, Q-Learning, Policy Iteration, Bellman Equation, Model-based Learning, Model-free Learning, Agent, Reward Signal, Discount Factor, Off-policy Learning, Temporal Difference, Simulation.

Frequently Asked Questions

What is the core focus of this bachelor thesis?

The thesis focuses on explaining Markov Decision Processes (MDPs) and their application through Reinforcement Learning (RL) algorithms, shifting from theoretical foundations to a practical implementation.

Which specific reinforcement learning methods are presented?

The thesis presents three primary methods: Value Iteration, Monte Carlo Learning, and Q-Learning.

What is the primary goal of the research?

The goal is to demonstrate how these algorithms can be used to derive an optimal policy for an agent, specifically a cleaning robot, to navigate an environment and find a target destination (the location of dust).

What scientific approach does the author take?

The author emphasizes a mathematical point of view for understanding these algorithms, rather than focusing purely on computer science implementations.

What is covered in the main body of the work?

The main body covers the mathematical definitions of MDPs, the transition matrix, state-value and action-value functions, the Bellman expectation equation, and the subsequent implementation of these concepts in Python for a simulated robot.

Which keywords best characterize this work?

Key terms include Reinforcement Learning, MDP, Q-Learning, Monte Carlo, Value Iteration, and optimal policy.

Why is Value Iteration described as model-based?

It is model-based because the agent requires prior knowledge of the environment's dynamics, specifically the transition probabilities and reward functions, to compute the optimal results.

What are the advantages of Q-Learning mentioned in the thesis?

Q-Learning is highlighted for being an off-policy algorithm, having lower variance than Monte Carlo methods, and the ability to learn online from incomplete episodes.

How is the environment of the cleaning robot modeled?

The environment is modeled as a grid-based apartment with 7 rooms, where the agent receives a reward of 1 when reaching the child's room (where dust is present) and 0 or -1 elsewhere.