<commit_before>package burlap.behavior.singleagent.planning.stochastic.sparsesampling;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;


import burlap.behavior.singleagent.Policy;
import burlap.behavior.singleagent.QValue;
import burlap.behavior.singleagent.ValueFunctionInitialization;
import burlap.behavior.singleagent.options.Option;
import burlap.behavior.singleagent.planning.OOMDPPlanner;
import burlap.behavior.singleagent.planning.QComputablePlanner;
import burlap.behavior.statehashing.NameDependentStateHashFactory;
import burlap.behavior.statehashing.StateHashFactory;
import burlap.behavior.statehashing.StateHashTuple;
import burlap.debugtools.DPrint;
import burlap.oomdp.core.AbstractGroundedAction;
import burlap.oomdp.core.Domain;
import burlap.oomdp.core.State;
import burlap.oomdp.core.TerminalFunction;
import burlap.oomdp.core.TransitionProbability;
import burlap.oomdp.singleagent.Action;
import burlap.oomdp.singleagent.GroundedAction;
import burlap.oomdp.singleagent.RewardFunction;

/**
 * An implementation of the Sparse Sampling (SS) [1] planning algorithm. SS's computational complexity is indepdent of the state space size, which makes it appealing
 * for exponentially large or infinite state space MDPs and it guarantees epsilon optimal planning under certain conditions (use the {@link #setHAndCByMDPError(double, double, int)}
 * method to ensure this, however, the required horizon and C will probably be intractably large). SS must replan for every new state it sees, so an agent following it in general must replan after every step it takes in the real world. Using a
 * Q-based {@link Policy} object, will ensure this behavior because this algorithm will call the planner whenever it's quried for the Q-value for a state it has not seen.
 * <p/>
 * The algorithm operates by building a tree frome the source initial state. The tree is built by sampling C outcome states for each possible state-action pair, thereby generating new
 * state nodes in the tree. The tree is built out to a fixed height H and then in a tail recursive way, the Q-value and state value is estimated using a Bellman update as if the C samples perfectly defined
 * the transition dyanamics. Because the values are are based on fixed horizon and computed in a tail recusive way, only one bellman update is required per node.
 * <p/>
 * Although the complexity of the algorithm is indepdent of the state space size, it is exponential in the height of the tree, so if a large tree height is required
 * to make good value function estimates, this algorithm may not be appropriate. Therefore, when rewards are sparse or uniform except at a distant horizon, this may not be an appropriate
 * algorithm choice.
 * <p/>
 * By default, this classs will remember the estimated Q-value for every state from which the {@link #planFromState(State)} method was called (which will be indirectly called
 * by the Q-value query methods if it does not have the Q-value for it) and it will also remember the value of state tree nodes it computed so that they may be reused in
 * subsequent tree creations, thereby limiting the amount of additional computation required. However, if memory is scarce, the class can be told to forget all prior planning
 * results, except the Q-value estimate for the most recently planned for state, by using the {@link #forgetPreviousPlanResults} method.
 * <p/>
 * By default, the C parameter (number of state transition samples) is fixed for all nodes; however, it may also be set to use a variable C that reduces the number
 * of sampled states the further down in the tree it is according to C_i = C_0 * gamma^(2i), where i is the depth of the node from the root and gamma is the discount
 * factor.
 * <p/>
 * By default, the state value of leafs will be set to 0, but this value can be changed by providing a {@link ValueFunctionInitialization} object via the
 * {@link #setValueForLeafNodes(ValueFunctionInitialization)} method. Using a non-zero heuristic value may reduce the need for a large tree height.
 * <p/>
 * This class will work with {@link Option}s, but including options will necessarily *increase* the computational complexity, so they are not reccommeneded.
 * <p/>
 * This class requires a {@link StateHashFactory}; if the domain is continuous, just use a {@link NameDependentStateHashFactory} instance.
 * <p/>
 * This class can optionally be set to not use sampling and instead use the full Bellman update, which results in the exact finite horizon Q-value being computed.
 * However, this should only be done when the number of possible state transitions is small and when the full model for the domain is defined (that is, the
 * {@link Action#getTransitions(State, String[])} method is defined). To set this class to comptue the exact finite horizon value function, use the
 * {@link #setComputeExactValueFunction(boolean)} method. Note that you cannot use {@link Option}s when using the fully Bellman update, because that would
 * required factored access to the probability of each length of each transition, which is not available from Options (it's aggregated into the transition function
 * itself). An exception will be thrown if {@link Option}s are used with the full Bellman transitions.
 * <p/>
 * 
 * 
 * 1. Kearns, Michael, <NAME>, and <NAME>. "A sparse sampling algorithm for near-optimal planning in large Markov decision processes." 
 * Machine Learning 49.2-3 (2002): 193-208.
 * 
 * 
 * @author <NAME>
 *
 */
public class SparseSampling extends OOMDPPlanner implements QComputablePlanner{

	/**
	 * The height of the tree
	 */
	protected int h;
	
	/**
	 * The number of transition dynamics samples (for the root if depth-variable C is used)
	 */
	protected int c;
	
	/**
	 * Whether the number of transition dyanmic samples should scale with the depth of the node. Default is false.
	 */
	protected boolean useVariableC = false;
	
	/**
	 * Whether previous planning results should be forgetten or reused; default is reused (false).
	 */
	protected boolean forgetPreviousPlanResults = false;
	
	/**
	 * The state value used for leaf nodes; default is zero.
	 */
	protected ValueFunctionInitialization vinit = new ValueFunctionInitialization.ConstantValueFunctionInitialization();
	
	
	/**
	 * This parameter indicates whether the exact finite horizon value function is computed or whether sparse sampling
	 * to estimate should be used. The default is false: to use sparse sampling.
	 */
	protected boolean computeExactValueFunction = false;
	
	
	/**
	 * The tree nodes indexed by state and height.
	 */
	protected Map<HashedHeightState, StateNode> nodesByHeight;
	
	/**
	 * The root state node Q-values that have been estimated by previous planning calls.
	 */
	protected Map<StateHashTuple, List<QValue>> rootLevelQValues;
	
	
	/**
	 * The total number of pseudo-Bellman updates
	 */
	protected int numUpdates = 0;
	
	
	
	/**
	 * The debug code used for printing planning information.
	 */
	protected int debugCode = 7369430;
	
	
	/**
	 * Initializes. Note that you can have h and c set to values that ensure epsilon optimality by using the {@link #setHAndCByMDPError(double, double, int)} method, but in
	 * general this will result in very large values that will be intractable. If you set c = -1, then the full transition dynamics will be used. You should
	 * only use the full transition dynanics if the number of possible transitions from each state is small and if the domain Action object's {@link Action#getTransitions(State, String[])}
	 * method is defined.
	 * @param domain the planning domain
	 * @param rf the reward function
	 * @param tf the terminal function
	 * @param gamma the discount factor
	 * @param hashingFactory the state hashing factory for matching generated states with their state nodes. If the domain is continuous, use a {@link NameDependentStateHashFactory}
	 * @param h the height of the tree
	 * @param c the number of transition dynamics samples used. If set to -1, then the full transition dynamics are used.
	 */
	public SparseSampling(Domain domain, RewardFunction rf, TerminalFunction tf, double gamma, StateHashFactory hashingFactory, int h, int c){
		this.plannerInit(domain, rf, tf, gamma, hashingFactory);
		this.h = h;
		this.c = c;
		this.nodesByHeight = new HashMap<SparseSampling.HashedHeightState, SparseSampling.StateNode>();
		this.rootLevelQValues = new HashMap<StateHashTuple, List<QValue>>();
		if(this.c < 0){
			this.computeExactValueFunction = true;
		}
	}
	
	
	/**
	 * Sets the height and number of transition dynamics samples in a way that ensure epsilon optimality.
	 * @param rmax the maximum reward value of the MDP
	 * @param epsilon the epsilon optimality (amount that the estimated value funciton may diverge from the true optimal)
	 * @param numActions the maximum number of actions that could be applied from a state
	 */
	public void setHAndCByMDPError(double rmax, double epsilon, int numActions){
		double lambda = epsilon * (1. - this.gamma) * (1. - this.gamma) / 4.;
		double vmax = rmax / (1. - this.gamma);
		<commit_msg>fixed debug print toggling of SparseSampling<commit_after>package burlap.behavior.singleagent.planning.stochastic.sparsesampling;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;


import burlap.behavior.singleagent.Policy;
import burlap.behavior.singleagent.QValue;
import burlap.behavior.singleagent.ValueFunctionInitialization;
import burlap.behavior.singleagent.options.Option;
import burlap.behavior.singleagent.planning.OOMDPPlanner;
import burlap.behavior.singleagent.planning.QComputablePlanner;
import burlap.behavior.statehashing.NameDependentStateHashFactory;
import burlap.behavior.statehashing.StateHashFactory;
import burlap.behavior.statehashing.StateHashTuple;
import burlap.debugtools.DPrint;
import burlap.oomdp.core.AbstractGroundedAction;
import burlap.oomdp.core.Domain;
import burlap.oomdp.core.State;
import burlap.oomdp.core.TerminalFunction;
import burlap.oomdp.core.TransitionProbability;
import burlap.oomdp.singleagent.Action;
import burlap.oomdp.singleagent.GroundedAction;
import burlap.oomdp.singleagent.RewardFunction;

/**
 * An implementation of the Sparse Sampling (SS) [1] planning algorithm. SS's computational complexity is indepdent of the state space size, which makes it appealing
 * for exponentially large or infinite state space MDPs and it guarantees epsilon optimal planning under certain conditions (use the {@link #setHAndCByMDPError(double, double, int)}
 * method to ensure this, however, the required horizon and C will probably be intractably large). SS must replan for every new state it sees, so an agent following it in general must replan after every step it takes in the real world. Using a
 * Q-based {@link Policy} object, will ensure this behavior because this algorithm will call the planner whenever it's quried for the Q-value for a state it has not seen.
 * <p/>
 * The algorithm operates by building a tree frome the source initial state. The tree is built by sampling C outcome states for each possible state-action pair, thereby generating new
 * state nodes in the tree. The tree is built out to a fixed height H and then in a tail recursive way, the Q-value and state value is estimated using a Bellman update as if the C samples perfectly defined
 * the transition dyanamics. Because the values are are based on fixed horizon and computed in a tail recusive way, only one bellman update is required per node.
 * <p/>
 * Although the complexity of the algorithm is indepdent of the state space size, it is exponential in the height of the tree, so if a large tree height is required
 * to make good value function estimates, this algorithm may not be appropriate. Therefore, when rewards are sparse or uniform except at a distant horizon, this may not be an appropriate
 * algorithm choice.
 * <p/>
 * By default, this classs will remember the estimated Q-value for every state from which the {@link #planFromState(State)} method was called (which will be indirectly called
 * by the Q-value query methods if it does not have the Q-value for it) and it will also remember the value of state tree nodes it computed so that they may be reused in
 * subsequent tree creations, thereby limiting the amount of additional computation required. However, if memory is scarce, the class can be told to forget all prior planning
 * results, except the Q-value estimate for the most recently planned for state, by using the {@link #forgetPreviousPlanResults} method.
 * <p/>
 * By default, the C parameter (number of state transition samples) is fixed for all nodes; however, it may also be set to use a variable C that reduces the number
 * of sampled states the further down in the tree it is according to C_i = C_0 * gamma^(2i), where i is the depth of the node from the root and gamma is the discount
 * factor.
 * <p/>
 * By default, the state value of leafs will be set to 0, but this value can be changed by providing a {@link ValueFunctionInitialization} object via the
 * {@link #setValueForLeafNodes(ValueFunctionInitialization)} method. Using a non-zero heuristic value may reduce the need for a large tree height.
 * <p/>
 * This class will work with {@link Option}s, but including options will necessarily *increase* the computational complexity, so they are not reccommeneded.
 * <p/>
 * This class requires a {@link StateHashFactory}; if the domain is continuous, just use a {@link NameDependentStateHashFactory} instance.
 * <p/>
 * This class can optionally be set to not use sampling and instead use the full Bellman update, which results in the exact finite horizon Q-value being computed.
 * However, this should only be done when the number of possible state transitions is small and when the full model for the domain is defined (that is, the
 * {@link Action#getTransitions(State, String[])} method is defined). To set this class to comptue the exact finite horizon value function, use the
 * {@link #setComputeExactValueFunction(boolean)} method. Note that you cannot use {@link Option}s when using the fully Bellman update, because that would
 * required factored access to the probability of each length of each transition, which is not available from Options (it's aggregated into the transition function
 * itself). An exception will be thrown if {@link Option}s are used with the full Bellman transitions.
 * <p/>
 * 
 * 
 * 1. Kearns, Michael, <NAME>, and <NAME>. "A sparse sampling algorithm for near-optimal planning in large Markov decision processes." 
 * Machine Learning 49.2-3 (2002): 193-208.
 * 
 * 
 * @author <NAME>
 *
 */
public class SparseSampling extends OOMDPPlanner implements QComputablePlanner{

	/**
	 * The height of the tree
	 */
	protected int h;
	
	/**
	 * The number of transition dynamics samples (for the root if depth-variable C is used)
	 */
	protected int c;
	
	/**
	 * Whether the number of transition dyanmic samples should scale with the depth of the node. Default is false.
	 */
	protected boolean useVariableC = false;
	
	/**
	 * Whether previous planning results should be forgetten or reused; default is reused (false).
	 */
	protected boolean forgetPreviousPlanResults = false;
	
	/**
	 * The state value used for leaf nodes; default is zero.
	 */
	protected ValueFunctionInitialization vinit = new ValueFunctionInitialization.ConstantValueFunctionInitialization();
	
	
	/**
	 * This parameter indicates whether the exact finite horizon value function is computed or whether sparse sampling
	 * to estimate should be used. The default is false: to use sparse sampling.
	 */
	protected boolean computeExactValueFunction = false;
	
	
	/**
	 * The tree nodes indexed by state and height.
	 */
	protected Map<HashedHeightState, StateNode> nodesByHeight;
	
	/**
	 * The root state node Q-values that have been estimated by previous planning calls.
	 */
	protected Map<StateHashTuple, List<QValue>> rootLevelQValues;
	
	
	/**
	 * The total number of pseudo-Bellman updates
	 */
	protected int numUpdates = 0;

	
	
	/**
	 * Initializes. Note that you can have h and c set to values that ensure epsilon optimality by using the {@link #setHAndCByMDPError(double, double, int)} method, but in
	 * general this will result in very large values that will be intractable. If you set c = -1, then the full transition dynamics will be used. You should
	 * only use the full transition dynanics if the number of possible transitions from each state is small and if the domain Action object's {@link Action#getTransitions(State, String[])}
	 * method is defined.
	 * @param domain the planning domain
	 * @param rf the reward function
	 * @param tf the terminal function
	 * @param gamma the discount factor
	 * @param hashingFactory the state hashing factory for matching generated states with their state nodes. If the domain is continuous, use a {@link NameDependentStateHashFactory}
	 * @param h the height of the tree
	 * @param c the number of transition dynamics samples used. If set to -1, then the full transition dynamics are used.
	 */
	public SparseSampling(Domain domain, RewardFunction rf, TerminalFunction tf, double gamma, StateHashFactory hashingFactory, int h, int c){
		this.plannerInit(domain, rf, tf, gamma, hashingFactory);
		this.h = h;
		this.c = c;
		this.nodesByHeight = new HashMap<SparseSampling.HashedHeightState, SparseSampling.StateNode>();
		this.rootLevelQValues = new HashMap<StateHashTuple, List<QValue>>();
		if(this.c < 0){
			this.computeExactValueFunction = true;
		}

		this.debugCode = 7369430;
	}
	
	
	/**
	 * Sets the height and number of transition dynamics samples in a way that ensure epsilon optimality.
	 * @param rmax the maximum reward value of the MDP
	 * @param epsilon the epsilon optimality (amount that the estimated value funciton may diverge from the true optimal)
	 * @param numActions the maximum number of actions that could be applied from a state
	 */
	public void setHAndCByMDPError(double rmax, double epsilon, int numActions){
		double lambda = epsilon * (1. - this.gamma) * (1. - this.gamma) / 4.;
		double vmax = rmax / (1. - this.gamma);
		
{'fraction_non_alphanumeric': 0.06653469701968548, 'fraction_numerical': 0.0037391399978005057, 'mean_word_length': 4.382361645457236, 'pattern_counts': {'":': 0, '<': 41, '<?xml version=': 0, '>': 39, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '5835810', 'n_tokens_mistral': 4943, 'n_tokens_neox': 4605, 'n_words': 2343}