Skip to main content
Post Undeleted by devyen936
I added a new methodology using greedy episolon as suggested
Source Link

Brute forceThis is as Multi-armed Bandit problem. Based on nature of the best wayrewards I think that choosing explore as most often is optimal.
Play until find theAn optimal outcome is hitting 1274 each time. Unless you findRegret is the 728 indifference between optimal outcome and chosen path.
After calculating the first, second, or third dayaverage regret for each experiment 1000 times with Epsilon values from .1 to 1--meaning what percent of the time will the algo explore vs exploit its known rewards--my conclusion is explore until finding the 1274 is optimal.

dayworst brute forceBest brute forceFind 728Find 728 2 dayepsilon Find 728 3 dayAvg regret
0.1 612747284167814010
0.291274728 72841611949
0.3 15127472872872810767
0.4261274728728 7289257
0.545 12747287287288391
0.6781274728 7287287577
0.7 41612747287287286885
0.8728 12747287287286079
0.912741274728728728
1012741274728728728
1112741274728 728728
1212741274728728728
1312741274728728728
14127412747287287285642
sum8967178361019298801 92305057
import pandas as pd
import numpy as np
import random
import statistics as sts

def explore():
    reward = random.choice(reward_list)
    known_list.append(reward)
    return max(known_list)

def exploit():
    return max(known_list)

def calculate_regret(results):
    opt = np.full(shape=14, fill_value=1274)  # optimal strategy = 17836
    r = sum(opt) - sum(results)
    print(f'Regret: {r}')
    return r


def run_experiment():    
    results = []
    for j in range(14):
        if random.random() > epsilon:
            results.append(exploit())
        else:
            results.append(explore())
    return results

r_list = []
for i in range(1000):
    # E % of days: explore
    # 1 - E of days:  exploit
    epsilon = 1
    reward_list = [6, 9, 15, 26, 45, 78, 416, 728, 1274]
    known_list = [136]

    results = run_experiment()
    r = calculate_regret(results)
    r_list.append(r)

sts.mean(r_list)

Brute force is the best way
Play until find the 1274. Unless you find the 728 in the first, second, or third day

dayworst brute forceBest brute forceFind 728Find 728 2 day Find 728 3 day
1 6127472841678
291274728 728416
3 151274728728728
4261274728728 728
545 1274728728728
6781274728 728728
7 4161274728728728
8728 1274728728728
912741274728728728
1012741274728728728
1112741274728 728728
1212741274728728728
1312741274728728728
1412741274728728728
sum896717836101929880 9230

This is as Multi-armed Bandit problem. Based on nature of the rewards I think that choosing explore as most often is optimal.
An optimal outcome is hitting 1274 each time. Regret is the difference between optimal outcome and chosen path.
After calculating the average regret for each experiment 1000 times with Epsilon values from .1 to 1--meaning what percent of the time will the algo explore vs exploit its known rewards--my conclusion is explore until finding the 1274 is optimal.

epsilon Avg regret
0.1 14010
0.2 11949
0.3 10767
0.4 9257
0.5 8391
0.6 7577
0.7 6885
0.8 6079
0.9 5642
1 5057
import pandas as pd
import numpy as np
import random
import statistics as sts

def explore():
    reward = random.choice(reward_list)
    known_list.append(reward)
    return max(known_list)

def exploit():
    return max(known_list)

def calculate_regret(results):
    opt = np.full(shape=14, fill_value=1274)  # optimal strategy = 17836
    r = sum(opt) - sum(results)
    print(f'Regret: {r}')
    return r


def run_experiment():    
    results = []
    for j in range(14):
        if random.random() > epsilon:
            results.append(exploit())
        else:
            results.append(explore())
    return results

r_list = []
for i in range(1000):
    # E % of days: explore
    # 1 - E of days:  exploit
    epsilon = 1
    reward_list = [6, 9, 15, 26, 45, 78, 416, 728, 1274]
    known_list = [136]

    results = run_experiment()
    r = calculate_regret(results)
    r_list.append(r)

sts.mean(r_list)
Post Deleted by devyen936
replaced code table with Markdown table (more accessible)
Source Link
bobble
  • 10.6k
  • 4
  • 34
  • 86
+-----+-------------------+------------------+----------+-----------------+-----------------+
| day | worst brute force | Best brute force | Find 728 | Find 728 2 day  | Find 728 3 day  |
+-----+-------------------+------------------+----------+-----------------+-----------------+
| 1   | 6                 | 1274             | 728      | 416             | 78              |
| 2   | 9                 | 1274             | 728      | 728             | 416             |
| 3   | 15                | 1274             | 728      | 728             | 728             |
| 4   | 26                | 1274             | 728      | 728             | 728             |
| 5   | 45                | 1274             | 728      | 728             | 728             |
| 6   | 78                | 1274             | 728      | 728             | 728             |
| 7   | 416               | 1274             | 728      | 728             | 728             |
| 8   | 728               | 1274             | 728      | 728             | 728             |
| 9   | 1274              | 1274             | 728      | 728             | 728             |
| 10  | 1274              | 1274             | 728      | 728             | 728             |
| 11  | 1274              | 1274             | 728      | 728             | 728             |
| 12  | 1274              | 1274             | 728      | 728             | 728             |
| 13  | 1274              | 1274             | 728      | 728             | 728             |
| 14  | 1274              | 1274             | 728      | 728             | 728             |
| sum | 8967              | 17836            | 10192    | 9880            | 9230            |
+-----+-------------------+------------------+----------+-----------------+-----------------+
dayworst brute forceBest brute forceFind 728Find 728 2 dayFind 728 3 day
16127472841678
291274728728416
3151274728728728
4261274728728728
5451274728728728
6781274728728728
74161274728728728
87281274728728728
912741274728728728
1012741274728728728
1112741274728728728
1212741274728728728
1312741274728728728
1412741274728728728
sum8967178361019298809230
+-----+-------------------+------------------+----------+-----------------+-----------------+
| day | worst brute force | Best brute force | Find 728 | Find 728 2 day  | Find 728 3 day  |
+-----+-------------------+------------------+----------+-----------------+-----------------+
| 1   | 6                 | 1274             | 728      | 416             | 78              |
| 2   | 9                 | 1274             | 728      | 728             | 416             |
| 3   | 15                | 1274             | 728      | 728             | 728             |
| 4   | 26                | 1274             | 728      | 728             | 728             |
| 5   | 45                | 1274             | 728      | 728             | 728             |
| 6   | 78                | 1274             | 728      | 728             | 728             |
| 7   | 416               | 1274             | 728      | 728             | 728             |
| 8   | 728               | 1274             | 728      | 728             | 728             |
| 9   | 1274              | 1274             | 728      | 728             | 728             |
| 10  | 1274              | 1274             | 728      | 728             | 728             |
| 11  | 1274              | 1274             | 728      | 728             | 728             |
| 12  | 1274              | 1274             | 728      | 728             | 728             |
| 13  | 1274              | 1274             | 728      | 728             | 728             |
| 14  | 1274              | 1274             | 728      | 728             | 728             |
| sum | 8967              | 17836            | 10192    | 9880            | 9230            |
+-----+-------------------+------------------+----------+-----------------+-----------------+
dayworst brute forceBest brute forceFind 728Find 728 2 dayFind 728 3 day
16127472841678
291274728728416
3151274728728728
4261274728728728
5451274728728728
6781274728728728
74161274728728728
87281274728728728
912741274728728728
1012741274728728728
1112741274728728728
1212741274728728728
1312741274728728728
1412741274728728728
sum8967178361019298809230
Source Link

Brute force is the best way
Play until find the 1274. Unless you find the 728 in the first, second, or third day

+-----+-------------------+------------------+----------+-----------------+-----------------+
| day | worst brute force | Best brute force | Find 728 | Find 728 2 day  | Find 728 3 day  |
+-----+-------------------+------------------+----------+-----------------+-----------------+
| 1   | 6                 | 1274             | 728      | 416             | 78              |
| 2   | 9                 | 1274             | 728      | 728             | 416             |
| 3   | 15                | 1274             | 728      | 728             | 728             |
| 4   | 26                | 1274             | 728      | 728             | 728             |
| 5   | 45                | 1274             | 728      | 728             | 728             |
| 6   | 78                | 1274             | 728      | 728             | 728             |
| 7   | 416               | 1274             | 728      | 728             | 728             |
| 8   | 728               | 1274             | 728      | 728             | 728             |
| 9   | 1274              | 1274             | 728      | 728             | 728             |
| 10  | 1274              | 1274             | 728      | 728             | 728             |
| 11  | 1274              | 1274             | 728      | 728             | 728             |
| 12  | 1274              | 1274             | 728      | 728             | 728             |
| 13  | 1274              | 1274             | 728      | 728             | 728             |
| 14  | 1274              | 1274             | 728      | 728             | 728             |
| sum | 8967              | 17836            | 10192    | 9880            | 9230            |
+-----+-------------------+------------------+----------+-----------------+-----------------+