Free cookie consent management tool by TermsFeed Policy Generator

source: branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/BanditPolicies/UCB1TunedPolicy.cs @ 11792

Last change on this file since 11792 was 11792, checked in by gkronber, 9 years ago

#2283 work-in-progress commit (does not compile)

File size: 1.9 KB
Line 
1using System;
2using System.Collections.Generic;
3using System.Diagnostics;
4using System.Linq;
5using System.Text;
6using System.Threading.Tasks;
7using HeuristicLab.Common;
8
9namespace HeuristicLab.Algorithms.Bandits.BanditPolicies {
10  // policy for k-armed bandit (see Auer et al. 2002)
11  public class UCB1TunedPolicy : IBanditPolicy {
12
13    public int SelectAction(Random random, IEnumerable<IBanditPolicyActionInfo> actionInfos) {
14      var myActionInfos = actionInfos.OfType<MeanAndVariancePolicyActionInfo>();
15
16      int totalTries = myActionInfos.Where(a => !a.Disabled).Sum(a => a.Tries);
17
18      int aIdx = -1;
19      double bestQ = double.NegativeInfinity;
20      var bestActions = new List<int>();
21      foreach (var aInfo in myActionInfos) {
22        aIdx++;
23        if (aInfo.Disabled) continue;
24        double q;
25        if (aInfo.Tries == 0) {
26          q = double.PositiveInfinity;
27        } else {
28          var sumReward = aInfo.SumReward;
29          var tries = aInfo.Tries;
30
31          var avgReward = sumReward / tries;
32          q = avgReward + Math.Sqrt((Math.Log(totalTries) / tries) * Math.Min(1.0 / 4, V(aInfo, totalTries)));
33          // 1/4 is upper bound of bernoulli distributed variable
34        }
35        if (q > bestQ) {
36          bestQ = q;
37          bestActions.Clear();
38          bestActions.Add(aIdx);
39        } else if (q == bestQ) {
40          bestActions.Add(aIdx);
41        }
42      }
43      Debug.Assert(bestActions.Any());
44
45      return bestActions.SelectRandom(random);
46    }
47
48    public IBanditPolicyActionInfo CreateActionInfo() {
49      return new MeanAndVariancePolicyActionInfo();
50    }
51
52    private double V(MeanAndVariancePolicyActionInfo actionInfo, int totalTries) {
53      var s = actionInfo.Tries;
54      return actionInfo.RewardVariance + Math.Sqrt(2 * Math.Log(totalTries) / s);
55    }
56
57    public override string ToString() {
58      return "UCB1TunedPolicy";
59    }
60  }
61}
Note: See TracBrowser for help on using the repository browser.