Nhập môn Reinforcement Learning: Các kỹ thuật Bandit nâng cao & Giới thiệu MDP

Chào mọi người, tiếp nối series bài viết về RL, ở phần trước chúng ta đã dừng lại ở các phương pháp cơ bản của bài toán k-armed bandit và cách tracking trong môi trường nonstationary. Trong phần này, chúng ta sẽ đi nốt một vài kỹ thuật nâng cao hơn để tối ưu việc lựa chọn hành động, trước khi chính thức bước vào khái niệm cốt lõi nhất của Reinforcement Learning: Finite Markov Decision Processes (MDP).

Optimistic Initial values.

Tất cả các phương pháp mà chúng ta thảo luận ở phần trước đến thời điểm hiện tại đều phụ thuộc vào việc lựa chọn giá trị khởi tạo trong việc dự đoán action-value, $Q_1(a)$. Trong lý thuyết của xác suất thống kê, những phương pháp này thường bị biased bởi chính những giá trị khởi tạo đó.

Lấy ví dụ trong sample-average methods, sự thiên vị (bias) này chỉ mất đi khi mà tất cả các actions được lựa chọn ít nhất 1 lần. Nhưng với hằng số step-size $\alpha$, sự thiên vị này là vĩnh cửu và chỉ giảm dần theo thời gian. Trong thực chiến, sự thiên vị này thường không hẳn là một vấn đề, mà đôi khi nó còn đem lại một vài lợi ích nhất định. Ngược lại, giá trị dự đoán khởi tạo phải chịu sự chi phối của user nếu ta chỉ đặt tất cả chúng về 0. Điều tốt là nó có thể cung cấp một vài kiến thức có sẵn nhằm hỗ trợ đạt một mức độ rewards nào đó từ sớm.

Tự khởi tạo action values có thể sử dụng như một cách đơn giản để ủng hộ exploration. Giả sử thay vì set các giá trị khởi tạo cho action values là 0 giống như trong 10-armed testbed, thì chúng ta đặt tất cả là $+5$. Trả về là $q_*(a)$ trong bài toán trên được lựa chọn với normal distribution có mean 0 và variance 1. Với giá trị khởi tạo là $+5$ đã đưa về một trạng thái khá lạc quan (optimistic).

Đây là một trick tối ưu việc ủng hộ cho action-value methods explore. Điều này dẫn tới việc reward trong giai đoạn đầu nhận được sẽ thấp hơn kỳ vọng (thấp hơn 5). Kết quả là hệ thống sẽ tự động thử các actions khác (exploration) kể cả khi hành động greedy đang được lựa chọn. Tóm lại, tất cả các actions đều sẽ được thử một vài lần trước khi mà reward thực sự hội tụ.

Upper-Confidence-Bound (UCB) Action Selection.

Exploration là cần thiết bởi vì sẽ luôn có một sự không chắc chắn về accuracy của việc dự đoán action-value. Phương pháp greedy luôn tìm kết quả tốt nhất tới thời điểm hiện tại, nhưng một vài actions khác có thể đem lại hiệu quả tốt hơn.

$\epsilon$-greedy lựa chọn các hành động để ép buộc các non-greedy actions được trải nghiệm, nhưng nó lại lựa chọn một cách bừa bãi. Với các hành động mà xấp xỉ giá trị greedy sẽ không được lựa chọn một cách thường xuyên. Sẽ tốt hơn nếu các non-greedy actions được lựa chọn dựa vào tiềm năng mà chúng có thể trở thành tối ưu, lấy độ bất định làm cơ sở. Một trong những cách hiệu quả để làm điều này là sử dụng UCB:

$$A_t = \arg\max_a \left[ Q_t(a) + c \sqrt{\frac{\ln t}{N_t(a)}} \right]$$

Ở đây $\ln t$ là natural logarithm của $t$, $N_t(a)$ là số lần mà action $a$ được lựa chọn cho tới thời điểm $t$, và $c > 0$ xác định góc của exploration (mức độ tự tin). Nếu $N_t(a) = 0$, thì $a$ sẽ được ưu tiên lựa chọn luôn.

Ý tưởng của UCB action selection là sử dụng trạng thái căn bậc hai để đo lường sự không chắc chắn (uncertainty) của variance trong việc dự đoán a value. Mỗi lần $a$ được lựa chọn, $N_t(a)$ ở mẫu số tăng lên, sự không chắc chắn sẽ giảm xuống. Ngược lại, với mỗi lần một action khác $a$ được lựa chọn, $t$ ở tử số tăng lên nhưng $N_t(a)$ thì không, dẫn đến sự không chắc chắn của action $a$ sẽ được tăng lên. Việc sử dụng natural logarithm mang ý nghĩa rằng giá trị này sẽ tăng dần theo thời gian, nhưng biên độ sẽ hẹp dần. Mọi hành động đều sẽ được lựa chọn nhưng các hành động có giá trị dự đoán thấp sẽ ít được gọi hơn theo thời gian. Note: Các setting nâng cao của UCB action selection thường khá khó khả thi trong các bài toán thực chiến lớn.

Gradient Bandit Algorithms.

Đến thời điểm hiện tại, chúng ta đã đề cập tới các phương pháp dự đoán action values và sử dụng nó cho việc chọn hành động. Đây thường là một cách tiếp cận tốt nhưng không phải duy nhất.

Ở phần này, chúng ta sẽ cân nhắc đến sự ưa thích số học (preference) cho từng action $a$, được xác định là $H_t(a) \in \mathbb{R}$. Sự ưa thích càng lớn thì sự thường xuyên trong việc lựa chọn action đó càng nhiều, nhưng ta cũng cần hiểu rằng sự ưa thích không đánh đồng với reward. Nếu ta cộng thêm 1000 cho tất cả sự ưa thích, nó hoàn toàn không gây ảnh hưởng tới phân phối xác suất của action, điều này được xác định dựa vào softmax distribution:

$$Pr\{A_t = a\} = \frac{e^{H_t(a)}}{\sum_{b=1}^k e^{H_t(b)}} = \pi_t(a)$$

Ở đây $\pi_t(a)$ là xác suất để thực hiện hành động $a$ tại thời điểm $t$. Khởi tạo ban đầu tất cả sự ưa thích là như nhau (vd $H_1(a) = 0 \quad \forall a$), điều này dẫn tới các hành động đều có xác suất được chọn ngang nhau.

Có một phương pháp natural learning algorithm dành cho softmax action preferences dựa trên ý tưởng của stochastic gradient ascent. Ở mỗi step, sau khi thực hiện action $A_t$ và nhận được $R_t$, giá trị action preferences được cập nhật bởi:

$$H_{t+1}(A_t) = H_t(A_t) + \alpha (R_t - \bar{R}_t)(1 - \pi_t(A_t)) \quad \text{và}$$

$$H_{t+1}(a) = H_t(a) - \alpha (R_t - \bar{R}_t)\pi_t(a) \quad \text{với mọi } a \neq A_t$$

Ở đây $\alpha > 0$ là tham số step-size, và $\bar{R}_t$ là trung bình của rewards tới thời điểm trước $t$ (có thể dễ dàng tính bằng công thức incremental).

$\bar{R}_t$ được định ra làm một baseline để các reward so sánh với. Nếu reward nhận được cao hơn baseline, xác suất lấy $A_t$ trong tương lai được gia tăng; nếu reward ở dưới baseline thì xác suất sẽ giảm. Các hành động không được lựa chọn sẽ di chuyển theo hướng ngược lại. (Nếu bỏ baseline $\bar{R}_t$ đi, performance của thuật toán sẽ bị giảm một cách đáng kể do không thích ứng kịp với reward level mới).

Chứng minh Gradient Bandit Algorithm là Stochastic Gradient Ascent

Để hiểu sâu hơn, ta có thể nhìn gradient bandit algorithm như một stochastic approximation của gradient ascent. Trong gradient ascent chuẩn, mỗi action preference $H_t(a)$ sẽ được tăng cường bằng partial derivative của expected reward:

$$H_{t+1}(a) = H_t(a) + \alpha \frac{\partial \mathbb{E}[R_t]}{\partial H_t(a)}$$

Khi mà ta tính toán performance là expected reward: $\mathbb{E}[R_t] = \sum_x \pi_t(x) q_*(x)$. Tất nhiên, điều này là bất khả thi trong thực tế do ta không hề biết giá trị $q_*(x)$. Tuy nhiên thuật toán cập nhật gradient bandit lại tương đương với công thức trên trong expected value. Cách chứng minh chỉ cần một chút kiến thức tích phân:

Đầu tiên nhìn vào phần exact performance gradient:

$$\frac{\partial \mathbb{E}[R_t]}{\partial H_t(a)} = \frac{\partial}{\partial H_t(a)} \left[ \sum_x \pi_t(x) q_*(x) \right] = \sum_x q_*(x) \frac{\partial \pi_t(x)}{\partial H_t(a)} = \sum_x (q_*(x) - B_t) \frac{\partial \pi_t(x)}{\partial H_t(a)}$$

Ở đây $B_t$ là baseline (bất kỳ scalar nào không phụ thuộc vào $x$). Chúng ta có thể thêm baseline vào mà không làm thay đổi phương trình bởi vì tổng gradient của tất cả các action luôn bằng 0: $\sum_x \frac{\partial \pi_t(x)}{\partial H_t(a)} = 0$ (do tổng xác suất luôn bằng 1).

Tiếp đến, nhân với $\frac{\pi_t(x)}{\pi_t(x)}$:

$$= \sum_x \pi_t(x) (q_*(x) - B_t) \frac{\partial \pi_t(x)}{\partial H_t(a)} / \pi_t(x)$$

Lúc này, equation trên đã chuyển về trạng thái expected value của biến ngẫu nhiên $A_t$:

$$= \mathbb{E} \left[ (q_*(A_t) - B_t) \frac{\partial \pi_t(A_t)}{\partial H_t(a)} / \pi_t(A_t) \right]$$

Lựa chọn baseline $B_t = \bar{R}_t$ và thay thế $R_t$ cho $q_*(A_t)$ (được phép do $\mathbb{E}[R_t | A_t] = q_*(A_t)$). Theo quy tắc đạo hàm của hàm softmax, ta có $\frac{\partial \pi_t(x)}{\partial H_t(a)} = \pi_t(x)(\mathbb{1}_{a=x} - \pi_t(a))$. Thay vào ta được:

$$= \mathbb{E} \left[ (R_t - \bar{R}_t) \pi_t(A_t) (\mathbb{1}_{a=A_t} - \pi_t(a)) / \pi_t(A_t) \right]$$

$$= \mathbb{E} \left[ (R_t - \bar{R}_t) (\mathbb{1}_{a=A_t} - \pi_t(a)) \right]$$

Chúng ta vừa chứng minh được giá trị cập nhật mong đợi của gradient bandit tương đương với đạo hàm của reward mong đợi. Nó cho thấy thuật toán này là một phần của stochastic gradient ascent và có tính hội tụ mạnh.

Associative Search (Contextual Bandits)

Như ta đã đi qua, các task nãy giờ đều không có tính liên kết, nghĩa là ta không cần map các actions khác nhau với các tình huống khác nhau. Agent chỉ tìm một hành động tốt nhất khi task là cố định hoặc biến đổi theo thời gian. Mặc dù vậy, trong các bài toán phổ thông của RL, mục tiêu sẽ là học được một policy, mapping các trạng thái (states) khác nhau với các hành động cụ thể sao cho tốt nhất.

Giả sử ta có một máy gacha thay đổi màu sắc ở mỗi step, và phần thưởng của từng action phụ thuộc vào màu sắc đó. Lúc này, chúng ta sẽ phải học từng policy liên kết với từng task (ở đây là màu sắc), và lựa chọn hành động tốt nhất cho context hiện tại.

Đây là ví dụ của Associative Search task (hay Contextual Bandits). Nó là bước đệm trung gian giữa k-armed bandit và full RL problem. Nếu action không chỉ ảnh hưởng tới reward tức thời mà còn ảnh hưởng tới cả tình huống tiếp theo (next situation), thì ta chính thức có một bài toán RL đầy đủ.

Finite Markov Decision Processes (MDP có giới hạn)

Sau khi dạo đầu chán chê với bandit, giờ chúng ta sẽ gác lại nó và đi vào vấn đề cốt lõi của RL. Để hiểu được format chuẩn của RL, chúng ta phải tìm hiểu về MDPs (Finite Markov Decision Processes).

Agent-Environment Interface.

MDPs mang hàm nghĩa của một frame các vấn đề học tập từ interaction với mục tiêu là đạt được kết quả. Learner (hay đối tượng ra quyết định) gọi là Agent. Thứ mà agent giao tiếp với, bao gồm mọi thành phần ngoại trừ bản thân nó, gọi là Environment. Sự tương tác này là liên tục: agent lựa chọn hành động, environment trả về một trạng thái mới và một reward.

Nói chính xác hơn, agent và environment giao tiếp với nhau qua các discrete time steps: $t = 0, 1, 2, 3, \dots$ Tại mỗi thời điểm $t$, agent nhận một representation của state $S_t \in \mathcal{S}$, dựa trên đó đưa ra action $A_t \in \mathcal{A}(s)$. Sang time step tiếp theo, như một hệ quả của action đó, agent nhận được reward $R_{t+1} \in \mathcal{R} \subset \mathbb{R}$ và một state mới $S_{t+1}$. Quá trình này tạo thành một chuỗi (trajectory):

$$S_0, A_0, R_1, S_1, A_1, R_2, S_2, A_2, R_3, \dots$$

Trong finite MDP, tập $\mathcal{S}, \mathcal{A}, \mathcal{R}$ luôn có số lượng phần tử hữu hạn. Biến ngẫu nhiên $R_t$ và $S_t$ phụ thuộc hoàn toàn vào preceding state và action, chúng ta định nghĩa xác suất chuyển đổi bằng hàm $p$:

$$p(s', r | s, a) \doteq \Pr\{S_t = s', R_t = r \mid S_{t-1} = s, A_{t-1} = a\}$$

Hàm $p$ định nghĩa hoàn toàn sự biến động (dynamics) của môi trường MDP. Việc state hiện tại mang đầy đủ thông tin của quá khứ để đưa ra dự đoán trong tương lai mà không cần nhìn lại lịch sử được gọi là Markov property.

Goals and Rewards.

Trong RL, mục tiêu của agent được formalized dựa trên signal từ environment gọi là reward. Ở mỗi time step, reward là một scalar $R_t$. Mục tiêu của agent không phải là tối ưu những reward nhất thời mà là cumulative reward.

Điều này được gọi là reward hypothesis. Ví dụ: để robot học cách đi bộ, ta cấp reward khi robot tiến về phía trước. Trong giải mê cung, ta cho reward $-1$ ở mỗi step để thúc đẩy việc thoát mê cung nhanh nhất có thể. Nhìn chung, ta muốn agent làm gì thì ta phải thiết kế reward function phản ánh đúng mục tiêu đó.

Returns and Episodes.

Vậy chính xác thì "tối đa hóa cumulative reward" nghĩa là tối ưu cái gì? Chúng ta muốn tối ưu hóa expected return, ký hiệu là $G_t$. Đơn giản nhất:

$$G_t \doteq R_{t+1} + R_{t+2} + R_{t+3} + \dots + R_T$$

Với $T$ là bước cuối cùng (terminal state). Khi agent-environment interaction có thể chia nhỏ thành các chuỗi con độc lập (giống như các ván game), ta gọi chúng là episodes. Task trong các episodes này gọi là episodic tasks. Mỗi episode kết thúc độc lập với nhau.

Tuy nhiên, có nhiều task không thể break thành các episodes mà kéo dài vô hạn (vd: các hệ thống điều khiển tự động, robot hoạt động lâu dài). Đây gọi là continuing tasks. Nếu $T = \infty$, giá trị $G_t$ có thể tiến tới vô cực. Cách đơn giản nhất để giải quyết là dùng discounting.

Agent sẽ cố lựa chọn hành động sao cho tổng các discounted rewards trong tương lai là tối ưu:

$$G_t \doteq R_{t+1} + \gamma R_{t+2} + \gamma^2 R_{t+3} + \dots = \sum_{k=0}^{\infty} \gamma^k R_{t+k+1}$$

Ở đây $\gamma \in [0, 1]$ là discount rate. Discount rate thể hiện value của các rewards trong tương lai: một reward nhận được ở $k$ time steps trong tương lai chỉ có trọng số $\gamma^{k-1}$.

• Nếu $\gamma = 0$, agent sẽ bị "myopic" (cận thị), chỉ lo tối ưu hóa reward tức thời $R_{t+1}$.
• Nếu $\gamma$ tiến gần 1, agent sẽ có tầm nhìn xa hơn và coi trọng cả những rewards trong tương lai dài hạn.

Vì $\gamma < 1$, chuỗi vô hạn bên trên sẽ hội tụ về một giá trị hữu hạn, giúp bài toán tính toán được.

Tập 3 tạm dừng tại đây. Bài toán MDP là nền tảng cực kỳ quan trọng, nắm chắc nó thì các bạn đọc tiếp về Value Function và Bellman Equation ở bài sau sẽ cực kỳ dễ thở. Cảm ơn các bạn đã theo dõi!