Index: branches/HeuristicLab.Algorithms.IteratedSentenceConstruction/HeuristicLab.Algorithms.IteratedSymbolicExpressionConstruction/3.3/HeuristicLab.Algorithms.IteratedSymbolicExpressionConstruction-3.3.csproj
===================================================================
--- branches/HeuristicLab.Algorithms.IteratedSentenceConstruction/HeuristicLab.Algorithms.IteratedSymbolicExpressionConstruction/3.3/HeuristicLab.Algorithms.IteratedSymbolicExpressionConstruction-3.3.csproj	(revision 12910)
+++ branches/HeuristicLab.Algorithms.IteratedSentenceConstruction/HeuristicLab.Algorithms.IteratedSymbolicExpressionConstruction/3.3/HeuristicLab.Algorithms.IteratedSymbolicExpressionConstruction-3.3.csproj	(revision 12922)
@@ -161,4 +161,5 @@
     <Compile Include="Plugin.cs" />
     <Compile Include="Policies\BoltzmannExplorationSymbolicExpressionConstructionPolicy.cs" />
+    <Compile Include="Policies\UcbTunedSymbolicExpressionConstructionPolicy.cs" />
     <Compile Include="Policies\EpsGreedySymbolicExpressionConstructionPolicy.cs" />
     <Compile Include="Policies\SymbolicExpressionConstructionPolicyBase.cs" />
@@ -168,4 +169,5 @@
     </Compile>
     <Compile Include="Properties\AssemblyInfo.cs" />
+    <Compile Include="QualityFunctions\TabularQualityFunctionBase.cs" />
     <Compile Include="QualityFunctions\TabularAvgQualityFunction.cs" />
     <Compile Include="QualityFunctions\TabularMaxQualityFunction.cs" />
Index: branches/HeuristicLab.Algorithms.IteratedSentenceConstruction/HeuristicLab.Algorithms.IteratedSymbolicExpressionConstruction/3.3/Interfaces/ITabularQualityFunction.cs
===================================================================
--- branches/HeuristicLab.Algorithms.IteratedSentenceConstruction/HeuristicLab.Algorithms.IteratedSymbolicExpressionConstruction/3.3/Interfaces/ITabularQualityFunction.cs	(revision 12910)
+++ branches/HeuristicLab.Algorithms.IteratedSentenceConstruction/HeuristicLab.Algorithms.IteratedSymbolicExpressionConstruction/3.3/Interfaces/ITabularQualityFunction.cs	(revision 12922)
@@ -9,4 +9,5 @@
   // represents quality functions that use a table representation for states & actions and can therefore return the number of tries for each state/action pair
   public interface ITabularQualityFunction : IQualityFunction {
+    double QVariance(object state, int action); // estimate for the variance of observed rewards
     int Tries(object state, int action);
   }
Index: branches/HeuristicLab.Algorithms.IteratedSentenceConstruction/HeuristicLab.Algorithms.IteratedSymbolicExpressionConstruction/3.3/Policies/SymbolicExpressionConstructionPolicyBase.cs
===================================================================
--- branches/HeuristicLab.Algorithms.IteratedSentenceConstruction/HeuristicLab.Algorithms.IteratedSymbolicExpressionConstruction/3.3/Policies/SymbolicExpressionConstructionPolicyBase.cs	(revision 12910)
+++ branches/HeuristicLab.Algorithms.IteratedSentenceConstruction/HeuristicLab.Algorithms.IteratedSymbolicExpressionConstruction/3.3/Policies/SymbolicExpressionConstructionPolicyBase.cs	(revision 12922)
@@ -46,4 +46,5 @@
 
     protected SymbolicExpressionConstructionPolicyBase() {
+
     }
 
@@ -106,5 +107,8 @@
         // and add child node to parent
         var childNode = alts[selectedIdx].CreateTreeNode();
-        if (childNode.HasLocalParameters) childNode.ResetLocalParameters(Random);
+        if (childNode.HasLocalParameters) {
+          throw new NotSupportedException("Symbols with parameters are not supported by construction policies for symbolic expressions. Try to reformulate the problem so that only discrete actions are necessary");
+          // childNode.ResetLocalParameters(Random);
+        }
 
         Contract.Assert(parent.SubtreeCount == childIdx);
@@ -113,5 +117,5 @@
 
         // push new slots 
-        for (int chIdx = childNode.Symbol.MinimumArity - 1; chIdx >= 0; chIdx--) {
+        for (int chIdx = g.GetMinimumSubtreeCount(childNode.Symbol) - 1; chIdx >= 0; chIdx--) {
           int minForChild = g.GetAllowedChildSymbols(childNode.Symbol, chIdx).Min(a => g.GetMinimumExpressionLength(a)); // min length of all possible alts for the slot
           openSlots.Push(new Slot() { parent = childNode, childIdx = chIdx, minSize = minForChild });
Index: branches/HeuristicLab.Algorithms.IteratedSentenceConstruction/HeuristicLab.Algorithms.IteratedSymbolicExpressionConstruction/3.3/Policies/UcbTunedSymbolicExpressionConstructionPolicy.cs
===================================================================
--- branches/HeuristicLab.Algorithms.IteratedSentenceConstruction/HeuristicLab.Algorithms.IteratedSymbolicExpressionConstruction/3.3/Policies/UcbTunedSymbolicExpressionConstructionPolicy.cs	(revision 12922)
+++ branches/HeuristicLab.Algorithms.IteratedSentenceConstruction/HeuristicLab.Algorithms.IteratedSymbolicExpressionConstruction/3.3/Policies/UcbTunedSymbolicExpressionConstructionPolicy.cs	(revision 12922)
@@ -0,0 +1,85 @@
+﻿using System;
+using System.Collections.Generic;
+using System.Linq;
+using HeuristicLab.Common;
+using HeuristicLab.Core;
+using HeuristicLab.Data;
+using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding;
+using HeuristicLab.Parameters;
+using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
+using HeuristicLab.PluginInfrastructure;
+using HeuristicLab.Random;
+
+namespace HeuristicLab.Algorithms.IteratedSymbolicExpressionConstruction {
+  [StorableClass]
+  [Item("UcbTunedSymbolicExpressionConstructionPolicy", "Also uses an estimate of the variance")]
+  public class UcbTunedSymbolicExpressionConstructionPolicy : SymbolicExpressionConstructionPolicyBase {
+    public double R {
+      get { return ((IFixedValueParameter<DoubleValue>)Parameters["R"]).Value.Value; }
+      set { ((IFixedValueParameter<DoubleValue>)Parameters["R"]).Value.Value = value; }
+    }
+
+    public ITabularQualityFunction QualityFunction {
+      get {
+        return ((IValueParameter<ITabularQualityFunction>)Parameters["Quality function"]).Value;
+      }
+      set { ((IValueParameter<ITabularQualityFunction>)Parameters["Quality function"]).Value = value; }
+    }
+
+
+    protected UcbTunedSymbolicExpressionConstructionPolicy(UcbTunedSymbolicExpressionConstructionPolicy original, Cloner cloner)
+      : base(original, cloner) {
+    }
+
+    [StorableConstructor]
+    protected UcbTunedSymbolicExpressionConstructionPolicy(bool deserializing) : base(deserializing) { }
+
+
+    public UcbTunedSymbolicExpressionConstructionPolicy()
+      : base() {
+      Parameters.Add(new FixedValueParameter<DoubleValue>("R", "The weighting factor for the confidence bound (should be scaled based on the range or the fitness values)", new DoubleValue(1.0)));
+      Parameters.Add(new ValueParameter<ITabularQualityFunction>("Quality function", "The quality function to use", new TabularAvgQualityFunction()));
+    }
+
+    protected sealed override int Select(object state, IEnumerable<int> actions, IRandom random) {
+
+      // find best action
+      var bestActions = new List<int>();
+      var bestQuality = double.NegativeInfinity;
+      int totalTries = actions.Sum(a => QualityFunction.Tries(state, a));
+      foreach (var a in actions) {
+        double quality;
+        if (QualityFunction.Tries(state, a) == 0) {
+          quality = double.PositiveInfinity;
+        } else {
+          double v = QualityFunction.QVariance(state, a) + Math.Sqrt(2 * Math.Log(totalTries) / QualityFunction.Tries(state, a));
+          quality = QualityFunction.Q(state, a) + R * Math.Sqrt(Math.Log(totalTries) / QualityFunction.Tries(state, a) * v);
+        }
+        if (quality >= bestQuality) {
+          if (quality > bestQuality) {
+            bestActions.Clear();
+            bestQuality = quality;
+          }
+          bestActions.Add(a);
+        }
+      }
+      return bestActions.SampleRandom(random, 1).First();
+    }
+
+    public sealed override void Update(IEnumerable<Tuple<object, int>> stateActionSequence, double quality) {
+      foreach (var t in stateActionSequence) {
+        var state = t.Item1;
+        var action = t.Item2;
+        QualityFunction.Update(state, action, quality);
+      }
+    }
+
+    protected override object CreateState(ISymbolicExpressionTreeNode root, List<int> actions, ISymbolicExpressionTreeNode parent, int childIdx) {
+      return QualityFunction.StateFunction.CreateState(root, actions, parent, childIdx);
+    }
+
+    public override IDeepCloneable Clone(HeuristicLab.Common.Cloner cloner) {
+      return new UcbTunedSymbolicExpressionConstructionPolicy(this, cloner);
+    }
+  }
+}
Index: branches/HeuristicLab.Algorithms.IteratedSentenceConstruction/HeuristicLab.Algorithms.IteratedSymbolicExpressionConstruction/3.3/QualityFunctions/TabularAvgQualityFunction.cs
===================================================================
--- branches/HeuristicLab.Algorithms.IteratedSentenceConstruction/HeuristicLab.Algorithms.IteratedSymbolicExpressionConstruction/3.3/QualityFunctions/TabularAvgQualityFunction.cs	(revision 12910)
+++ branches/HeuristicLab.Algorithms.IteratedSentenceConstruction/HeuristicLab.Algorithms.IteratedSymbolicExpressionConstruction/3.3/QualityFunctions/TabularAvgQualityFunction.cs	(revision 12922)
@@ -9,59 +9,8 @@
   [StorableClass]
   [Item("TabularAvgQualityFunction", "")]
-  internal class TabularAvgQualityFunction : ParameterizedNamedItem, ITabularQualityFunction {
-    [Storable]
-    private readonly Dictionary<object, Dictionary<int, double>> q = new Dictionary<object, Dictionary<int, double>>();
-    [Storable]
-    private readonly Dictionary<object, Dictionary<int, int>> tries = new Dictionary<object, Dictionary<int, int>>();
+  internal class TabularAvgQualityFunction : TabularQualityFunctionBase {
 
-    public IStateFunction StateFunction {
-      get {
-        return ((IValueParameter<IStateFunction>)Parameters["State function"]).Value;
-      }
-      set { ((IValueParameter<IStateFunction>)Parameters["State function"]).Value = value; }
-    }
-
-    public TabularAvgQualityFunction() {
-      Parameters.Add(new ValueParameter<IStateFunction>("State function", "The function that is used to map partial trees to states", new DefaultStateFunction()));
-    }
-
-    public double Q(object state, int action) {
-      // an action that has never been tried has q == infinity
-      Dictionary<int, double> stateActionQualities;
-      if (!q.TryGetValue(state, out stateActionQualities)) return double.PositiveInfinity;
-      double quality;
-      if (!stateActionQualities.TryGetValue(action, out quality)) return double.PositiveInfinity;
-      return quality;
-    }
-
-    public void Update(object state, int action, double observedQuality) {
-      Dictionary<int, int> stateActionTries;
-      if (!tries.TryGetValue(state, out stateActionTries)) {
-        stateActionTries = new Dictionary<int, int>();
-        tries.Add(state, stateActionTries);
-      }
-      Dictionary<int, double> stateActionQualities = null;
-      if (!q.TryGetValue(state, out stateActionQualities)) {
-        stateActionQualities = new Dictionary<int, double>();
-        q.Add(state, stateActionQualities);
-      }
-      int t;
-      if (!stateActionTries.TryGetValue(action, out t)) {
-        t = 0;
-        stateActionTries.Add(action, t + 1);
-        stateActionQualities.Add(action, observedQuality);
-      } else {
-        stateActionTries[action] = t + 1;
-        var delta = observedQuality - stateActionQualities[action];
-        stateActionQualities[action] = stateActionQualities[action] + (1.0 / (t + 1)) * delta; // incremental calculation of average
-      }
-    }
-
-    public int Tries(object state, int action) {
-      Dictionary<int, int> stateTries;
-      if (!tries.TryGetValue(state, out stateTries)) return 0;
-      int stateActionTries;
-      if (!stateTries.TryGetValue(action, out stateActionTries)) return 0;
-      return stateActionTries;
+    public TabularAvgQualityFunction()
+      : base() {
     }
 
@@ -71,6 +20,4 @@
     protected TabularAvgQualityFunction(TabularAvgQualityFunction original, Cloner cloner)
       : base(original, cloner) {
-      this.q = new Dictionary<object, Dictionary<int, double>>(original.q);
-      this.tries = new Dictionary<object, Dictionary<int, int>>(original.tries);
     }
     public override IDeepCloneable Clone(Cloner cloner) {
@@ -79,11 +26,7 @@
     #endregion
 
-    public void InitializeState() {
-      ClearState();
-    }
-
-    public void ClearState() {
-      q.Clear();
-      tries.Clear();
+    protected override double CalculateNewQ(object state, int action, double observedQuality) {
+      var delta = observedQuality - Q(state, action);
+      return Q(state, action) + (1.0 / Tries(state, action)) * delta; // iterative calculation of mean
     }
   }
Index: branches/HeuristicLab.Algorithms.IteratedSentenceConstruction/HeuristicLab.Algorithms.IteratedSymbolicExpressionConstruction/3.3/QualityFunctions/TabularMaxQualityFunction.cs
===================================================================
--- branches/HeuristicLab.Algorithms.IteratedSentenceConstruction/HeuristicLab.Algorithms.IteratedSymbolicExpressionConstruction/3.3/QualityFunctions/TabularMaxQualityFunction.cs	(revision 12910)
+++ branches/HeuristicLab.Algorithms.IteratedSentenceConstruction/HeuristicLab.Algorithms.IteratedSymbolicExpressionConstruction/3.3/QualityFunctions/TabularMaxQualityFunction.cs	(revision 12922)
@@ -9,58 +9,8 @@
   [StorableClass]
   [Item("TabularMaxQualityFunction", "")]
-  internal class TabularMaxQualityFunction : ParameterizedNamedItem, ITabularQualityFunction {
-    [Storable]
-    private readonly Dictionary<object, Dictionary<int, double>> q = new Dictionary<object, Dictionary<int, double>>();
-    [Storable]
-    private readonly Dictionary<object, Dictionary<int, int>> tries = new Dictionary<object, Dictionary<int, int>>();
+  internal class TabularMaxQualityFunction : TabularQualityFunctionBase {
 
-    public IStateFunction StateFunction {
-      get {
-        return ((IValueParameter<IStateFunction>)Parameters["State function"]).Value;
-      }
-      set { ((IValueParameter<IStateFunction>)Parameters["State function"]).Value = value; }
-    }
-
-    public TabularMaxQualityFunction() {
-      Parameters.Add(new ValueParameter<IStateFunction>("State function", "The function that is used to map partial trees to states", new DefaultStateFunction()));
-    }
-
-    public double Q(object state, int action) {
-      // an action that has never been tried has q == infinity
-      Dictionary<int, double> stateActionQualities;
-      if (!q.TryGetValue(state, out stateActionQualities)) return double.PositiveInfinity;
-      double quality;
-      if (!stateActionQualities.TryGetValue(action, out quality)) return double.PositiveInfinity;
-      return quality;
-    }
-
-    public void Update(object state, int action, double observedQuality) {
-      Dictionary<int, int> stateActionTries;
-      if (!tries.TryGetValue(state, out stateActionTries)) {
-        stateActionTries = new Dictionary<int, int>();
-        tries.Add(state, stateActionTries);
-      }
-      Dictionary<int, double> stateActionQualities = null;
-      if (!q.TryGetValue(state, out stateActionQualities)) {
-        stateActionQualities = new Dictionary<int, double>();
-        q.Add(state, stateActionQualities);
-      }
-      int t;
-      if (!stateActionTries.TryGetValue(action, out t)) {
-        t = 0;
-        stateActionTries.Add(action, t + 1);
-        stateActionQualities.Add(action, observedQuality);
-      } else {
-        stateActionTries[action] = t + 1;
-        stateActionQualities[action] = Math.Max(stateActionQualities[action], observedQuality);
-      }
-    }
-
-    public int Tries(object state, int action) {
-      Dictionary<int, int> stateTries;
-      if (!tries.TryGetValue(state, out stateTries)) return 0;
-      int stateActionTries;
-      if (!stateTries.TryGetValue(action, out stateActionTries)) return 0;
-      return stateActionTries;
+    public TabularMaxQualityFunction()
+      : base() {
     }
 
@@ -70,6 +20,4 @@
     protected TabularMaxQualityFunction(TabularMaxQualityFunction original, Cloner cloner)
       : base(original, cloner) {
-      this.q = new Dictionary<object, Dictionary<int, double>>(original.q);
-      this.tries = new Dictionary<object, Dictionary<int, int>>(original.tries);
     }
     public override IDeepCloneable Clone(Cloner cloner) {
@@ -78,11 +26,6 @@
     #endregion
 
-    public void InitializeState() {
-      ClearState();
-    }
-
-    public void ClearState() {
-      q.Clear();
-      tries.Clear();
+    protected override double CalculateNewQ(object state, int action, double observedQuality) {
+      return Math.Max(Q(state, action), observedQuality);
     }
   }
Index: branches/HeuristicLab.Algorithms.IteratedSentenceConstruction/HeuristicLab.Algorithms.IteratedSymbolicExpressionConstruction/3.3/QualityFunctions/TabularQualityFunctionBase.cs
===================================================================
--- branches/HeuristicLab.Algorithms.IteratedSentenceConstruction/HeuristicLab.Algorithms.IteratedSymbolicExpressionConstruction/3.3/QualityFunctions/TabularQualityFunctionBase.cs	(revision 12922)
+++ branches/HeuristicLab.Algorithms.IteratedSentenceConstruction/HeuristicLab.Algorithms.IteratedSymbolicExpressionConstruction/3.3/QualityFunctions/TabularQualityFunctionBase.cs	(revision 12922)
@@ -0,0 +1,111 @@
+﻿using System;
+using System.Collections.Generic;
+using HeuristicLab.Common;
+using HeuristicLab.Core;
+using HeuristicLab.Parameters;
+using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
+
+namespace HeuristicLab.Algorithms.IteratedSymbolicExpressionConstruction {
+  [StorableClass]
+  internal abstract class TabularQualityFunctionBase : ParameterizedNamedItem, ITabularQualityFunction {
+    [Storable]
+    private readonly Dictionary<object, Dictionary<int, double>> q = new Dictionary<object, Dictionary<int, double>>();
+    [Storable]
+    private readonly Dictionary<object, Dictionary<int, double>> qVariance = new Dictionary<object, Dictionary<int, double>>();
+    [Storable]
+    private readonly Dictionary<object, Dictionary<int, int>> tries = new Dictionary<object, Dictionary<int, int>>();
+
+    public IStateFunction StateFunction {
+      get {
+        return ((IValueParameter<IStateFunction>)Parameters["State function"]).Value;
+      }
+      set { ((IValueParameter<IStateFunction>)Parameters["State function"]).Value = value; }
+    }
+
+    protected TabularQualityFunctionBase()
+      : base() {
+      Parameters.Add(new ValueParameter<IStateFunction>("State function", "The function that is used to map partial trees to states", new DefaultStateFunction()));
+    }
+
+    public int Tries(object state, int action) {
+      Dictionary<int, int> stateTries;
+      if (!tries.TryGetValue(state, out stateTries)) return 0;
+      int stateActionTries;
+      if (!stateTries.TryGetValue(action, out stateActionTries)) return 0;
+      return stateActionTries;
+    }
+
+    public double Q(object state, int action) {
+      // an action that has never been tried has q == infinity
+      Dictionary<int, double> stateActionQualities;
+      if (!q.TryGetValue(state, out stateActionQualities)) return double.PositiveInfinity;
+      double quality;
+      if (!stateActionQualities.TryGetValue(action, out quality)) return double.PositiveInfinity;
+      return quality;
+    }
+
+    public double QVariance(object state, int action) {
+      // an action that has never been tried has qVariance == infinity
+      Dictionary<int, double> stateActionVariances;
+      if (!qVariance.TryGetValue(state, out stateActionVariances)) return double.PositiveInfinity;
+      double var;
+      if (!stateActionVariances.TryGetValue(action, out var)) return double.PositiveInfinity;
+      return var / Tries(state, action);
+    }
+
+    public virtual void Update(object state, int action, double observedQuality) {
+      Dictionary<int, int> stateActionTries;
+      if (!tries.TryGetValue(state, out stateActionTries)) {
+        stateActionTries = new Dictionary<int, int>();
+        tries.Add(state, stateActionTries);
+      }
+      Dictionary<int, double> stateActionQualities = null;
+      if (!q.TryGetValue(state, out stateActionQualities)) {
+        stateActionQualities = new Dictionary<int, double>();
+        q.Add(state, stateActionQualities);
+      }
+      Dictionary<int, double> stateActionVariances = null;
+      if (!qVariance.TryGetValue(state, out stateActionVariances)) {
+        stateActionVariances = new Dictionary<int, double>();
+        qVariance.Add(state, stateActionVariances);
+      }
+      int t;
+      if (!stateActionTries.TryGetValue(action, out t)) {
+        t = 0;
+        stateActionTries.Add(action, t + 1);
+        stateActionQualities.Add(action, observedQuality);
+        stateActionVariances.Add(action, 0); // naive initialization
+      } else {
+        stateActionTries[action] = t + 1;
+        var delta = observedQuality - stateActionQualities[action];
+        var curMean = CalculateNewQ(state, action, observedQuality);
+        stateActionQualities[action] = curMean;
+        stateActionVariances[action] = stateActionVariances[action] + delta * (observedQuality - curMean); // iterative calculation of mean
+      }
+    }
+
+    protected abstract double CalculateNewQ(object state, int action, double observedQuality);
+
+
+    #region item
+    [StorableConstructor]
+    protected TabularQualityFunctionBase(bool deserializing) : base(deserializing) { }
+    protected TabularQualityFunctionBase(TabularQualityFunctionBase original, Cloner cloner)
+      : base(original, cloner) {
+      this.q = new Dictionary<object, Dictionary<int, double>>(original.q);
+      this.qVariance = new Dictionary<object, Dictionary<int, double>>(original.qVariance);
+      this.tries = new Dictionary<object, Dictionary<int, int>>(original.tries);
+    }
+    #endregion
+
+    public void InitializeState() {
+      ClearState();
+    }
+
+    public void ClearState() {
+      q.Clear();
+      tries.Clear();
+      qVariance.Clear();
+    }
+  }
+}
Index: branches/HeuristicLab.Algorithms.IteratedSentenceConstruction/HeuristicLab.Algorithms.IteratedSymbolicExpressionConstruction/3.3/SearchTree.cs
===================================================================
--- branches/HeuristicLab.Algorithms.IteratedSentenceConstruction/HeuristicLab.Algorithms.IteratedSymbolicExpressionConstruction/3.3/SearchTree.cs	(revision 12910)
+++ branches/HeuristicLab.Algorithms.IteratedSentenceConstruction/HeuristicLab.Algorithms.IteratedSymbolicExpressionConstruction/3.3/SearchTree.cs	(revision 12922)
@@ -62,9 +62,8 @@
 
     private void RemoveRecursively(Node node) {
-      if (node == null) return;
       // when the last child has been removed we must remove the current node from it's parent
-      if (node.children.All(ch => ch == null) && node.parent != null) {
+      while (node.parent != null && node.children.All(ch => ch == null)) {
         node.parent.children[Array.IndexOf(node.parent.children, node)] = null;
-        RemoveRecursively(node.parent);
+        node = node.parent;
       }
     }
