Free cookie consent management tool by TermsFeed Policy Generator

source:branches/HeuristicLab.Problems.GrammaticalOptimization-gkr/HeuristicLab.Algorithms.Bandits/Policies/UCB1TunedPolicy.cs@12876

Last change on this file since 12876 was 12876, checked in by gkronber, 8 years ago

#2283: implemented first crude version of extreme hunter algorithm in branch

File size: 1.9 KB
Line
1using System;
2using System.Collections.Generic;
3using System.Diagnostics;
4using System.Linq;
5using System.Text;
7using HeuristicLab.Common;
8
9namespace HeuristicLab.Algorithms.Bandits.BanditPolicies {
10  // policy for k-armed bandit (see Auer et al. 2002)
11  // specific to Bernoulli distributed rewards
12  public class UCB1TunedPolicy : IBanditPolicy {
13
14    public int SelectAction(Random random, IEnumerable<IBanditPolicyActionInfo> actionInfos) {
15      var myActionInfos = actionInfos.OfType<MeanAndVariancePolicyActionInfo>();
16
17      int totalTries = myActionInfos.Sum(a => a.Tries);
18
19      int aIdx = -1;
20      double bestQ = double.NegativeInfinity;
21      var bestActions = new List<int>();
22      foreach (var aInfo in myActionInfos) {
23        aIdx++;
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();
39        } else if (q.IsAlmost(bestQ)) {
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.