multiplicative-weight-update

You are currently browsing articles tagged multiplicative-weight-update.

Trong bài hai bài trước (ở đâyở đây) chúng ta đã tìm hiểu phương pháp multiplicative weight update (MWU) trong trò chơi dự đoán chứng khoán. Trong bài này chúng ta sẽ tìm hiểu ứng dụng của phương pháp này trong bài toán tìm chiến lược trong các zero-sum game với 2 người chơi (2-player zero-sum games), gọi tắt là các zero-sum game.

Zero-sum games

Giả sử có hai người chơi $R$ (Row) và $C$ (Column) chơi một trò chơi. Trong mỗi bước đi $R$ có $n$ lựa chọn và $C$ có $m$ lựa chọn. Sau mỗi nước đi, nếu $R$ "ăn" được $x$ đồng thì $C$ sẽ bị "thua" $x$ đồng và ngược lại. (Do đó, trò chơi có tên là zero-sum game vì tổng ăn/thua của $R$ và $C$ trong mỗi nước đi bằng 0.)

Ta có thể biểu diễn trò chơi giữa $R$ và $C$ bằng một trận $A[1\ldots n,1 \ldots m]$ kích thước $n\times m$, gọi là ma trận ăn/thua (payoff matrix) như sau: nếu trong một bước đi $(i,j)$ $C$ ăn được $x$ đồng thì $A[i,j] = x$ và ngược lại, $A[i,j] = -x$.

Dưới đây minh họa một ma trận ăn/thua $2\times 2$.

$\begin{bmatrix} 5 & -1 \\ -3 & 2 \end{bmatrix} $

Trong trò chơi ví dụ $2\times 2$ ở trên, cho dù $R$ có lựa chọn gì đi nữa thì $C$ cũng có lựa chọn tương ứng sao cho $R$ luôn thua, và ngược lại. Do đó, không có nước đi nào đảm bảo $R$ luôn ăn. Trong trường hợp xấu nhất, $R$ luôn thua ít nhất $2$ đồng nếu $C$ có một lựa chọn hợp lí.

Tuy nhiên, $R$ có thể sử dụng chiến lược ngẫu nhiên để tối thiểu mất mát kì vọng của mình trong mỗi bước. Ví dụ, trong mỗi nước đi, nếu $R$ chọn hàng đầu tiên với xác suất $1/5$ và hàng thứ 2 với xác suất $4/5$ thì cho dù $C$ có lựa chọn gì đi nữa, $R$ chỉ thua $7/5$ (kì vọng), nhỏ hơn $2$. Nếu $R$ chọn một chiến lược ngẫu nhiên khác thì mất mát sau mỗi bước của $R$ có thể nhỏ hơn, thậm chí $R$ còn có thể chiến thằng sau mỗi bước.

John von Neuman chỉ ra rằng, tồn tại một chiến lược ngẫu nhiên mang về cho $R$ payoff theo kì vọng nhiều nhất (trong trường hợp xấu nhất). Bài này, chúng ta sẽ tìm hiểu cách tìm chiến lược (xấp xỉ) như vậy cho $R$.

Giả sử trong mỗi nước đi, $R$ chọn hàng thứ $i$ của $A$ với xác suất $\mathbb{p}[i]$. Nếu $C$ chọn cột thứ $j$ thì payoff kì vọng của $C$ sẽ là:

$E_{i \in \mathbb{p}}[A[i,j]] = \sum_{i=1}^n \mathbb{p}[i]A[i,j] \qquad (1)$

Giả sư $C$ rất thông minh. Mỗi bước $C$ sẽ chọn cột $j$ sao cho đại lượng trong (1) là lớn nhất. Do đó, $R$ nên chọn phân bố $\mathbb{p}$ sao cho payoff kì vọng của $C$ là nhỏ nhất. Khi đó, payoff tối đa của $C$ là:

$ \min_{\mathbb{p}}\max_{j} E_{i \in \mathbb{p}}[A[i,j]] \qquad (2)$

$C$ cũng có thể áp dụng chiến lược tương tự, khi chơi chọn một cột theo phân bố xác suất $\mathbb{q}$. Khi đó, nhiệm vụ của $C$ là tìm phân bố $\mathbb{q}$ sao cho payoff kì vọng của mình lớn nhất:

$ \max_{\mathbb{q}}\min_{i} E_{j \in \mathbb{q}}[A[i,j]] \qquad (3)$

John von Neumann chứng minh rằng nếu $R$ và $C$ chọn cho mình hai phân phối tương ứng $p,q$ mang lại payoff kì vọng tốt nhât thì hai giá trị payoff kì vọng này là bằng nhau.

Theorem 1 (Minimax Theorem): Nếu $A[1\ldots n, 1\ldots m]$ là một ma trận ăn/thua biểu diễn một zero-sum game giữa hai người chơi thì:

$ \min_{\mathbb{p}}\max_{j} E_{i \in \mathbb{p}}[A[i,j]] = \max_{\mathbb{q}}\min_{i} E_{j \in \mathbb{q}}[A[i,j]] \qquad (4)$

 

Khi đó ta nói chiến lược của hai người chơi đã đạt tới một điểm cân bằng.

Áp dụng cho ví dụ ma trận ăn/thua 2x2 ở trên, $R$ nên áp dụng chiến lược $\mathbb{p} = [5/11, 6/11]^T$ còn $C$ nên chọn chiến lược $\mathbb{q} = [3/11, 8/11]^T$. Khi đó, payoff kì vọng (bằng nhau) của hai người chơi là $7/11$. Có nghĩa là trong mỗi nước đi, trung bình $C$ ăn $7/11$ và $R$ thua $7/11$ (nếu giá trị này âm thì mang ý nghĩa ngược lại, $C$ thua còn $R$ ăn). Hướng dẫn chi tiết tính hai phân phối này sẽ có trong bài tập 1.

Tìm chiến lược tối ưu trong zero-sum games

Nếu bạn đọc đã quen thuộc với quy hoạch tuyến tính (linear programming) thì sẽ thấy tìm $\mathbb{p}, \mathbb{q}$ có thể quy về giải bài toán quy hoạch tuyến tính. Ở đây mình trình bày phương pháp tìm một chiến lược (xấp xỉ) sử dụng MWU.

Giả sử $\mathbb{p}^*$ là một chiến lược tối ưu của $R$ và $\lambda$ là giá trị payoff kì vọng tương ứng. Cụ thể,

$ \lambda = \max_{j} E_{i \in \mathbb{p}^*}[A[i,j]] \qquad (5)$

Ta sẽ đi tìm chiến lược $\mathbb{p}'$ sao cho:

$ \max_{j} E_{i \in \mathbb{p}'}[A[i,j]] \leq \lambda + \eta \qquad (6)$

với $\eta$ là một hằng số nhỏ hơn $1$ tùy ý. Ta nói $\mathbb{p}'$ là một chiến lược xấp xỉ của $\mathbb{p}^*$.

Để phân tích trở nên đơn giản, ta sẽ giả sử $A[i,j] \in [0,1]$ bằng cách biển đổi ma trận $A$ như sau: cộng mỗi phần tử của ma trận với một giá trị $M$ đủ lớn để các phần tử của ma trận đều không âm. Sau đó, ta chia mỗi phần tử của ma trận thu được với giá trị lớn nhất trong số các phần tử của ma trận. Việc chứng minh phép biến đổi này không làm thay đổi chiến lược tối ưu của người chơi coi như bài tập cho bạn đọc (bài tập 2).

Để phân tích thời gian của giải thuật sẽ trình bày dưới đây, ta sẽ giả sử tồn tại một hàm, kí hiệu Oracle$(\mathbb{p})$. Hàm này có đầu vào là một chiến lược của $R$ (một phân bố xác suất rời rạc), và đầu ra là một lựa chọn cho $C$ (chỉ số của một cột), sao cho lựa chọn này mang lại cho $C$ nhiều payoff kì vọng nhất. Hàm này có thể thực hiện được trong thời gian $O(nm)$ bằng cách tính payoff kì vọng của mỗi cột trong thời gian $O(n)$ và trả về cột có payoff kì vọng lớn nhất. Ta gọi đầu ra của Oracle$(\mathbb{p})$ là lựa chọn tốt nhất của $C$ ứng với chiến lược $\mathbb{p}$.

Ý tưởng thuật toán: Ta sẽ coi mỗi hàng của ma trận $A$ như một "chuyên gia". Ban đầu, mỗi hàng sẽ được cấp trọng số $1$, tương ứng với một phân phối đều, i.e, $\mathbb{p}_0[i] = 1/n$ với mọi $i$. Khi mỗi "chuyên gia" đưa ra dự đoán ở vòng lặp thứ $t$, ta sử dụng Oracle$(\mathbb{p}_t)$ để tìm ra lựa chọn tốt nhất $j_t$ của $C$. Sau đó, trọng số của các "chuyên gia" sẽ bị giảm/tăng tùy theo payoff của hàng tương ứng tại cột $j_t$ lớn hay nhỏ theo chiến lược MWU. Sau khi giảm trọng số, ta sẽ chuẩn hóa để thu được một phân phối mới $\mathbb{p}_{t+1}$ và tiếp tục một vòng "dự đoán" mới. Ta sẽ chứng minh khi số vòng lặp $T$ đủ lớn, ta sẽ tìm được một phân bố gần với chiến lược tối ưu của $R$.

Theorem 1: Cho trước một số $\eta \leq 1/2$, trong thời gian:

$ \frac{4\log n (T(n,m) + O(n))}{\eta^2}$

ta có thể tìm được một chiến lược $\mathbb{p}'$ cho $R$ với payoff kì vọng $\lambda + \eta$. Ở đây $\lambda$ là payoff kì vọng của chiến lược tối ưu $\mathbb{p}^*$ và $T(n,m)$ là thời gian của hàm Oracle$(\mathbb{p})$.

 

Chứng minh: Ta sẽ chứng minh có thể tìm được $\mathbb{p}'$ từ mô tả ý tưởng thuật toán ở trên. Trước hết, ta có một số nhận xét sau:

  1. Kì vọng payoff của $R$ sau $T$ vòng chơi là $\sum_{t=1}^T \langle \mathbb{p}_t, A[:, j_t] \rangle $, trong đó $A[:, j_t]$ là vector cột $j_t$ của ma trận $A$.
  2. Chi phí của chuyên gia thứ $i$ trong vòng chơi $t$ là $A[i,j_t]$.

Theo Corollary 1 của bài trước, ta có:

$ \frac{\sum_{t=1}^T \langle \mathbb{p}_t, A[:, j_t] \rangle}{T} \leq \frac{\sum_{t=1}^T \langle \mathbb{p}^*, A[:, j_t] \rangle }{T} + \epsilon \frac{\sum_{t=1}^T \langle \mathbb{p}^*, |A[:, j_t|] \rangle}{T} + \frac{\log n}{T\epsilon} \qquad (7)$

Trong (7), $\mathbb{p}^*$ là chiến lược tối ưu của $R$. Ta xét từng đại lượng trong vế phải của $(7)$.

  • Theo (5), $\langle \mathbb{p}^*, A[:, j_t] \rangle \leq \lambda$. Do đó, $\frac{\sum_{t=1}^T \langle \mathbb{p}^*, A[:, j_t] \rangle }{T} \leq \lambda$.
  • Do $A[i,j] \leq 1$ với mọi $i,j$, $\langle \mathbb{p}^*, |A[:, j_t|] \rangle \leq 1$. Do đó, $\frac{\sum_{t=1}^T \langle \mathbb{p}^*, |A[:, j_t|] \rangle}{T}\leq 1$.

Từ (7) ta suy ra:

$ \frac{\sum_{t=1}^T \langle \mathbb{p}_t, A[:, j_t] \rangle}{T} \leq \lambda + \epsilon + \frac{\log n}{T\epsilon} \qquad (8)$

Chọn $\epsilon = \eta/2$ và $T = 4\log n / \eta^2$, từ (8), ta suy ra:

$ \frac{\sum_{t=1}^T \langle \mathbb{p}_t, A[:, j_t] \rangle}{T} \leq \lambda + \eta \qquad (9)$

Gọi $t_0 = \arg\min_{1\leq i \leq t}(\langle \mathbb{p}_t, A[:, j_t] \rangle)$. Từ (9), ta có:

$ \langle \mathbb{p}_{t_0}, A[:, j_{t_0}] \rangle \leq \frac{\sum_{t=1}^T \langle \mathbb{p}_t, A[:, j_t] \rangle}{T} \leq \lambda + \eta \qquad (10)$

Do $j_{t_0}$ là lựa chọn tốt nhất của $C$ đối với chiến lược $\mathbb{p}_{t_0}$ của $R$, ta suy ra:

$ \langle \mathbb{p}_{t_0}, A[:, j] \rangle \leq \langle \mathbb{p}_{t_0}, A[:, j_{t_0}] \rangle \quad \forall 1 \leq j \leq m \qquad (11)$

Như vậy, $\mathbb{p}_{t_0}$ chính là chiến lược xấp xỉ cần tìm.


Remark 1: Theo tính tuyến tính của kì vọng, ta có thể chứng minh được phân bố $ \mathbb{p}' = \frac{\sum_{t=1}^T \mathbb{p}_t}{T}$ cũng thỏa mãn điều kiện của Theorem 1. Chi tiết coi như bài tập cho bạn đọc (bài tập 3).

Remark 2: Để tìm chiến lược xấp xỉ $ \mathbb{q}'$ cho $C$, ta có thể lặp lại phương pháp ta đã sử dụng cho $R$. Tuy nhiên, ta có thể tìm trực tiếp từ kế quả của quá trình tìm chiến lược cho $R$ như sau. Kí hiệu $F[j] = \{t| j_t = j\}$ là tập các vòng chơi mà kết quả của Oracle trả lại là cột $j$. $|F[j]|$ chính là tần số mà cột $j$ được sử dụng trong $T$ lần các "chuyên gia" dự đoán. Gọi $\mathbb{q}'$ là phân phối trong đó:

$ \mathbb{q'[j]} = \frac{|F[j]|}{T} \qquad (12)$

Phân phối $\mathbb{q}'$ như trong (12) chính là môt chiến lược xấp xỉ cho $C$. Chi tiết chứng minh coi như bài tập cho bạn đọc (bài tập 4).

Tham khảo

[1] S. Arora and E. Hazan and S. Kale. The Multiplicative Weights Update Method: a Meta-Algorithm and Applications. Theory of Computing 8.1 (2012): 121-164.
[2] Y. Freund and R. E. Schapire. A Desicion-theoretic Generalization of On-line Learning and an Application to Boosting. European Conference on Computational Learning Theory. Springer, Berlin, Heidelberg, 1995.
[3] A. Gupta. The Multiplicative Weights Algorithm. Lecture Notes, CMU. Accessed 01/05/2018.

Bài tập

Bài tập 1: Gọi $\mathbb{p}^* = [a,b]$ là chiến lược tối ưu cho $R$ trong ví dụ ma trận ăn/thua 2x2 ở trên, trong đó $a + b = 1$. Chứng minh rằng, $(a,b)$ là kết quả của bài toán:

$ \min_{a,b} \max(5a - 3b, -a + 2b) \quad \mbox{subject to } a+b = 1 \qquad (13)$

Chứng minh rằng $a = 5/11, b = 6/11$ là nghiệm của $(13)$. Tương tự, tìm chiến lược cho $C$ trong ví dụ 2x2 ở trên.

Bài tập 2: Chứng minh rằng phép biến đổi ma trận về dạng các phần tử trong đoạn $[0,1]$ trình bài ở trên không làm thay đổi chiến lược tối ưu của $R$ và $C$.

Bài tập 3: Chứng minh rằng phân phối định nghĩa trong Remark 1 cũng thỏa mãn điều kiện của Theorem 1.

Bài tập 4: Chứng minh rằng phân phối định nghĩa trong (12) cũng là một chiến lược xấp xỉ của C. Cụ thể, chứng minh rằng:

$ \min_{i} E_{j \in \mathbb{q}'}[A[i,j]] \geq \lambda - \eta \qquad (14)$

Tags: , , ,

« Older entries