[RL1] Markov Decision Process – Introduction

[RL1] Markov Decision process – Introduction
[RL2a] Markov Decision Process – Discounted Reward
[RL2b] Markov Decision Process – Bellman equation
[RL2c] Markov Decision Process – Solving Bellman equation
[RL3] Q-Learning
[RL4] Game Theory – overview

Đây là bài đầu tiên trong chuỗi bài về Reinforcement Learning. Đáng lẽ sẽ viết về Bayesian Optimization trước khi chuyển qua đề tài mới, nhưng vì Reinforcement Learning hay quá nên không kiềm chế được. Theo kế hoạch thì sẽ cố gắng viết 4 bài trước, sau đó có thể sẽ viết thêm về Game Theory, hoặc Deep Reinforcement Learning, tuỳ tình hình học bài tới đâu. Bayesian Optimization sẽ viết sau, khi nào có thời gian.

Cách dễ nhất để nghĩ về Reinforcement Learning chắc là ứng dụng điều khiển robot. Đại loại là một robot (gọi chung là agent) hoạt động trong một thế giới gồm N trạng thái. Có thể hiểu mỗi trạng thái là một vị trí mà robot có thể đi tới. Trong số các trạng thái này, có một số trạng thái đặc biệt mà khi robot đi vào đó thì trò chơi kết thúc: robot tìm được báu vật, hoặc bị giết. Tại mỗi trạng thái, robot sẽ được tặng một phần thưởng nhỏ nào đó (gọi là reward), riêng các trạng thái đặc biệt thì thường có reward lớn hơn. Tại mỗi trạng thái, robot phải quyết định thực hiện 1 hành động (action) nào đó trong số các hành động mà nó biết (đi qua trái, đi qua phải, đi thẳng v.v…), sao cho chuỗi các trạng thái này sẽ dẫn nó tới trạng thái có phần thưởng cao nhất (tìm được kho báu). Nói cách khác, bài toán đặt ra là xác định chuỗi hành động để robot tìm được kho báu.

1. Markov Decision Process

Để mô hình hoá bài toán này, người ta dùng 1 framework gọi là Markov Decision Process (MDP), một cách hình thức thì bao gồm các thành phần như sau:

  • States: S = \left\{s_i\right\}_{i=1}^N
  • Actions: A(s), hoặc đơn giản là A
  • Transition model: T\left(s, a, s'\right) \sim Pr\left(s'\vert s, a\right)
  • Reward: R\left(s\right), R\left(s, a\right) hoặc R\left(s, a, s'\right)
  • Policy: \pi\left(s\right) -> a, \pi^*

S là tập các trạng thái mà agent có thể tới tại các thời điểm khác nhau trong cuộc đời nó. Tại mỗi trạng thái s \in S, agent có thể thực hiện một trong các hành động được định nghĩa bởi A\left(s\right) = \left\{a_1, a_2, ..., a_k\right\}.

Tại trạng thái s, nếu agent thực hiện hành động a, thì nó sẽ chuyển sang trạng thái s' với xác suất T\left(s, a, s'\right), được gọi là transition model. Đương nhiên để đúng với định nghĩa xác suất thì \sum_{s'}T\left(s, a, s'\right) = 1.

Tại mỗi trạng thái, agent nhận được phần thưởng là R\left(s\right). Đôi khi người ta cũng kí hiệu R\left(s\right) là R\left(s, a\right) hoặc R\left(s, a, s'\right), nhưng hai kí hiệu sau cùng có thể chuyển về cách viết R\left(s\right) bằng cách thay đổi định nghĩa của các trạng thái, nên viết R\left(s\right) vẫn không mất tính tổng quát.

Lời giải của Markov Decision Process là một chính sách (policy) \pi\left(s\right), thể hiện hành động mà agent nên thực hiện tại mỗi trạng thái s, sao cho nó đạt được tổng reward lớn nhất. Policy như vậy gọi là optimal policy, kí hiệu là \pi^*.

Trong framework này có một số chi tiết được ngầm hiểu:

  • Như các mô hình Markov khác, mặc định ta hiểu rằng thời gian là rời rạc. Tại mỗi thời điểm, agent chỉ có thể có một trạng thái duy nhất. Khi nó thực hiện một hành động thì sẽ chuyển sang một trạng thái khác ở thời điểm tiếp theo (aka. không có lượng tử gì gì)
  • Trạng thái kế tiếp s' mà agent chuyển đến chỉ phụ thuộc vào trạng thái hiện tại s và hành động a của nó, thể hiện bởi T\left(s, a, s'\right). Đây gọi là  Markov condition, có lẽ sẽ quen thuộc với những người đã biết về chuỗi Markov, và thật ra là lí do tại sao framework này gọi là Markov Decision process.
  • Trong suốt vòng đời của agent, thì States, Actions, Transition Model và Reward là không đổi, nghĩa là luật chơi không thay đổi. Đây gọi là tính chất Stationary. Ta sẽ gặp lại Stationary trong một hình dạng khác sau đây.

Tới đây ta có thể thấy rõ ràng sự khác biệt của Reinforcement Learning (RL) so với Supervised hay Unsupervised Learning. Trong RL thì agent không nhận được một label signal rõ ràng như trong Supervised Learning, mà nó chỉ nhận được một tín hiệu “yếu” từ reward của mỗi state, và reward thật sự của mỗi chuỗi các hành động có thể chỉ tới sau khi nó thực hiện liên tiếp vài hành động (gọi là delayed reward). Điều này làm cho RL khác hẳn so với 2 thể loại còn lại.

2. Stationary

Ngoài các giả sử ngầm định đã nói trên, thì MDP còn có một vài giả định khác, như sau:

Thứ nhất, ta giả sử Infinite Horizons. Nghĩa là agent có thể sống mãi mãi, và không có giới hạn về thời gian cho sự sống của agent. Điều này rất quan trọng vì nếu agent không bất tử thì nó phải nghĩ ra một chiến lược khác hẳn, để có thể đến trạng thái kết thúc trước khi thời gian vượt quá mức cho phép. Thực tế vì giả sử thời gian rời rạc ở trên, Infinite Horizons nghĩa là ta không giới hạn số lần chuyển trạng thái của agent.

Giả sử thứ hai rất quan trọng, gọi là Utility of Sequences. Nếu gọi U\left(s_0, s_1, s_2, ...\right)utility (“giá trị”) của chuỗi trạng thái s_0, s_1, s_2, ... thì ta giả sử rằng:

If U\left(s_0, s_1, s_2, ...\right) \textgreater U\left(s_0, s'_1, s'_2, ...\right) then U\left(s_1, s_2, ...\right) \textgreater U\left(s'_1, s'_2, ...\right)

Giả sử này có vẻ trivial, vì ta nghĩ rằng utility của chuỗi trạng thái chỉ là tổng reward của tất cả các trạng thái. Khi đó đương nhiên điều kiện ở trên thoả mãn.

Tuy nhiên điều tricky ở đây là U\left(s_0, s_1, s_2, ...\right) không thể định nghĩa là tổng các reward ở các trạng thái! Đây là điểm rất thú vị của MDP, và ta sẽ trở lại trong bài sau.

Pour Meo.

Advertisements

7 comments

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s