Tất cả thử thách
Dễ 0 đã giải Tỷ lệ chấp nhận 0%

Epsilon-Greedy Multi-Armed Bandit

Balance exploration and exploitation on a multi-armed bandit with epsilon-greedy action selection.

Bạn sẽ học được gì

  • Balance exploring and exploiting
  • Update running averages incrementally
  • See why pure greedy agents get stuck

Đề bài

Xem bản dịch

A multi-armed bandit is a row of slot machines (arms) with unknown payouts. Epsilon-greedy balances exploring and exploiting: with probability epsilon it pulls a random arm, otherwise it pulls the arm with the highest estimated value.

To make the run testable, the random numbers are given. Start with an estimate Q = 0 and a count N = 0 for every arm. At each step t:

  1. If random_values[t] < epsilon, explore: arm = random_arms[t]. Otherwise exploit: arm = the arm with the highest Q (the lowest index if several tie).
  2. Receive reward = rewards[t][arm].
  3. N[arm] ← N[arm] + 1 and Q[arm] ← Q[arm] + (reward - Q[arm]) / N[arm], the running average.

Implement epsilon_greedy(rewards, epsilon, random_values, random_arms).

Input

rewards: One row per step with the reward each arm would pay at that step.

epsilon: The exploration probability.

random_values: One random number in [0, 1) per step.

random_arms: The arm to pull at each step if exploring.

Output

Return the final Q estimates, one per arm.

Ràng buộc

1 ≤ steps ≤ 10,000, 1 ≤ arms ≤ 100

0 ≤ epsilon ≤ 1, -100 ≤ each reward ≤ 100

Ví dụ

Ví dụ 1
Đầu vào:
rewards = [
    [1.0, 3.0],
    [1.0, 3.0],
    [1.0, 3.0],
    [1.0, 3.0]
]
epsilon = 0.1
random_values = [0.5, 0.05, 0.7, 0.9]
random_arms = [0, 1, 0, 0]

Kết quả mong đợi:
expected = [1.0, 3.0]
Đầu vào:
std::vector<std::vector<double>> rewards = {
    {1.0, 3.0},
    {1.0, 3.0},
    {1.0, 3.0},
    {1.0, 3.0}
};
double epsilon = 0.1;
std::vector<double> random_values = {0.5, 0.05, 0.7, 0.9};
std::vector<long long> random_arms = {0, 1, 0, 0};

Kết quả mong đợi:
std::vector<double> expected = {1.0, 3.0};
Đầu vào:
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}
};
double epsilon = 0.1;
double[] random_values = new double[] {0.5, 0.05, 0.7, 0.9};
long[] random_arms = new long[] {0, 1, 0, 0};

Kết quả mong đợi:
double[] expected = new double[] {1.0, 3.0};

Giải thích

Step 0 exploits; both Q are 0, so arm 0 is pulled and Q = [1, 0]. Step 1 explores (0.05 < 0.1) and tries arm 1: Q = [1, 3]. Steps 2 and 3 exploit the better arm 1. Result: [1, 3].

Ví dụ 2
Đầu vào:
rewards = [
    [2.0, 5.0],
    [4.0, 5.0],
    [0.0, 5.0]
]
epsilon = 0.0
random_values = [0.5, 0.5, 0.5]
random_arms = [1, 1, 1]

Kết quả mong đợi:
expected = [2.0, 0.0]
Đầu vào:
std::vector<std::vector<double>> rewards = {
    {2.0, 5.0},
    {4.0, 5.0},
    {0.0, 5.0}
};
double epsilon = 0.0;
std::vector<double> random_values = {0.5, 0.5, 0.5};
std::vector<long long> random_arms = {1, 1, 1};

Kết quả mong đợi:
std::vector<double> expected = {2.0, 0.0};
Đầu vào:
double[][] rewards = new double[][] {
    new double[] {2.0, 5.0},
    new double[] {4.0, 5.0},
    new double[] {0.0, 5.0}
};
double epsilon = 0.0;
double[] random_values = new double[] {0.5, 0.5, 0.5};
long[] random_arms = new long[] {1, 1, 1};

Kết quả mong đợi:
double[] expected = new double[] {2.0, 0.0};

Giải thích

With epsilon = 0 the agent never explores. It keeps pulling arm 0, whose average goes 2 → 3 → 2, and never finds out arm 1 pays 5. Result: [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

At each step, choose either the forced random arm or the currently best estimated arm.

Gợi ý 2

Update each arm’s value with a running average so old rewards matter less as more pulls accumulate.

Gợi ý 3

Break ties by choosing the smallest-index arm, and remember that only the chosen arm changes each step.

Độ phức tạp mong đợi

O(steps * arms) time, O(arms) extra space

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.

Lời giải đạt tốt nhất của mỗi người. Lời giải nhanh hơn, tốn ít bộ nhớ hơn và được đánh giá cao hơn sẽ đứng trên.

Chưa có lời giải nào đạt. Giải bài này để giành hạng nhất.

Học hỏi từ người khác

Giải pháp cộng đồng

Chưa có giải pháp nào được chia sẻ. Hãy giải thử thách này để đăng giải pháp đầu tiên.