[RL2a] Markov Decision Process – Discounted Reward

[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

Trong bài trước, ta đang dừng ở hàm Utility của một chuỗi trạng thái, và ta nói rằng U\left(s_0, s_1, s_2, ...\right) không thể là tổng reward của tất cả trạng thái. Nói cách khác:

U\left(s_0, s_1, s_2,...\right) \neq \sum_{t=0}^\infty R\left(s_t\right)

Vì sao như vậy?

Tất cả là vì giả sử Infinite Horizons. Vì chuỗi trạng thái có thể kéo dài vô tận nên tổng của các reward rất có khả năng diverge, và trở thành infinity. Khi đó ta không thể so sánh chuỗi trạng thái này có tốt hơn chuỗi khác hay không (không thoả điều kiện Utility of Sequence), vì cả hai đều là infinity.

Nói cách khác, nếu bạn bất tử thì việc mỗi ngày bạn làm ra bao nhiêu tiền cũng không còn quan trọng gì nữa.

Ta sẽ xem ví dụ sau:

Giả sử bạn là Cuội, và bất tử. Hằng Nga một ngày nọ buồn tình Trư Bát Giới, cho Cuội 2 lựa chọn:

  1. Ngày nào Hằng Nga cũng cấp cho Cuội 1$ tiền Mặt trăng, không bao giờ dừng lại (vì Cuội bất tử)
  2. Ngày nào cũng cấp cho 2$ tiền Mặt trăng

Nếu là Cuội thì bạn chọn option nào?

Thật ra cả 2 đều như nhau, vì 1 + 1 + 1 + … và 2 + 2 + 2 + … đều là infinity (trừ khi chọn Hằng Nga).

Đương nhiên nếu Cuội không bất tử, thì lựa chọn 2 chắc chắn tốt hơn, nhưng trong ngữ cảnh infinite series thì intuition về các phép toán mà ta đã quen trong ngữ cảnh finite thường không còn đúng nữa, dẫn đến rất nhiều kết quả bất ngờ kiểu như thế này.

Vậy giờ tổng của chuỗi vô hạn thì sẽ có khả năng diverge, thanh niên ham học phải làm sao?

Té ra không phải lúc nào nó cũng diverge. Chẳng hạn ta biết chuỗi hình học không diverge, và thực tế là ta có thể sửa lại định nghĩa của hàm Utility để cho nó không diverge, như sau:

\displaystyle U\left(s_0, s_1, s_2,...\right) = \sum_{t=0}^\infty \gamma^t R\left(s_t\right)\; \text{where} \; 0 \leq \gamma \textless 1

và đây gọi là discounted rewards, còn \gamma gọi là discount factor.

Chuỗi này không diverge vì ta có:

\begin{array}{rl} \displaystyle S = \sum_{t=0}^\infty \gamma^t & = \gamma^0 + \gamma^1 + \gamma^2 + \gamma^3 + \gamma^4 + ... \\ & = 1 + \gamma\left(\gamma^0 + \gamma^1 + \gamma^2 + \gamma^3 + ...\right) \\ & = 1 + \gamma S\\ \Rightarrow S & \displaystyle = \frac{1}{1-\gamma} \end{array}

Như vậy:

\begin{array}{rl} \displaystyle U\left(s_0, s_1, s_2,...\right) = \sum_{t=0}^\infty \gamma^t R\left(s_t\right) & \displaystyle \leq \left(\sum_{t=0}^\infty \gamma^t\right)R_{max} \\ \displaystyle \Rightarrow U\left(s_0, s_1, s_2,...\right) & \displaystyle \leq \frac{1}{1-\gamma}R_{max} \end{array}

với R_{max} = \max_t R\left(s_t\right). Do U\left(s_0, s_1, s_2,...\right) bị chặn trên bởi một số thực nên nó chắc chắn không diverge.

Như vậy ta đã biết làm thế nào để định nghĩa hàm utility cho 1 chuỗi trạng thái vô hạn. Trong bài tới ta sẽ xem thêm 1 ít toán để làm sao nghĩ ra thuật toán cho agent maximize reward của nó.

Advertisements

6 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