Index: trunk/sources/HeuristicLab.Algorithms.DataAnalysis/3.4/MctsSymbolicRegression/Policies/EpsGreedy.cs
===================================================================
--- trunk/sources/HeuristicLab.Algorithms.DataAnalysis/3.4/MctsSymbolicRegression/Policies/EpsGreedy.cs	(revision 13659)
+++ trunk/sources/HeuristicLab.Algorithms.DataAnalysis/3.4/MctsSymbolicRegression/Policies/EpsGreedy.cs	(revision 13659)
@@ -0,0 +1,89 @@
+﻿using System;
+using System.Collections.Generic;
+using System.Diagnostics.Contracts;
+using System.Linq;
+using System.Text;
+using System.Threading.Tasks;
+using HeuristicLab.Common;
+using HeuristicLab.Core;
+using HeuristicLab.Data;
+using HeuristicLab.Parameters;
+
+namespace HeuristicLab.Algorithms.DataAnalysis.MctsSymbolicRegression.Policies {
+  [Item("EpsilonGreedy", "Epsilon greedy policy with parameter eps to balance between exploitation and exploration")]
+  internal class EpsilonGreedy : PolicyBase {
+    private class ActionStatistics : IActionStatistics {
+      public double SumQuality { get; set; }
+      public double AverageQuality { get { return SumQuality / Tries; } }
+      public int Tries { get; set; }
+      public bool Done { get; set; }
+    }
+    private List<int> buf = new List<int>();
+
+    public IFixedValueParameter<DoubleValue> EpsParameter {
+      get { return (IFixedValueParameter<DoubleValue>)Parameters["Eps"]; }
+    }
+
+    public double Eps {
+      get { return EpsParameter.Value.Value; }
+      set { EpsParameter.Value.Value = value; }
+    }
+
+    private EpsilonGreedy(EpsilonGreedy original, Cloner cloner)
+      : base(original, cloner) {
+    }
+    public EpsilonGreedy()
+      : base() {
+      Parameters.Add(new FixedValueParameter<DoubleValue>("Eps", "Rate of random selection 0 (greedy) <= eps <= 1 (random)", new DoubleValue(0.1)));
+    }
+
+    public override IDeepCloneable Clone(Cloner cloner) {
+      return new EpsilonGreedy(this, cloner);
+    }
+
+    public override int Select(IEnumerable<IActionStatistics> actions, IRandom random) {
+      return Select(actions, random, Eps, buf);
+    }
+
+    public override void Update(IActionStatistics action, double q) {
+      var a = action as ActionStatistics;
+      a.SumQuality += q;
+      a.Tries++;
+    }
+
+    public override IActionStatistics CreateActionStatistics() {
+      return new ActionStatistics();
+    }
+
+    private static int Select(IEnumerable<IActionStatistics> actions, IRandom rand, double c, IList<int> buf) {
+      buf.Clear();
+      if (rand.NextDouble() >= c) {
+        // select best
+        var bestQ = double.NegativeInfinity;
+        int aIdx = -1;
+        foreach (var a in actions) {
+          ++aIdx;
+          if (a.Done) continue;
+          var actionQ = a.Tries > 0 ? a.AverageQuality : double.PositiveInfinity; // always try unvisited actions first
+          if (actionQ > bestQ) {
+            buf.Clear();
+            buf.Add(aIdx);
+            bestQ = actionQ;
+          } else if (actionQ >= bestQ) {
+            buf.Add(aIdx);
+          }
+        }
+        return buf[rand.Next(buf.Count)];
+      } else {
+        // random selection
+        int aIdx = -1;
+        foreach (var a in actions) {
+          ++aIdx;
+          if (a.Done) continue;
+          buf.Add(aIdx);
+        }
+        return buf[rand.Next(buf.Count)];
+      }
+    }
+  }
+}
Index: trunk/sources/HeuristicLab.Algorithms.DataAnalysis/3.4/MctsSymbolicRegression/Policies/IActionStatistics.cs
===================================================================
--- trunk/sources/HeuristicLab.Algorithms.DataAnalysis/3.4/MctsSymbolicRegression/Policies/IActionStatistics.cs	(revision 13659)
+++ trunk/sources/HeuristicLab.Algorithms.DataAnalysis/3.4/MctsSymbolicRegression/Policies/IActionStatistics.cs	(revision 13659)
@@ -0,0 +1,13 @@
+﻿using System;
+using System.Collections.Generic;
+using System.Linq;
+using System.Text;
+using System.Threading.Tasks;
+
+namespace HeuristicLab.Algorithms.DataAnalysis.MctsSymbolicRegression.Policies {
+  public interface IActionStatistics {
+    double AverageQuality { get; }
+    int Tries { get; }
+    bool Done { get; set; }
+  }
+}
Index: trunk/sources/HeuristicLab.Algorithms.DataAnalysis/3.4/MctsSymbolicRegression/Policies/IPolicy.cs
===================================================================
--- trunk/sources/HeuristicLab.Algorithms.DataAnalysis/3.4/MctsSymbolicRegression/Policies/IPolicy.cs	(revision 13659)
+++ trunk/sources/HeuristicLab.Algorithms.DataAnalysis/3.4/MctsSymbolicRegression/Policies/IPolicy.cs	(revision 13659)
@@ -0,0 +1,14 @@
+﻿using System;
+using System.Collections.Generic;
+using System.Linq;
+using System.Text;
+using System.Threading.Tasks;
+using HeuristicLab.Core;
+
+namespace HeuristicLab.Algorithms.DataAnalysis.MctsSymbolicRegression.Policies {
+  public interface IPolicy : IItem {
+    int Select(IEnumerable<IActionStatistics> actions, IRandom random);
+    void Update(IActionStatistics action, double q);
+    IActionStatistics CreateActionStatistics();
+  }
+}
Index: trunk/sources/HeuristicLab.Algorithms.DataAnalysis/3.4/MctsSymbolicRegression/Policies/PolicyBase.cs
===================================================================
--- trunk/sources/HeuristicLab.Algorithms.DataAnalysis/3.4/MctsSymbolicRegression/Policies/PolicyBase.cs	(revision 13659)
+++ trunk/sources/HeuristicLab.Algorithms.DataAnalysis/3.4/MctsSymbolicRegression/Policies/PolicyBase.cs	(revision 13659)
@@ -0,0 +1,36 @@
+﻿using System;
+using System.Collections.Generic;
+using System.Diagnostics.Contracts;
+using System.Linq;
+using System.Text;
+using System.Threading.Tasks;
+using HeuristicLab.Common;
+using HeuristicLab.Core;
+using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
+
+namespace HeuristicLab.Algorithms.DataAnalysis.MctsSymbolicRegression.Policies {
+  [StorableClass]
+  internal abstract class PolicyBase : Item, IParameterizedItem, IPolicy {
+    [Storable]
+    public IKeyedItemCollection<string, IParameter> Parameters { get; private set; }
+
+    [StorableConstructor]
+    private PolicyBase(bool deserializing) : base(deserializing) { }
+    protected PolicyBase(PolicyBase original, Cloner cloner)
+      : base(original, cloner) {
+      Parameters = cloner.Clone(original.Parameters);
+    }
+    protected PolicyBase()
+      : base() {
+      Parameters = new ParameterCollection();
+    }
+
+    public void CollectParameterValues(IDictionary<string, IItem> values) {
+      foreach (var p in Parameters) values.Add(this.ItemName + "." + p.Name, p.ActualValue);
+    }
+
+    public abstract int Select(IEnumerable<IActionStatistics> actions, IRandom random);
+    public abstract void Update(IActionStatistics action, double q);
+    public abstract IActionStatistics CreateActionStatistics();
+  }
+}
Index: trunk/sources/HeuristicLab.Algorithms.DataAnalysis/3.4/MctsSymbolicRegression/Policies/Ucb.cs
===================================================================
--- trunk/sources/HeuristicLab.Algorithms.DataAnalysis/3.4/MctsSymbolicRegression/Policies/Ucb.cs	(revision 13659)
+++ trunk/sources/HeuristicLab.Algorithms.DataAnalysis/3.4/MctsSymbolicRegression/Policies/Ucb.cs	(revision 13659)
@@ -0,0 +1,93 @@
+﻿using System;
+using System.Collections.Generic;
+using System.Diagnostics.Contracts;
+using System.Linq;
+using System.Text;
+using System.Threading.Tasks;
+using HeuristicLab.Common;
+using HeuristicLab.Core;
+using HeuristicLab.Data;
+using HeuristicLab.Parameters;
+
+namespace HeuristicLab.Algorithms.DataAnalysis.MctsSymbolicRegression.Policies {
+  [Item("Ucb Policy", "Ucb with parameter c to balance between exploitation and exploration")]
+  internal class Ucb : PolicyBase {
+    private class ActionStatistics : IActionStatistics {
+      public double SumQuality { get; set; }
+      public double AverageQuality { get { return SumQuality / Tries; } }
+      public int Tries { get; set; }
+      public bool Done { get; set; }
+    }
+    private List<int> buf = new List<int>();
+
+    public IFixedValueParameter<DoubleValue> CParameter {
+      get { return (IFixedValueParameter<DoubleValue>)Parameters["C"]; }
+    }
+
+    public double C {
+      get { return CParameter.Value.Value; }
+      set { CParameter.Value.Value = value; }
+    }
+
+    private Ucb(Ucb original, Cloner cloner)
+      : base(original, cloner) {
+    }
+    public Ucb()
+      : base() {
+      Parameters.Add(new FixedValueParameter<DoubleValue>("C", "Parameter to balance between exploration and exploitation 0 <= c < 100", new DoubleValue(Math.Sqrt(2))));
+    }
+
+    public override IDeepCloneable Clone(Cloner cloner) {
+      return new Ucb(this, cloner);
+    }
+
+    public override int Select(IEnumerable<IActionStatistics> actions, IRandom random) {
+      return Select(actions, random, C, buf);
+    }
+
+    public override void Update(IActionStatistics action, double q) {
+      var a = action as ActionStatistics;
+      a.SumQuality += q;
+      a.Tries++;
+    }
+
+    public override IActionStatistics CreateActionStatistics() {
+      return new ActionStatistics();
+    }
+
+    private static int Select(IEnumerable<IActionStatistics> actions, IRandom rand, double c, IList<int> buf) {
+      // determine total tries of still active actions
+      int totalTries = 0;
+      buf.Clear();
+      int aIdx = -1;
+      foreach (var a in actions) {
+        ++aIdx;
+        if (a.Done) continue;
+        if (a.Tries == 0) buf.Add(aIdx);
+        else totalTries += a.Tries;
+      }
+      // if there are unvisited actions select a random action
+      if (buf.Any()) {
+        return buf[rand.Next(buf.Count)];
+      }
+      Contract.Assert(totalTries > 0);
+      double logTotalTries = Math.Log(totalTries);
+      var bestQ = double.NegativeInfinity;
+      aIdx = -1;
+      foreach (var a in actions) {
+        ++aIdx;
+        if (a.Done) continue;
+        var actionQ = a.AverageQuality + c * Math.Sqrt(logTotalTries / a.Tries);
+        if (actionQ > bestQ) {
+          buf.Clear();
+          buf.Add(aIdx);
+          bestQ = actionQ;
+        } else if (actionQ >= bestQ) {
+          buf.Add(aIdx);
+        }
+      }
+      return buf[rand.Next(buf.Count)];
+    }
+
+  }
+}
Index: trunk/sources/HeuristicLab.Algorithms.DataAnalysis/3.4/MctsSymbolicRegression/Policies/UcbTuned.cs
===================================================================
--- trunk/sources/HeuristicLab.Algorithms.DataAnalysis/3.4/MctsSymbolicRegression/Policies/UcbTuned.cs	(revision 13659)
+++ trunk/sources/HeuristicLab.Algorithms.DataAnalysis/3.4/MctsSymbolicRegression/Policies/UcbTuned.cs	(revision 13659)
@@ -0,0 +1,97 @@
+﻿using System;
+using System.Collections.Generic;
+using System.Diagnostics.Contracts;
+using System.Linq;
+using System.Text;
+using System.Threading.Tasks;
+using HeuristicLab.Common;
+using HeuristicLab.Core;
+using HeuristicLab.Data;
+using HeuristicLab.Parameters;
+
+namespace HeuristicLab.Algorithms.DataAnalysis.MctsSymbolicRegression.Policies {
+  [Item("UcbTuned Policy", "UcbTuned is similar to Ucb but tracks empirical variance. Use parameter c to balance between exploitation and exploration")]
+  internal class UcbTuned : PolicyBase {
+    private class ActionStatistics : IActionStatistics {
+      public double SumQuality { get; set; }
+      public double SumSqrQuality { get; set; }
+      public double AverageQuality { get { return SumQuality / Tries; } }
+      public double QualityVariance { get { return SumSqrQuality / Tries - AverageQuality * AverageQuality; } }
+      public int Tries { get; set; }
+      public bool Done { get; set; }
+    }
+    private List<int> buf = new List<int>();
+
+    public IFixedValueParameter<DoubleValue> CParameter {
+      get { return (IFixedValueParameter<DoubleValue>)Parameters["C"]; }
+    }
+
+    public double C {
+      get { return CParameter.Value.Value; }
+      set { CParameter.Value.Value = value; }
+    }
+
+    private UcbTuned(UcbTuned original, Cloner cloner)
+      : base(original, cloner) {
+    }
+    public UcbTuned()
+      : base() {
+      Parameters.Add(new FixedValueParameter<DoubleValue>("C", "Parameter to balance between exploration and exploitation 0 <= c < 100", new DoubleValue(Math.Sqrt(2))));
+    }
+
+    public override IDeepCloneable Clone(Cloner cloner) {
+      return new UcbTuned(this, cloner);
+    }
+
+    public override int Select(IEnumerable<IActionStatistics> actions, IRandom random) {
+      return Select(actions, random, C, buf);
+    }
+
+    public override void Update(IActionStatistics action, double q) {
+      var a = action as ActionStatistics;
+      a.SumQuality += q;
+      a.SumSqrQuality += q * q;
+      a.Tries++;
+    }
+
+    public override IActionStatistics CreateActionStatistics() {
+      return new ActionStatistics();
+    }
+
+    private static int Select(IEnumerable<IActionStatistics> actions, IRandom rand, double c, IList<int> buf) {
+      // determine total tries of still active actions
+      int totalTries = 0;
+      buf.Clear();
+      int aIdx = -1;
+      foreach (var a in actions) {
+        ++aIdx;
+        if (a.Done) continue;
+        if (a.Tries == 0) buf.Add(aIdx);
+        else totalTries += a.Tries;
+      }
+      // if there are unvisited actions select a random action
+      if (buf.Any()) {
+        return buf[rand.Next(buf.Count)];
+      }
+      Contract.Assert(totalTries > 0);
+      double logTotalTries = Math.Log(totalTries);
+      var bestQ = double.NegativeInfinity;
+      aIdx = -1;
+      foreach (var a in actions.Cast<ActionStatistics>()) {
+        ++aIdx;
+        if (a.Done) continue;
+        var varianceBound = a.QualityVariance + Math.Sqrt(2.0 * logTotalTries / a.Tries);
+        if (varianceBound > 0.25) varianceBound = 0.25;
+        var actionQ = a.AverageQuality + c * Math.Sqrt(logTotalTries / a.Tries * varianceBound);
+        if (actionQ > bestQ) {
+          buf.Clear();
+          buf.Add(aIdx);
+          bestQ = actionQ;
+        } else if (actionQ >= bestQ) {
+          buf.Add(aIdx);
+        }
+      }
+      return buf[rand.Next(buf.Count)];
+    }
+  }
+}
