reinforcement learning

[RL2b] Markov Decision Process – Bellman equation

[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

Lại nói tiếp về MDP. Trong bài trước, ta đã thấy utility của một chuỗi trạng thái được định nghĩa là discounted reward \displaystyle U\left(s_0, s_1, ...\right) = \sum_{t=0}^\infty \gamma^t R\left(s_t\right).

Nhắc lại rằng trong ngữ cảnh của MDP, thì ta cần tìm 1 policy \pi sao cho nó tối đa hoá discounted reward của agent. Còn nhớ \pi là một hàm theo trạng thái s, theo đó \pi\left(s\right) trả về một hành động mà agent có thể thực hiện tại trạng thái s. Mặt khác ta biết MDP là một quá trình xác suất, nên với mỗi hành động \pi\left(s\right) mà agent thực hiện, trạng thái kế tiếp của nó được xác định dựa trên xác suất chuyển trạng thái trong transition model.

Nói tóm lại, ngay cả khi cho trước một policy \pi, thì discounted reward của agent tuân theo policy đó, kí hiệu \displaystyle \sum_{t=0}^\infty \gamma^t R\left(s_t\right) \vert \pi, cũng là một biến ngẫu nhiên.

(more…)

Advertisements

[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?

(more…)

[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.

(more…)