Đề bài
Một multi-armed bandit là một dãy máy đánh bạc (các tay) với mức trả thưởng chưa biết. Epsilon-greedy cân bằng giữa khám phá và khai thác: với xác suất epsilon nó kéo một tay ngẫu nhiên, ngược lại nó kéo tay có giá trị ước lượng cao nhất.
Để có thể kiểm thử, các số ngẫu nhiên được cho sẵn. Bắt đầu với ước lượng Q = 0 và số lần N = 0 cho mọi tay. Ở mỗi bước t:
- Nếu
random_values[t]< epsilon, khám phá: arm =random_arms[t]. Ngược lại khai thác: arm = tay có Q cao nhất (chỉ số nhỏ nhất nếu nhiều tay bằng nhau). - Nhận reward =
rewards[t][arm]. - N[arm] ← N[arm] + 1 và Q[arm] ← Q[arm] + (reward - Q[arm]) / N[arm], tức trung bình cộng dồn.
Hãy viết epsilon_greedy(rewards, epsilon, random_values, random_arms).
Đầu vào
rewards: Mỗi bước một hàng, chứa phần thưởng mà từng tay sẽ trả ở bước đó.
epsilon: Xác suất khám phá.
random_values: Mỗi bước một số ngẫu nhiên trong [0, 1).
random_arms: Tay sẽ kéo ở mỗi bước nếu khám phá.
Đầu ra
Trả về các ước lượng Q cuối cùng, mỗi tay một giá trị.
Ràng buộc
1 ≤ số bước ≤ 10.000, 1 ≤ số tay ≤ 100
0 ≤ epsilon ≤ 1, -100 ≤ mỗi phần thưởng ≤ 100
Ví dụ
Đầu vào:
epsilon = 0.1
rewards = [
[1.0, 3.0],
[1.0, 3.0],
[1.0, 3.0],
[1.0, 3.0]
]
random_arms = [0, 1, 0, 0]
random_values = [0.5, 0.05, 0.7, 0.9]
Kết quả mong đợi:
expected = [1.0, 3.0]Đầu vào:
double epsilon = 0.1;
std::vector<std::vector<double>> rewards = {
{1.0, 3.0},
{1.0, 3.0},
{1.0, 3.0},
{1.0, 3.0}
};
std::vector<long long> random_arms = {0, 1, 0, 0};
std::vector<double> random_values = {0.5, 0.05, 0.7, 0.9};
Kết quả mong đợi:
std::vector<double> expected = {1.0, 3.0};Đầu vào:
double epsilon = 0.1;
double[][] rewards = new double[][] {
new double[] {1.0, 3.0},
new double[] {1.0, 3.0},
new double[] {1.0, 3.0},
new double[] {1.0, 3.0}
};
long[] random_arms = new long[] {0, 1, 0, 0};
double[] random_values = new double[] {0.5, 0.05, 0.7, 0.9};
Kết quả mong đợi:
double[] expected = new double[] {1.0, 3.0};Giải thích
Bước 0 khai thác; cả hai Q đều bằng 0, nên kéo tay 0 và Q = [1, 0]. Bước 1 khám phá (0.05 < 0.1) và thử tay 1: Q = [1, 3]. Bước 2 và 3 khai thác tay tốt hơn là tay 1. Kết quả: [1, 3].
Đầu vào:
epsilon = 0.0
rewards = [
[2.0, 5.0],
[4.0, 5.0],
[0.0, 5.0]
]
random_arms = [1, 1, 1]
random_values = [0.5, 0.5, 0.5]
Kết quả mong đợi:
expected = [2.0, 0.0]Đầu vào:
double epsilon = 0.0;
std::vector<std::vector<double>> rewards = {
{2.0, 5.0},
{4.0, 5.0},
{0.0, 5.0}
};
std::vector<long long> random_arms = {1, 1, 1};
std::vector<double> random_values = {0.5, 0.5, 0.5};
Kết quả mong đợi:
std::vector<double> expected = {2.0, 0.0};Đầu vào:
double epsilon = 0.0;
double[][] rewards = new double[][] {
new double[] {2.0, 5.0},
new double[] {4.0, 5.0},
new double[] {0.0, 5.0}
};
long[] random_arms = new long[] {1, 1, 1};
double[] random_values = new double[] {0.5, 0.5, 0.5};
Kết quả mong đợi:
double[] expected = new double[] {2.0, 0.0};Giải thích
Với epsilon = 0 tác tử không bao giờ khám phá. Nó cứ kéo tay 0, trung bình đi từ 2 → 3 → 2, và không bao giờ biết tay 1 trả 5. Kết quả: [2, 0].
Hướng tiếp cận
Hãy tự thử trước, sau đó mở từng gợi ý một.
Gợi ý 1
Ở mỗi bước, chọn hoặc arm ngẫu nhiên bắt buộc, hoặc arm có ước lượng tốt nhất hiện tại.
Gợi ý 2
Cập nhật giá trị của mỗi arm bằng trung bình chạy để phần thưởng cũ giảm ảnh hưởng khi số lần kéo tăng lên.
Gợi ý 3
Phá hòa bằng cách chọn arm có chỉ số nhỏ nhất, và nhớ rằng mỗi bước chỉ arm được chọn mới thay đổi.
Độ phức tạp mong đợi
thời gian O(steps * arms), bộ nhớ phụ O(arms)
Tham khảo
Thử thách này đã được điều chỉnh cho CodeUtility. Hãy làm theo đề bài và các ràng buộc ở trên.