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.
day | worst brute force | Best brute force | Find 728 | Find 728 2 dayepsilon | Find 728 3 dayAvg regret |
---|---|---|---|---|---|
0.1 | 6 | 1274 | 728 | 416 | 7814010 |
0.2 | 9 | 1274 | 728 | 728 | 41611949 |
0.3 | 15 | 1274 | 728 | 728 | 72810767 |
0.4 | 26 | 1274 | 728 | 728 | 7289257 |
0.5 | 45 | 1274 | 728 | 728 | 7288391 |
0.6 | 78 | 1274 | 728 | 728 | 7287577 |
0.7 | 416 | 1274 | 728 | 728 | 7286885 |
0.8 | 728 | 1274 | 728 | 728 | 7286079 |
0.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 | 7285642 |
sum | 8967 | 17836 | 10192 | 98801 | 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)