Giải thích phương trình Bellman

Trong bài viết này, chúng ta sẽ tìm hiểu về phương trình Bellman, phương trình được xem là trung tâm trong nhiều thuật toán của học tăng cường (reinforcement learning).

Tác nhân theo hàm giá trị (Value-based Agents)

Hãy nhớ rằng mục tiêu của tác nhân (agent) là tìm ra một chuỗi các hành động sẽ tối đa hóa lợi nhuận (return): tổng phần thưởng (chiết khấu hoặc không chiết khấu - tùy thuộc vào giá trị gamma) trong một tập (episode) hoặc toàn bộ vòng đời của tác nhân, tùy thuộc vào nhiệm vụ.

Trong một nhiệm vụ liên tục, chuỗi các hành động này là vô hạn. Chúng ta có thể giải quyết vấn đề này với sự trợ giúp của hệ số chiết khấu (discounted factor), nằm trong phạm vi [0: 1]. Công thức cho lợi tức chiết khấu $G$ tại thời điểm bước $t$ như sau:

$G_{t} = r_{t+1} + \gamma r_{t+2} + \gamma^{2} r_{t+3} + ... = \sum_{j=0}^{t}\gamma^{j}r_{t+j+1}$

Mặc dù tổng chuỗi hành động vẫn vô hạn nhưng nếu $\gamma < 1$ thì $G_{t}$ sẽ có giá trị hữu hạn. Nếu $\gamma = 0$ , tác nhân chỉ quan tâm đến phần thưởng trước mắt và loại bỏ lợi nhuận dài hạn. Ngược lại, nếu $\gamma = 1$ , tác nhân sẽ coi tất cả phần thưởng trong tương lai bằng phần thưởng trước mắt.

Chúng ta có thể viết lại phương trình của lợi tức $G_{t}$ theo cách hồi quy như sau:

$G_{t} = r_{t+1} + \gamma r_{t+2} + \gamma^{2} r_{t+3} + \gamma^{3} r_{t+4} + ... + \gamma^{T-1} r_{T} = r_{t+1} + \gamma ( r_{t+2} + \gamma r_{t+3} + \gamma^{2} r_{t+4} + ... + \gamma^{T-2} r_{T} ) = r_{t+1} + \gamma( G_{t+1} )$

Nói tóm lại, tác nhân phải có khả năng khai thác thông tin mà chúng ta thể hiện qua lợi tức $G$ này để đưa ra quyết định hành động khi ở một trạng thái nhất định.

Hầu hết tất cả các thuật toán học tăng cường được thực thi bởi tác nhân đều liên quan đến việc ước tính các hàm giá trị (value functions) - hàm của các trạng thái (hoặc của các cặp trạng thái-hành động). Những thuật toán này gọi chung là tác nhân theo hàm giá trị (value-based agents).

Một hàm giá trị ước tính mức độ tốt của tác nhân ở một trạng thái nhất định (hoặc mức độ tốt khi thực hiện một hành động nhất định trong một trạng thái nhất định) dựa trên lợi tức $G$ . Lưu ý rằng lợi tức $G$ mà tác nhân có thể có phụ thuộc vào những hành động tiếp theo mà nó sẽ thực hiện.

Hàm $V$ - giá trị trạng thái

Hàm giá trị đầu tiên chúng ta sẽ giới thiệu là hàm $V$ ( $V$ -function). Nói chung, hàm $V$ giúp trả lời cho câu hỏi cơ bản “Chúng ta mong đợi được lợi tức $G$ bao nhiêu khi ở trạng thái này?”.

Hàm giá trị trạng thái

Chính thức hơn, hàm $V$ , còn được gọi là hàm giá trị trạng thái, hoặc đơn giản hơn là hàm giá trị, hoặc kí hiệu đơn giản là hàm $V$ , đo lường mức độ tốt của mỗi trạng thái. Nói cách khác, nó đo lường mức độ tốt hoặc mức độ xấu ở một trạng thái cụ thể theo lợi tức $G$ khi tuân theo một chính sách $\pi$

Nghĩa là, chúng ta có thể định nghĩa hàm $V$ là tổng phần thưởng dự kiến (chiết khấu hoặc không chiết khấu - tùy thuộc vào giá trị của gamma) có thể nhận được từ trạng thái. Nói một cách chính thống, giá trị của $V_{\pi}(s)$ là:

$V_{\pi} ( s ) = E_{\pi}[ G_{t}| s = s_{t} ] = E_{\pi}[ \sum_{j=0}^{T} \gamma r^{j} _{t+j+1} |s = s_{t}]$

Phương trình này mô tả giá trị kỳ vọng của tổng lợi nhuận $G$ , tại bước thời gian $t$ bắt đầu từ trạng thái $s$ tại thời điểm $t$ và sau đó tuân theo chính sách $\pi$ . Nó được định nghĩa là kỳ vọng $E$ vì hàm chuyển đổi môi trường có thể hoạt động theo cách ngẫu nhiên (the environment transition function might act in a stochastic way).

Để làm rõ khái niệm hơn một chút, hãy xem xét một môi trường rất đơn giản với ba trạng thái:

Trạng thái ban đầu của tác nhân là 0.
Trạng thái 1 là trạng thái mà tác nhân sẽ ở sau khi thực hiện hành động “sang trái” (action 'left') từ trạng thái ban đầu. Phần thưởng nhận được từ việc này là $r = + 1$
Trạng thái 2 là trạng thái mà tác nhân sẽ ở sau khi thực hiện hành động “sang phải” (action 'right'). Phần thưởng nhận được từ việc này là $r = + 2$

Chúng ta có thể biểu hiện quá trình này như hình dưới:

Môi trường trong quá trình này là là tất định (deterministic) - mọi hành động đều thành công và chúng ta luôn bắt đầu từ trạng thái 0. Khi chúng ta đạt đến trạng thái 1 hoặc trạng thái 2, một tập (episode) sẽ kết thúc.

Bây giờ, câu hỏi là, giá trị của trạng thái 0 là gì? Một chi tiết quan trọng là giá trị của một trạng thái luôn được tính toán (phụ thuộc) theo một số chính sách (policy) mà tác nhân của chúng ta tuân theo. Ngay cả trong một môi trường đơn giản như trong ví dụ này, tác nhân của chúng ta có thể có các hành vi khác nhau, mỗi hành vi sẽ có giá trị riêng đối với trạng thái 0. Hãy xem xét một số ví dụ về chính sách (policy):

Tác nhân luôn đi bên trái.
Tác nhân luôn đi bên phải.
Tác nhân đi bên trái với xác suất 0.5 và bên phải với xác suất 0.5.
Tác nhân đi bên trái với xác suất 0.2 và bên phải với xác suất 0.8.

Giá trị của trạng thái 0, $V(0)$ , trong mỗi chính sách trên là:

Giá trị của trạng thái 0 trong trường hợp tác nhân “luôn sang trái” là $V(0)$ = 1.0 (mỗi khi nó đi sang trái, nó sẽ nhận được một phần thưởng là +1 và một tập kết thúc).
Đối với tác nhân “luôn sang phải”, giá trị của trạng thái 0 là $V(0)$ = 2.0 (mỗi khi nó đi sang phải, nó sẽ nhận được phần thưởng +2 và một tập kết thúc).
Đối với tác nhân "0.5 trái + 0.5 phải", giá trị là $V(0)$ = 1.0 * 0.5 + 2.0 * 0.5 = 1.5.
Đối với tác nhân "0.2 trái + 0.8 phải", giá trị là $V(0)$ = 1.0 * 0.2 + 2.0 * 0.8 = 1.8.

Do mục tiêu của tác nhân là nhận được càng nhiều phần thưởng càng tốt, do đó chính sách tối ưu cho tác nhân trong môi trường một-bước-đi đơn giản này là chính sách 2, chính sách "luôn sang phải".

Nhưng ví dụ trước có thể tạo ấn tượng sai lầm rằng chúng ta nên “tham lam” và luôn thực hiện hành động với phần thưởng tức thời cao nhất. Thật không may, câu chuyện lại không đơn giản như vậy. Ví dụ: hãy mở rộng môi trường trước của chúng ta với một trạng thái khác có thể truy cập được từ trạng thái 2. Trạng thái 2 không còn là trạng thái cuối mà chỉ là sự chuyển đổi sang trạng thái 3, với phần thưởng không tốt là –10:

Sự chuyển đổi trạng thái của môi trường mới với phần thưởng có thể được biểu thị như sau:

Với sự bổ sung đó, đối với mỗi chính sách, $V(0)$ sẽ là:

Đối với chính sách "luôn sang trái", $V(0)$ = + 1.0.
Đối với chính sách "luôn sang phải": $V(0)$ = 2.0 + (–10.0) = –8.0
Đối với chính sách "0.5 trái + 0.5 phải": $V(0)$ = 1.0 * 0.5 + (2.0 + (- 10.0)) * 0.5 = -3.5
Đối với chính sách “0.2 trái + 0.8 phải”: $V(0)$ = 1.0 * 0.2 + (2.0 + (- 10.0)) * 0.8 = -6.2

Vì vậy, chính sách tốt nhất cho môi trường mới này hiện nay là chính sách 1: "luôn sang trái". Lưu ý rằng một khi tác nhân đã chọn hành động "luôn sang phải" ở trạng thái 0, phần thưởng xấu là điều khó tránh khỏi, vì từ trạng thái 2 chúng ta chỉ có một lối đi.

Ví dụ dựa trên một môi trường rất đơn giản này giúp bạn đọc nhận độ sự phức tạp của vấn đề tối ưu và chuẩn bị cho các bạn thấy được tầm quan trọng của phương trình Bellman.

Phương trình Bellman

Phương trình Bellman xuất hiện ở khắp mọi nơi trong tài liệu học tăng cường, là một trong những yếu tố trung tâm của nhiều thuật toán học tăng cường.Một cách tóm tắt, chúng ta có thể nói rằng phương trình Bellman phân tách hàm giá trị thành hai phần, phần thưởng trước mắt cộng với phần thưởng chiết khấu trong tương lai.

Phương trình này đơn giản hóa việc tính toán hàm giá trị, sao cho thay vì tính tổng theo nhiều bước thời gian, chúng ta có thể tìm ra lời giải tối ưu của một bài toán phức tạp bằng cách chia nó thành các bài toán con đệ quy, đơn giản hơn và tìm ra lời giải tối ưu của chúng.

Để dễ hiểu về công thức trong các phần sau, sơ đồ tiếp theo hiển thị quy ước tên được đặt cho các biến và mối quan hệ của chúng:

Trong biểu đồ này, $P$ có nghĩa là xác suất của hành động $a$ , được đưa ra ở trạng thái $s$ , kết thúc ở trạng thái $s'$ (với phần thưởng $r$ ).

Phương trình Bellman cho hàm giá trị trạng thái

Chúng ta đã thấy rằng chúng ta có thể xác định lợi tức chiết khấu, $G$ , theo thuật ngữ đệ quy. Bây giờ hãy xem cách thức đệ quy mà chúng ta có thể định nghĩa phương trình Bellman cho hàm giá trị trạng thái:

$V_{\pi}s = \sum_{a} \pi(a|s)\cdot \sum_{s'}P_{ss'}^{a}( r(s,a) + \gamma V_{\pi}( s') )$

Phương trình này cho chúng ta biết cách tìm giá trị của trạng thái $s$ . Chúng ta có thể trực quan thấy rằng nó chia nhỏ một cách đệ quy việc tính toán giá trị thành một phần thưởng dự kiến tức thời lấy từ trạng thái tiếp theo (tổng giá trị trong số các xác suất chính sách) và lợi tức chiết khấu cho tất cả các trạng thái khả dĩ tiếp theo, theo sau trạng thái hiện tại.

Phương trình Bellman rất quan trọng vì nó cho chúng ta khả năng mô tả giá trị của trạng thái $s$ , với giá trị của trạng thái $s'$ và với cách tiếp cận lặp lại mà chúng ta có thể tính giá trị của tất cả những trạng thái. Thật không may, trong hầu hết các tình huống, chúng ta không biết trước xác suất $P$ và phần thưởng $r$ , vì vậy chúng ta không thể giải bài toán tối ưu Markov bằng cách áp dụng trực tiếp phương trình Bellman.

Hàm $Q$ - hàm giá trị hành động

Chúng ta xác định giá trị cho mỗi cặp trạng thái-hành động, được gọi là hàm giá trị-hành động, còn được gọi là hàm $Q$ ( $Q$ -function) hoặc đơn giản là $Q$ . Nó xác định giá trị của việc thực hiện hành động $a$ ở trạng thái $s$ theo chính sách $\pi$ , được ký hiệu là $Q_{\pi}(s, a)$ như là một lợi tức kỳ vọng $G$ bắt đầu từ $s$ , thực hiện hành động $a$ và sau đó tuân theo chính sách $\pi$ :

$Q(s, a) = E_{\pi}[ G_{t} | S_{t} = s, A_{t} = a] = E_{\pi}[ \sum_{j=0}^{t} \gamma^{j} r_{j+t+1} | S_{t} = s, A_{t} = a]$

Tiếp theo, hãy biểu thị bằng $\pi(s|a)$ là xác suất mà một chính sách, $\pi$ , chọn một hành động, $a$ , cho một trạng thái hiện tại, $s$ . Một lần nữa nó được xem như là kỳ vọng $E[.]$ vì hàm chuyển đổi môi trường có thể hoạt động theo cách ngẫu nhiên.

Bây giờ, chúng ta đã xác định $Q_{\pi}(s, a)$ , chúng ta có thể khẳng định rằng hàm giá trị trạng thái tương đương với tổng các hàm giá trị - hành động của tất cả các hành động khả dĩ $a$ (từ trạng thái $s$ ) , nhân với xác suất chính sách của việc chọn mỗi hành động:

$V_{pi}(s) = \sum_{a} \pi(a|s)Q_{\pi}(s, a)$

Lưu ý rằng tổng xác suất của tất cả các hành động đi từ $s$ bằng 1:

$\sum_{a} \pi(a|s) = 1$

Phương trình Bellman cho hàm giá trị hành động

Chúng ta cũng có phương trình Bellman cho hàm giá trị hành động:

$Q_{\pi}(s,a) = \sum_{s'}P_{ss'}^{a}(r(s,a) + \gamma \sum_{a'} \pi(a'|s' )\cdot Q_{\pi}( s',a'))$

và do chúng ta đã chỉ ra rằng hàm giá trị trạng thái $V(s')$ tương đương với tổng các hàm giá trị hành động $Q_{\pi}( s',a')$ của tất cả các hành động đi $a'$ , nhân với xác suất chính sách của việc chọn từng hành động , $pi(a'|s')$ , công thức trước có thể được biểu diễn như sau:

$Q(s,a) = \sum_{s'} P_{ss'}^{a}(r(s,a) + \gamma V(s'))$

Một lần nữa, để dễ hiểu về công thức, chúng ta có thể xây dựng sơ đồ này với mối quan hệ giữa biến cho hàm giá trị hành động:

Phương trình Bellman tối ưu

Phương trình Bellman được sử dụng để tìm giá trị tối ưu của các hàm giá trị trong các thuật toán.

Phương trình tối ưu Bellman cho hàm giá trị trạng thái

Bellman đã chứng minh rằng giá trị tối ưu của một trạng thái thì bằng với việc thực hiện một hành động mà mang lại cho chúng ta phần thưởng tức thì tối đa có thể mong đợi, cộng với phần thưởng dài hạn được chiết khấu cho trạng thái tiếp theo:

$V_{\ast }(s) = \sum_{s'} P_{ss'}^{a}(r(s,a) + \gamma V_{\ast }(s') )$

Chính sách tối ưu

Mục tiêu của tác nhân là tối đa hóa tổng phần thưởng tích lũy trong thời gian dài. Chính sách tối đa hóa tổng phần thưởng tích lũy được gọi là chính sách tối ưu. Lưu ý rằng có thể có các chính sách tối ưu khác nhau, nhưng chúng đều có chung các hàm giá trị, các hàm giá trị “tối ưu”.

Phương trình tối ưu Bellman không chỉ mang lại cho chúng ta phần thưởng tốt nhất mà chúng ta có thể nhận được, mà nó còn cung cấp cho chúng ta chính sách tối ưu để đạt được phần thưởng đó.

Nếu tác nhân của chúng ta biết giá trị của từng trạng thái, thì tác nhân sẽ biết cách thu thập tất cả phần thưởng này và tác nhân chỉ cần chọn trong mỗi bước thời gian (time steps) một hành động mà có thể dẫn tác nhân đến trạng thái có phần thưởng dự kiến tối đa trong mỗi thời điểm.

Phương trình tối ưu Bellman cho hàm giá trị hành động

Chúng ta cũng có thể định nghĩa $V(s)$ thông qua $Q(s,a)$ :

$V_{\ast}(s) = underset{a}{max} Q(s,a)$

Điều này chỉ có nghĩa là giá trị của một trạng thái bằng với giá trị tối đa của một hành động (trong một tập hợp các hành động khả dĩ) mà chúng ta có thể thực hiện từ trạng thái đó.

Bellman cũng chứng minh rằng giá trị tối ưu của trạng thái - hành động có thể được xác định một cách đệ quy là:

$Q_{\ast}left (s,a) = r(s,a) + \gamma underset{a'}{max}Q( s',a')$

Điều đó có nghĩa là để có được chính sách tối ưu, chúng ta có thể lấy giá trị trạng thái tối ưu thông qua giá trị hành động.

Để chỉ ra điều đó, hãy xem một ví dụ đơn giản về cách lấy $V(s$ qua $Q(s,a)$ . Hãy xem xét một môi trường tương tự như môi trường Frozen-Lake, nhưng có cấu trúc đơn giản hơn nhiều. Chúng ta có một trạng thái ban đầu (s0) được bao quanh bởi bốn trạng thái mục tiêu s1, s2, s3 và s4, với phần thưởng tương ứng là + 1, + 2, + 3 và +4.

Mọi hành động đều có tính xác suất giống như trong môi trường frozen lake. Với 33% khả năng hành động của chúng ta sẽ được thực hiện mà không cần điều chỉnh, 33% khả năng chúng ta sẽ bị trượt sang trái so với mục tiêu, và 33% khả năng chúng ta sẽ bị trượt sang phải. Để đơn giản, chúng ta sử dụng hệ số chiết khấu $\gamma = 1$ . Sự chuyển đổi trạng thái của môi trường có thể được biểu diễn như sau.

Các trạng thái cuối 1, 2, 3 và 4 không có kết nối ra ngoài, vì vậy giá trị $Q$ cho các trạng thái đó bằng 0. Do đó, giá trị của các trạng thái cuối bằng với phần thưởng tức thì của chúng theo công thức trước đó. Khi đó, $V(1)$ = 1, $V(2)$ = 2, $V left(3)$ = 3 và $V(4)$ = 4.

Bây giờ là lúc để tính giá trị của trạng thái 0. Theo công thức:

$Q(0, 0) = 0.33 * V1 + 0.33* V2 + 0.33 * V3$
$Q(0, 1) = 0.33 * V2 + 0.33* V3 + 0.33 * V4$
$Q(0, 2) = 0.33 * V1 + 0.33* V3 + 0.33 * V4$
$Q(0, 3) = 0.33 * V1 + 0.33* V2 + 0.33 * V4$

thay giá trị vào công thức ta có:

$Q(0, 0) = 0.33 * 1 + 0.33* 2 + 0.33 * 3 = 1.98$
$Q(0, 1) = 0.33 * 1 + 0.33* 3 + 0.33 * 4 = 2.64$
$Q(0, 2) = 0.33 * 1 + 0.33* 3 + 0.33 * 4 = 2.64$
$Q(0, 3) = 0.33 * 1 + 0.33 * 2 + 0.33 * 4 = 2.31$

Giá trị cho trạng thái 0, là giá trị lớn nhất của tất cả các giá trị $Q$ , sẽ là $V_{\ast}(0)$ = 2.64.

Phương pháp Q-learning

Trong thực tế, giá trị $Q$ thuận tiện hơn nhiều, vì đối với tác nhân, việc đưa ra quyết định về các hành động dựa trên giá trị $Q$ đơn giản hơn nhiều so với giá trị $V$ . Trong trường hợp giá trị $Q$ , để chọn hành động dựa trên trạng thái, tác nhân chỉ cần tính giá trị $Q$ cho tất cả các hành động có sẵn bằng cách sử dụng trạng thái hiện tại và sau đó chọn hành động có giá trị $Q$ lớn nhất.

Để làm điều tương tự bằng cách sử dụng các giá trị của các trạng thái, nhân cần biết không chỉ các giá trị mà còn cả xác suất cho các chuyển đổi. Trong thực tế, chúng ta hiếm khi biết trước về chúng, vì vậy tác nhân cần ước tính xác suất chuyển đổi cho mọi cặp hành động và trạng thái.

Cách tiếp cận này đã đặt tên cho toàn bộ họ phương pháp gọi là $Q$ -learning này mà chúng tôi có thể thảo luận trong các bài khác.

Các bạn có thể đọc bài viết gốc tại đây.

Chia sẻ bài viết

Giải thích phương trình Bellman