Learning Factored Markov Decision Processes with Unawareness
Craig Innes Alex Lascarides

	
	Discovery of a nitrogen-enhanced mildly metal-poor binary system: Possible evidence for pollution from an extinct AGB Star
    
José G. Fernández-Trincado1,2,3,
Ronald Mennickent3,
Mauricio Cabezas4, 
Olga Zamora5,6,
Sarah L. Martell7,8,
Timothy C. Beers9,
Vinicius M. Placco9,
David M. Nataf10,
Szabolcs Mészáros11,12,
Dante Minniti13, 14, 15,
Dominik R. G. Schleicher3,
Baitian Tang16,
Angeles Pérez-Villegas17,
Annie C. Robin2,
Céline Reylé2,
and
Mario Ortigoza-Urdaneta1

    Received ...; Accepted ...
================================================================================================================================================================================================================================================================================================================================================================


		Methods for learning and planning in sequential decision problems often assume the learner is aware of all possible states and actions in advance. This assumption is sometimes untenable. In this paper, we give a method to learn factored markov decision problems from both domain exploration and expert assistance, which guarantees convergence to near-optimal behaviour, even when the agent begins unaware of factors critical to success. Our experiments show our agent learns optimal behaviour on small and large problems, and that conserving information on discovering new possibilities results in faster convergence.
	
	
	

§ INTRODUCTION

	
	
	Factored markov decision processes (s) are a fundamental tool for modelling complex sequential problems. When the transition and reward functions of an  are known in advance, there are tractable methods to learn its optimal policy via dynamic programming <cit.>. When these components are unknown, methods exist to jointly learn a structured model of the transition and reward functions <cit.>. Yet all such methods (with the exception of <cit.>) assume that the way the domain of the problem is conceptualized—the possible actions available to the agent and the belief variables that describe the state space—are completely known in advance of learning. In many scenarios, this assumption does not hold.
	
	For example in medicine, suppose an agent prescribes a particular drug, but later a senior pharmacologist objects to the prescription based on a reason unforeseen by the agent—the patient carries a newly discovered genetic trait, and the drug produces harmful side effects in its carriers. Further, this discovery may occur after the agent has already learned a lot about how other (foreseen) factors impact the drug's effectiveness. As <cit.> point out, such scenarios are common in human discussion—the answer to a person's inquiry may not only provide information about which of the questioner's existing hypotheses are likely, but may also reveal entirely new hypotheses not yet considered. This example also shows that while it may be infeasible for an agent to gather all relevant factors of a problem before learning, it may be easy for an expert to offer contextually relevant corrective advice during learning. Another example is in robotic skill learning. Methods such as <cit.> enable an expert to teach a robot how to perform a new action, but don't teach when it's optimal to use it. In lifelong-learning scenarios, we want to integrate new skills into existing decision tasks without forcing the robot to restart learning each time.
	
	Current models of learning and decision making don't address these issues; they assume the task is to use data to refine a distribution over a fixed hypothesis space. Under this framework, any change to the set of possible hypotheses constitutes an unrelated problem. The above examples, however, illustrate a sort of reverse bayesianism <cit.>, where the hypothesis space itself expands over time.
	
	Instead of overcoming unawareness of states and actions, we could just represent unawareness as an infinite number of hidden states by modelling the problem as an infinite partially observable markov chain decision process (i) <cit.>. This approach has several drawbacks. First, is don't currently address what to do when an unforeseen action is discovered. More importantly, since the hidden variables are not tied to grounded concepts with explicit meaning, it is difficult for an agent to justify its decisions to a user, or to articulate queries about its current understanding of the world so as to solicit help from an expert.
	
	We instead propose a system where an agent makes explicit attempts to overcome its unawareness while constructing an interpretable model of its environment. This paper makes three contributions: First, an algorithm which incrementally learns all components of an . This includes the transition, reward, and value functions, but also the set of actions and belief variables themselves (Section <ref>). Second, an expert-agent communication protocol (Section <ref>)  which interleaves contextual advice with learning, and guarantees our agent converges to near-optimal behaviour, despite beginning unaware of factors critical to success. Third, experiments on small and large sequential decision problems showing our agent successfully learns optimal behaviour in practice (Section <ref>).
	
	

§ THE LEARNING TASK

	
	
	We focus on learning episodic, finite state s with discrete states and actions. We begin with the formalisms for learning optimal behaviour in s where the agent is fully aware of all possible states and actions. We then extend the task to one where the agent starts unaware of relevant variables and actions, and show how the agent overcomes this unawareness with expert aid.
	
	

 §.§ Episodic Markov Decision Processes

	
	An  is a tuple ⟨𝒮, 𝒮_s, 𝒮_e, A, 𝒯, ℛ⟩, where 𝒮 and A are the set of states and actions; 𝒮_s, 𝒮_e⊆𝒮 are possible start and end (terminal) states of an episode;  𝒯 : S × A × S → [0,1] is the markovian transition function P(s' | s, a), and ℛ : S →R is the immediate reward function.[In this paper, we assume the agent's preferences depend only on the current state, and are both deterministic and stationary. Other works allow ℛ to depend on the action and/or resulting state (i.e., ℛ : S × A × S →R).] A policy π : 𝒮× A → [0,1] gives the probability π(s,a) that an agent will take action a in state s. When referring to the local time m in episode n, we denote the current state and reward by s_m,n and r_m,n = ℛ(s_m,n). When referring to the global time t across episodes, we denote them by s_t and r_t. 
	
	The discounted return for episode n is: G^n = ∑_i=0^Tγ^i * r_i,n, where 0 ≤γ≤ 1 is the discount factor governing how strongly the agent prefers immediate rewards. The agent's goal is to learn the optimal policy π_+, which maximizes the expected discounted return in all states. The value function V_π(s) defines the expected return when following a given policy π, while the related action-value function Q_π(s,a) gives the expected return of taking action a in state s, and thereafter following π.
	
	
    V_π(s) = ℛ(s) + γ∑_s' ∈ S P(s' | s, π(s)) V_π(s') 
    
    	Q_π(s,a) = ℛ(s) + γ∑_s' ∈ S P(s' | s, a) V_π(s')

	
	If 𝒯 and ℛ are known, we can compute π_+ via value iteration <cit.>. Further, we can measure the expected loss in discounted return of following policy π versus π_+ using (<ref>), which we refer to as the policy error. If the agent's policy is unknown, we can approximate the policy error using (<ref>):
	
	
	
    𝐸𝑟𝑟(π) = ∑_s_0 ∈𝒮_s P(s_0) (V_π_+(s_0) - V_π(s_0)) 
    𝐸𝑟𝑟(t, t+k) =
    	(∑_s_0 ∈𝒮_s P(s_0) V_π_+(s))
    	- ∑_i=t^t+k G^i/k

	
	If all episodes eventually terminate, then (<ref>) will converge to (<ref>). If our agent is ϵ-greedy (that is, in all states, has probability ϵ > 0 of executing any action from A at random), then termination in most s is guaranteed:
	
	
		A policy π is proper if, from all states s ∈𝒮, acting according to π guarantees one eventually reaches some terminal state s' ∈𝒮_e.
	
		
	
		
		If an  has a proper policy π, then any policy which is ϵ-greedy with respect to A is also proper.
	
	
	

 §.§ Learning FMDPs when Fully Aware

	
	
	If 𝒯 or ℛ are unknown, the agent must learn them using the data D_0:t = [d_0, …, d_t] gathered from domain interactions. At time t, the sequential trial d_t = ⟨ s_t, a_t, s_t+1, r_t+1⟩ gives the current state s_t, action a_t, resulting state s_t+1 and the reward r_t+1 given on entering s_t+1. s allow one to learn 𝒯 for large s by representing states as a joint assignment to a set of variables 𝒳 = { X_1, … , X_n } (Written as 𝒮 = v(𝒳)). Similarly, the reward function is defined as a function ℛ : v(scope(ℛ)) →R, where scope(ℛ) ⊆𝒳 are variables which determine the reward received in each state. To exploit conditional independence, 𝒯 is then represented by a Dynamic Bayesian Network () <cit.> for each action. That is, 𝒯 = { dbn_a_1, … dbn_a_n}, where dbn_a = ⟨^a, θ_a ⟩. Here, ^a is a directed acyclic graph with nodes { X_1, …, X_n,X'_1, … X'_n } where, as is standard, node X_i denotes the value of variable X_i ∈𝒳 at the current time, while X'_i denotes the same variable in the next time step. For each X'_i, ^a_X'_i defines the parents of X'_i. These are the only variables on which the value of X'_i depends. We also make the common assumption that our dbns contain no synchronic arcs <cit.>, meaning ∀ X'_i ∀ a, ^a_X'_i⊆{ X_1, …, X_n }.
	
	This structure, along with the associated parameters θ_a, allow us to write transition probabilities as a product of independent factors: P(s' | s, a) = ∏_X ∈𝒳θ^a_s'[X] , s[^a_X'].
	Here, s[Y⃗] is the projection of s onto the variables in Y⃗, and θ^a_X'=i,^a_X' = j denotes the probability of variable X taking on value i given that the agent performs action a when the variables ^a_X' have assignment j in the current time step.[If the context is clear, we condense this notation to θ^a_i,j.]
	
	Exploiting independence among belief variables doesn't guarantee a compact representation of V_π. We must also exploit the context-specific independencies between assignments by representing 𝒯 and ℛ as decision trees, rather than tables of values.
	
	Figure <ref> shows an example decision tree for ℛ and P(X' | X, Y). The leaves are either rewards, or a distribution over the values of X'. The non-leaves are test nodes, which perform a binary test of the form (X = i?) to check whether variable X ∈𝒳 takes on the value i in the current state. Notice that when X = 1 is true, the distribution over X' is conditionally independent of Y.
	
	
	
	Given trials D_0:t, we can estimate the most likely  structure, tree structure and parameters, then subsequently estimate V_π_+ via a series of steps. Equation (<ref>) is the Bayesian Dirichlet-Equivalent Score <cit.>, which estimates the posterior probability P(^a_X' | D_0:t) that the true parents of X' are ^a_X' by first integrating out all the possible parameters of the local probability distribution.
	
	
    P(^a_X' | D_0:t) ∝ P(^a_X')∫_θ P(D_0:t |θ) P(θ | ^a_X') 
       = P(^a_X')
    	∏_j ∈ v(^a_X')β(N^a_1,j + α^a_1,j, …, N^a_m,j + α^a_m,j)/β(α^a_1,j, …, α^a_m,j)

	
	Here, N^a_X=i,^a_X' = j denotes the number of trials in D_0:t in which action a was taken in a state where the joint assignment to ^a_X' was j, resulting in a state where X has the value i. The α terms are the hyper-parameters from the prior dirichlet distribution over parameters, and act as “pseudo-counts” when data is sparse. The prior P(^a_X') is typically chosen to favour simple structures:
		
	
    P(^a_X') = ρ^|^a_X'| (1 - ρ)^|𝒳| - |^a_X'|

	
	Equation (<ref>) penalizes s with many dependencies by attaching a cost ρ < 0.5 for each parent in ^a_X'. Note, if the space of possible s is too large, we can restrict the parent sets considered reasonable by using common pruning heuristics or, for example, restricting the maximum in-degree.
	
	Given ^a_X', we can then compute each variable's most likely conditional probability tree structure dt^a_X, restricting node tests to members of ^a_X':
	
	
    P(dt^a_X | ^a_X', D_0:t) ∝
    	P(dt^a_X) P(D_0:t | dt^a_X) 
    
    	P(D_0:t | dt^a_X) =
    	∏_ℓ∈ Leaves(dt^a_X)β(N^a_1 | ℓ + α^a_1 | ℓ , … ,N^a_m | ℓ + α^a_m | ℓ)/β(α^a_1 | ℓ, … ,α^a_m | ℓ)

	
	Rather than evaluating the probabilities of all possible dt structures each step, we can incrementally update the most likely dt as new trials arrive using incremental tree induction (), as described in <cit.>. While we lack the space to describe  in detail here, the algorithm broadly works by maintaining a single most-likely tree structure, with counts for all potential test assignments cached at intermediate nodes. As new trials arrive, the counts at relevant nodes become “stale”, as there might now exist an alternative test which could replace the current one, resulting in a higher value for equation (<ref>). If such a superior test exists, the test at this node is replaced, and the tree structure is transposed to reflect this change. We can also use  to learn a tree structure for ℛ based on the trials seen so far. The only difference is that we use an information-gain metric to decide on the best test nodes, rather than (<ref>).
	
	Finally, given dt^a_X, we compute the most likely parameters at each leaf via (<ref>), where N^a_.,j = ∑_i ∈ v(X) N^a_i,j:
	
	
    𝔼(θ^a_X=i,^a_X' = j | D_0:t, dt^a_X) 
    	   = N^a_i,j + α^a_i,j/N^a_. , j + α^a_. , j

	
	Once our agent has a transition and reward tree, we can then use structured value iteration () <cit.>—a variant of value iteration which works with decision trees instead of tables—to compute a compact representation of V_π_+. Algorithm <ref> shows an outline of an incremental version of  (i) <cit.>, which allows the agent to gradually update its beliefs about the optimal value function in response to incoming trials. The algorithm takes the current estimate of the reward and transition functions (ℛ_t and 𝒯_t), along with the previous estimate of the optimal value function (V_t-1), and combines them to produce a new estimate for each state-action function (Q^a_t), and value function (V_t). For further details about the merge and reduce functions used in , consult <cit.>.
	
	
	
	This section took an encapsulated approach to learning 𝒯 (In contrast to a unified one in e.g., <cit.>). This means we separate the task of finding an optimal  structure from the task of learning each local dt structure. Such an approach significantly reduces the space of dts that must be considered, but more importantly, provides us with posterior distributions P(^a_X' | D_0:t) over parent structures. We will use these posterior distributions in section <ref> to conserve information when adapting to new discoveries.
	
	

§ OVERCOMING UNAWARENESS

	
	
	So far, we've assumed our agent was aware of all relevant belief variables in 𝒳, all actions A, and all members of scope(ℛ). We now drop this assumption. From here onward we denote the true set of belief variables, actions, and reward scope as 𝒳^+, A^+ and scope_+(ℛ), and the learner's awareness of them at t as  𝒳^t, A^t, and scope_t(ℛ)
	
	Suppose X^+ = { X_1, X_2, X_3 }, X^0 = { X_1 }, A^+ = { a, a' }, A^t = { a }. We assume the agent can't observe the value of variables it is unaware of. In the medical example from before, if X_3 corresponds to a particular gene, then we assume the agent cannot detect the presence or absence of that gene if it is unaware that it exists. Similarly, we assume the agent cannot perform an action it is unaware of.[This assumption, while reasonable, may always not hold (E.g., an agent may lean on a button while unaware it is part of the task).] As a consequence, at time t=0, the agent does not directly observe the true trial d_0, but rather d_0[𝒳^0] = ⟨ s_0[𝒳^0], a_0, s_1[𝒳^0], r_0 ⟩. The key point here is that awareness of those missing factors may be crucial to successfully learning an optimal policy. For example, the transition between observed states may not obey the markov property unless X_2 is observed, the best action may depend upon whether X_3 is true, or the optimal policy may sometimes involve performing a'. The next sections aims to answer two main questions. First, by what mechanisms can an agent discover and overcome its own unawareness by asking for help? Second, when an agent discovers a new belief variable or action, how can they integrate it into their current model while conserving what they have learned from past experience?
	
	

 §.§ Expert Guidance

	
	Our agent can expand its awareness via advice from an expert. Teacher-apprentice learning is common in the real world, as it allows learners to receive contextually relevant advice which may inform them of new concepts they would not otherwise encounter.
	
	This paper assumes the expert has full knowledge of the true , is cooperative, and infallible. Further, we abstract away the complexity of grounding natural language statements in a formal semantics and instead assume that the agent and expert communicate via a pre-specified formal language (though see e.g., <cit.> for work on this problem). We do not, however, assume the expert knows the agent's current beliefs about the decision problem.
	
	As argued in the introduction, the goal is to provide a minimal set of communicative acts so that interaction between the agent and expert proceeds analogously to human teacher-apprentice interactions. Concretely, this means we want our system to have two properties. First, the expert should, for the most part, allow the agent the opportunity to learn by themselves, interjecting only when the agent is performing sufficiently poorly, or when the agent explicitly asks for advice. Secondly, following the gricean maxims of conversation <cit.>, the expert should provide non-exhaustive answers to queries, giving just enough information to resolve the agent's current query. We want this because in real world tasks with human experts it may be impossible to explain all details of a problem due to the cognitive constraints of the expert or costs associated with communication.
	
	The next sections identify three types of advice whose combination guarantee the agent behaves optimally in the long run, regardless of initial awareness.
	
	

  §.§.§ Better Action Advice

	
	
	If the expert sees the agent perform a sub-optimal action, it can tell the agent a better action it could have taken instead. For example: “When it is raining, take your umbrella instead of your sun hat”. Our goal is to avoid incessantly interrupting the agent each time it makes a mistake, so we specify the following conditions for when the agent is performing sufficiently poorly to warrant correction: Let t be the current (global) time step corresponding to the mth step in the nth episode. Similarly, let t', m', n' be the time the expert last uttered advice. When (<ref>-<ref>) hold, the expert utters advice of the form (<ref>):
	
	
    t - t' > μ
    𝐸𝑟𝑟(𝑛', 𝑛) > β∨ m > κ
    ∃ a' ∈ A^+, Q_π_+(a', s_m, n) > Q_π_+(a_m, n , s_m, n) 
    
    		Q_π_+(w^s_m,n, a') > Q_π_+(w^s_m,n,a_m,n)

	
	Equation (<ref>) ensures some minimum time μ has passed since the expert last gave advice. Equation (<ref>) ensures the expert won't interrupt unless its estimate of the agent's policy error is above some threshold β, or if the agent is unable to reach a terminal state after some reasonable bound κ (which is required because the agent's unawareness of A^+ may mean its current ϵ-greedy policy is not proper). If episode n is unfinished, the expert estimates the expected return via the heuristic G^n ≈∑_i = 0^m - 1γ^i r_i, n + γ^m V_π_+(s_m,n), i.e., we optimistically assume the agent will follow π_+ from now on. Taken together, μ, κ and β describe the expert's tolerance towards the agent's mistakes. Finally, (<ref>) ensures a better action a' actually exists at this time step. 
	
	Equation (<ref>) is the expert's utterance, and the term w^s_m,n in it requires explanation. On first thought, the expert should utter Q_π_+(s_m,n, a') > Q_π_+(s_m,n, a_m,n), explicitly stating the full description of s_m,n. However, remember that the agent's awareness, 𝒳^t, may be a tiny subset of 𝒳^+. Uttering such advice may involve enumerating a huge number of variables the agent is currently unaware of. This is exactly the type of exhaustive explanation we wish to avoid, since such an explanation may place a cognitive burden on the expert, or confuse a learner. Conversely, we could instead have our expert project its intended utterance onto only those variables 𝒳^e for which the expert has explicit evidence the agent is aware of them (i.e., utter: Q_π_+(s_m,n[𝒳^e], a') > Q_π_+(s_m,n[𝒳^e], a_m,n)). This can be understood by the agent without being made aware of any new variables, but might violate our assumption that the expert is truthful. For example, if ∃ s', s'[𝒳^e] = s_m,n[𝒳^e], but Q_π_+(s', a) > Q_π_+(s', a').
	
	The solution is to use a sense ambiguous term w^s, whose intended denotation is the true state s (i.e w_s ∈ v(𝒳^+)), but whose default interpretation by the agent is s[𝒳^t]. In words, it is as if the expert says “In the last step, it would have been better to do a' than a_m,n”.
	
	Thus, by introducing ambiguity, the agent can interpret the advice in two ways. The first is as a partial description of the true problem, which is monotonically true regardless of what it learns in future. On hearing (<ref>), the agent adds (<ref>-<ref>) to its knowledge:
	
	
    a' ∈ A^+ 
    ∃ s, s[𝒳^t] = s_m,n[𝒳^t] ∧ Q_π_+(s, a') > Q_π_+(s, a_m,n)

		
	Additionally however, the agent can choose to add its current default interpretation of the advice to its accumulated knowledge:
	
	
    Q_π_+(s[𝒳^t], a') > Q_π_+(s[𝒳^t], a)

	
	The agent can then act on the expert's advice directly by choosing a' whenever s[𝒳^t] = s_m,n[𝒳^t], regardless of what seems likely from D_0:t. We can see that even with a cooperative and infallible expert, even abstracting away issues of grounding natural language, misunderstandings can still happen due to differences in agent and expert awareness. As the next section shows, such misunderstandings can reveal gaps in the agent's awareness and help to articulate queries whose answers guarantee the agent expands its awareness.
	
	Lemma <ref> guarantees the expert's advice strategy reveals unforeseen actions to the agent so long as its performance in trials exceeds the expert's tolerance.[Proofs of  lemmas/theorems are in the technical supplement]
	
	
		
		Consider an  where π_+ is proper, an agent with awareness 𝒳^t ⊆𝒳^+, A^t ⊂ A^+, and expert acting with respect to (<ref>-<ref>). If ∃ a ∈ image(π_+), a ∉ A^t then as k →∞, either Err(t, t + k) → c with c ≤β or the expert utters (<ref>) such that a' ∉ A^t.
	
	
	

  §.§.§ Resolving Misunderstandings

	
	
	We noted before that the agent's defeasible interpretation of expert advice could result in misunderstandings. To illustrate, suppose the agent receives advice (<ref>) and (<ref>) at times t -k and t:
	
	
    Q_π_+(w^s_t-k, a) > Q_π_+(w^s_t-k, a') 
    
    	Q_π_+(w^s_t, a) < Q_π_+(w^s_t, a')

	
	While the intended meaning of each statement is true, the agent's default interpretations of w^s_t-k and w^s_t may be identical. That is, s_t-k[𝒳^t] = s_t[𝒳^t]. From the agent's perspective, (<ref>) and (<ref>) conflict, and thus give the agent a clue that its current awareness of 𝒳^+ is deficient. To resolve this conflict, the agent asks (<ref>) (in words, “which X has distinct values in s_t-k and s_t?”) and receives an answer of the form (<ref>):
		
	
    ?λ X(X∈𝒳^+ ∧ s_t - k[X] ≠ s_t[X]) 
    
    	X ∈𝒳^+

	
	Notice there may be multiple variables in 𝒳^+ ∖𝒳^t whose assignments differ in s_t-k and s_t. Thus, the expert's answer can be non-exhaustive, providing the minimum amount of information to resolve the agent's conflict without necessarily explaining all components of the task. This means the agent must abandon its previous defeasible interpretation of (<ref>), but can keep (<ref>-<ref>), as these are true regardless of known variables. Lemma <ref> guarantees the expert will reveal new belief variables, provided such misunderstandings can still arise.
	
	
		
		Consider an  where π_+ is proper and an agent with awareness 𝒳^t ⊂𝒳^+, image(π_+) ⊆ A^t ⊆ A^+. If ∃ s ∃ s' ≠ s, s[𝒳^t] = s'[𝒳^t], and π_+(s) ≠π_+(s'), then as k →∞, either Err(t, t + k) → c (c ≤β), or the expert utters (<ref>) such that X ∉𝒳^t
	
		
	

  §.§.§ Unexpected Rewards

	
	
	In typical s (where the agent is assumed fully aware of 𝒳^+, A^+, and scope_+(ℛ)), we tend only to think of the trials as providing counts, but for an unaware agent, a trial d_t = ⟨ s_t, a_t, s_t+1, r_t+1⟩ also encodes monotonic information:
	
	
    ∃ s, s[𝒳^t] = s_t+1∧ℛ_+(s) = r_t+1

	
	This constrains the form of ℛ the agent must learn. Recall that scope_t(ℛ), may be only a subset scope_+(ℛ), so it might be impossible to construct an ℛ : v(scope_t(ℛ)) →R satisfying all descriptions (<ref>) gathered so far. Further, those extra variables in scope_+(ℛ) ∖ scope_t(ℛ) may not be in 𝒳^t. To resolve this, if the agent fails to construct a valid reward function, it asks (<ref>) (in words, “which variable X (that I don't already know) is in scope(ℛ)?”), receiving an answer (<ref>):
	
	
    ?λ X(X∈𝑠𝑐𝑜𝑝𝑒_+(ℛ) ⋀_X'∈ scope_t(ℛ)
    	X≠ X') 
    
    		X ∈ scope_+(ℛ) ∧ X ∈𝒳^+

		
	Again, the agent may be unaware of many variables in scope_+(ℛ), so (<ref>) may be non exhaustive. Even so, we can guarantee that the agent's learned reward function eventually equals ℛ_+:
	
	
		
		Consider an  where π_+ is proper and an agent with awareness A^t ⊆ A^+, 𝒳^t ⊆𝒳^+, scope_t(ℛ) ⊆ scope_+(ℛ). As k →∞, there exists a K such that for all k ≥ K, ℛ_t+k(s) = ℛ_+(s) for all states s reachable using A^t.
	
	
	

 §.§ Adapting the Transition Function

	
	
	Section <ref> showed three ways the agent could expand its awareness of 𝒳, A, and scope(ℛ). If we wish to improve on the naive approach of restarting learning when faced with such expansions, we must now specify how the agent adapts 𝒯 and ℛ to such discoveries.
	
	Adapting 𝒯 upon discovering a new action a'  at time t is simple: Since the agent hasn't performed a' in any previous trial, it can just create a new , dbn_a', using the priors outlined in section <ref>. Our new model at time t then becomes 𝒯 = { dbn^t_a_1, … dbn^t_a_n}∪{dbn_a'}.
	
	The more difficult issue is adapting 𝒯 upon discovering a new belief variable Z. The main problem is that the agent's current distributions over s no longer cover all possible parent sets for each variable, nor all dts. For example, the current distribution over ^a_X' does not include the possibility that Z is a parent of X'. Worse, since we assume in general that the agent cannot observe Z's past values in D_0:t, it cannot observe the true value of N^a_Z  = i| j, nor N^a_X = i | ^a_X' = j when Z ∈^a_X'. The α-parameters involving Z are also undefined, yet we need them to calculate structure probabilities (<ref>, <ref>) and parameters via (<ref>).
	
	The problem is that new variables make the size of each (observed) state dynamic, in contrast to standard problems where they are static (e.g., ⟨ X_1 = 0, X_2 = 1 ⟩ becomes ⟨ X_1 = 0, X_2 = 1, Z = ?⟩ ) . We could phrase this as a missing data problem: Z was hidden in the past but visible in future states, so treat the problem as a  and estimate missing values via e.g., expectation maximization <cit.>. However, such methods commit us to costly passes over the full state-action history, and make it hard to learn dt structures with enough sparseness to ensure a compact value function. Alternatively, we could ignore states with missing information when counts involving Z are required. For example, we could use P(^a_X' | D_t:n) to score ^a_X' when Z ∈^a_X' but use P(^a_X' | D_0:n) when Z ∉^a_X'. However, as <cit.> points out, most structure scores, including (<ref>), assume we evaluate models with respect to the same data. If two models are compared using different data sets (even if they come from the same underlying distribution), the learner tends to favour the model evaluated with the smaller amount of data. Instead, our method discards the data gathered during the learner's previous deficient view of the hypothesis space, but conserves the relative  posterior probabilities learned from past data to construct new priors for the ^a, dt^a and θ^a in the expanded belief space.
	
	

  §.§.§ Parent Set Priors

	
	On discovering Z, the agent must update P(^a_X') for each X ≠ Z and a ∈ A^t to include parent sets containing Z. In (<ref>) we construct a new prior P'(^a_X') using the old posterior:
	
	
    P'(^a_X') =
    	
    	(1 - ρ) P(^a_X' | D_0:t)    if  Z ∉^a_X'
    ρ P((^a_X'∖ Z) | D_0:t)    otherwise

	
	This preserves the likelihoods among the parent sets that do not include Z. It also maintains our bias towards simpler structures by re-assigning only a portion ρ of the probability mass to parent sets including Z. To define P(^a_Z')—the distribution over parent sets for the newly discovered variable Z—we default to (<ref>), since the agent has no evidence (yet) concerning Z's parents.
	
	

  §.§.§ Decision Tree and Parameter Priors

	
	We must also update P(dt^a_X | ^a_X'), and P(θ^a_X, ^a_X' | ^a_X') to accommodate Z. Here, we return to the issue of the counts N^a_i | j and the associated α-parameters. As mentioned earlier, we wish to avoid the complexity of estimating Z's past values. Instead, we throw away the past counts of N^a_i | j, but retain the relative likelihoods they gave rise to by packing these into new α-parameters, as shown in (<ref>-<ref>):
	
	
    α^a_X = i | Y = j := 
    	K/|v(Z ∪ Y)|    if  X = Z 
    K/|v(Y)| P(i, j[Y ∖ Z] | dbn^t_a)     else
    
    	P'(dt^a_X' | ^a_X') ∝∏_ℓ∈ leaves(dt^a_X')β(α^a_X' = 1 | ℓ, … , α^a_X'=n | ℓ)

	
	Equation (<ref>) summarizes D_0:t via inferences on the old best , then encodes these inferences in the new α-parameters. The revised α-parameters ensure the new tree structure prior and expected parameters defined via (<ref>) and (<ref>) bias towards models the agent previously thought were likely. Indeed, the larger the (user-specified) K parameter is, the more the distributions learned before discovering Z influence the agent's reasoning after discovering Z.	
	
	

 §.§ Adapting Reward and Value Trees

	
	
	On becoming aware Z is part of scope_+(ℛ), the agent may wish to restructure its reward tree. This is because awareness that Z ∈ scope_+(ℛ) means there are tests of the form Z=i that the agent has not yet tried which may produce a more compact tree. In the language of , the current test nodes are “stale”, and must be re-checked to see if a replacement test would yield a tree with better information gain. If the agent was unaware of Z (i.e, Z ∉𝒳^t), we can still test on assignments to Z by following the  convention that any state where Z is missing automatically fails any test on Z.
	
	Once we have updated 𝒯 and ℛ, there is no need to make further changes to  V_t in response to a new action a' or variable Z. In effect, this encodes our conservative intuition that the true V_π_+ is more likely to be closer to the agent's current estimate V_t than some arbitrary value function. The agent essentially assumes (in absence of further information) that the value of a state is indifferent to this newly discovered factor. In subsequent trials where the agent performs a' or observes Z, algorithm <ref> ensures information about this new factor is incorporated into the agent's value function.

	
	
	Algorithm <ref> outlines how the agent updates 𝒯, ℛ, and V in response to new data and expert advice. Given algorithm <ref>, theorem <ref> guarantees our agent behaves indistinguishably from a near-optimal policy in the long run, regardless of initial awareness (provided all X ∈𝒳^+ are relevant to expressing the optimal policy).
	
	
		
		Consider an  where π_+ is proper and an agent with initial awareness 𝒳^0 ⊆𝒳^+, A^0 ⊆ A^+, and scope_0(ℛ) ⊆ scope_+(ℛ) acts according to algorithm <ref>. If for all X ∈𝒳^+, there exists a pair of states s, s' such that s[𝒳^+ ∖ X] = s'[𝒳^+ ∖ X], s[X] ≠ s'[X], and π_+(s) ≠π_+(s'), then as t →∞, Err(0, t) → c such that c ≤β
	
	

§ EXPERIMENTS AND RESULTS

	
	
	Our experiments show that agents following algorithm <ref> converge to near-optimal behaviour in both theory and practice. Further, we show that conserving information on 𝒯 and V gathered before each new discovery allows our agent learn faster than one which abandons this information. We do not investigate assigning an explicit budget to agent-expert communication, leaving this to future work. However we do show how varying the expert's tolerance affects the agent's performance.
		
	We test agents on two well-known problems: Coffee-Robot and Factory.[Full specifications at <https://cs.uwaterloo.ca/ jhoey/research/spudd/index.php>] In each, our agent begins with only partial awareness of 𝒳^+, A^+ and scope_+(ℛ). The agent takes actions for T time steps, using an ϵ-greedy policy (ϵ = 0.1). When the agent enters a terminal state, we reset it to one of the initial states randomly. We use the cumulative reward across all trials as our evaluation metric, which acts as a proxy for the quality of the agent's policy over time. To make the results more readable, we apply a discount of 0.99 at each step, resulting in the metric R^disc_t = r_t + 0.99 * R^disc_t-1.
	
	We test several variants of our agent to show the effectiveness of our approach. The default agent follows algorithm <ref> as is, with parameters ρ = 0.1, K = 5.0, μ=10, β=0.1, κ = 50 in equations (<ref>), (<ref>), (<ref>), and (<ref>-<ref>) respectively. The nonConservative agent does not conserve information about V, nor 𝒯 via (<ref>-<ref>) when a new factor is discovered. Instead, it resets V and 𝒯 to their initial values. This agent is included to show the value of conserving past information as 𝒳 and A expand. The truePolicy and random agents start with full knowledge of the true , and execute an ϵ-greedy version of π_+, or a choose random action respectively. These agents provide an upper/lower bound on performance. The lowTolerance / highTolerance agents change the expert's tolerance to β=0.01 and β=0.5.
	
	

 §.§ Coffee Robot

	
	
	Coffee-Robot is a small sequential problem where a robot must purchase coffee from a cafe, then return it to their owner. Also, the robot gets wet if it has no umbrella when it rains. The problem has 6 boolean variables—huc (user has coffee), hrc (robot has coffee), r (raining), w (wet), l (location), u (umbrella)— and 4 actions—move, delc, buyc and getu— making 256 state/action pairs. The terminal states are those where huc=1; initial states are all non-terminal ones. Our agent has initial awareness A^0 = {move}, 𝒳^0= scope_0(ℛ) = {huc} and discount factor γ = 0.8.[Original setting was γ=0.9. Changed to make π_+ proper.]
	
	
	
	Figure <ref> shows each agent's (discounted) cumulative reward. Despite starting unaware of factors critical to success, the default agent quickly discovers the relevant actions and beliefs with the expert's aid, and converges on the optimal policy. The non-conservative agent also learns the optimal policy, but takes longer. This shows the value of conserving 𝒯 and V on discovering new beliefs. We also see how expert tolerance affects performance. The agent paired with high tolerance expert learns a (marginally) worse final policy, but this makes little difference to cumulative reward. Figure <ref> shows why: The agent learned a “good enough” policy, so the expert doesn't reveal the “get umbrella” (getu) action, which yields only a minor increase in reward. Figure <ref> supports this explanation, showing how more tolerant experts reveals less variables over time.
	
	
	
	
	

	

 §.§ Factory

	
	
	Factory is a larger problem (|A^+| = 14, 𝒳^+ = 14, 774144 state/action pairs), which shows our method works on more realistically sized tasks. Here, an agent must shape, paint and connect two widgets to create products of varying quality. Some actions (like bolting) produce high quality products, whereas others (like gluing) produce low quality products. The agent receives a higher reward for producing goods which match the demanded quality.[Rewards were scaled to range 0.0-1.0 and, to make π_+ proper, terminal states which previously gave 0 reward were given a small reward of 0.01.]. The terminal states are those where connected=1; initial states are non-terminals where it is possible to connect two components. Our agent's initial awareness is 𝒳^0 = scope_0(ℛ) = {connected}, A^0 = {bolt, glue, drilla, drillb}, with γ=0.9. This represents a simplified task where the agent thinks the only goal is connecting the widgets.
	
	Figure <ref> shows results similar to previous experiments. The default agent converges on optimal behaviour, and does so quicker than the non-conservative agent. Varying the expert's tolerance now has a larger effect on the rate at which factors are discovered and on convergence towards the optimal policy (presumably because there are many more unforeseen variables/actions the agent can discover in this larger problem).
	
	

§ RELATED WORK

	
	
	Models of unawareness exist in logic and game theory <cit.>, but interpret (un)-awareness from an omniscient view. We instead model awareness from the agent's view and offer methods to overcome one's own unawareness.
	
	<cit.> defines unawareness similarly to us, using markov decision processes with unawareness (mdpus) to learn optimal behaviour when an agent starts unaware of some actions. They apply mdpus to a robotic-motion problem with around 1000 discretised atomic states. The agent uses an explore move, which randomly reveals useful motions they were previously unaware of. Our work differs from theirs in several ways. First, we provide a concrete mechanism for discovering unforeseen factors via expert advice, rather than random discovery from the agent's own exploration. Second, we allow the agent to discover explicit belief variables rather than atomic states, and focus more on exploiting the inherent structure in problems with a large number of features. This enables us to scale up to complex decision problems, where the agent converges on an optimal policies in a (true) state space around a million atomic states, as opposed to around 1000. <cit.> also learn an increasingly complex representation of the state space by gradually distinguishing between states which yield different rewards. Rather than dealing with unawareness, their approach focusses on refining an existing state space. In other words, they do not support introducing unforeseen states or actions that the learner was unaware of before learning.
	
	Several works use expert interventions to improve performance via reward shaping and corrections <cit.>. Yet all such methods assume the expert's intended meaning can be understood without expanding the agent's current state and action space. Our work allows experts to utter advice where ambiguity arises from their greater awareness of the problem.
		
	

§ CONCLUSION

	
	
	We have presented an agent-expert framework for learning optimal behaviour in both small and large s even when one starts unaware of factors critical to success. Further, we've shown that conserving one's beliefs helps improve the effectiveness of learning. In future work, we aim to lift some assumptions imposed on the expert, and expand the expressiveness of its advice. For instance, we could let the expert be fallible, or allow questions on the structure of 𝒯, as <cit.> do for Bayesian Networks.
	
	
	
