Free cookie consent management tool by TermsFeed Policy Generator

source: branches/HeuristicLab.Problems.GrammaticalOptimization-gkr/HeuristicLab.Algorithms.Bandits/Policies/UCB1Policy.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.6 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 UCB1Policy : IBanditPolicy {
12    public double MaxReward { get; private set; }
13    public UCB1Policy(double maxReward = 1.0) {
14      this.MaxReward = maxReward;
15    }
16    public int SelectAction(Random random, IEnumerable<IBanditPolicyActionInfo> actionInfos) {
17      var myActionInfos = actionInfos.OfType<DefaultPolicyActionInfo>();
18      double bestQ = double.NegativeInfinity;
19      int totalTries = myActionInfos.Sum(a => a.Tries);
20
21      var bestActions = new List<int>();
22      int aIdx = -1;
23      foreach (var aInfo in myActionInfos) {
24        aIdx++;
25        double q;
26        if (aInfo.Tries == 0) {
27          q = double.PositiveInfinity;
28        } else {
29
30          q = aInfo.SumReward / aInfo.Tries + MaxReward * Math.Sqrt((2 * Math.Log(totalTries)) / aInfo.Tries);
31        }
32        if (q > bestQ) {
33          bestQ = q;
34          bestActions.Clear();
35          bestActions.Add(aIdx);
36        } else if (q.IsAlmost(bestQ)) {
37          bestActions.Add(aIdx);
38        }
39      }
40      Debug.Assert(bestActions.Any());
41      return bestActions.SelectRandom(random);
42    }
43
44    public IBanditPolicyActionInfo CreateActionInfo() {
45      return new DefaultPolicyActionInfo();
46    }
47    public override string ToString() {
48      return "UCB1Policy";
49    }
50  }
51}
Note: See TracBrowser for help on using the repository browser.