This paper deals with user's preferences (wishes). Common users are uneducated in the decision-making (DM) theory and present their preferences incompletely. That is why we elicit them from such a user during the DM. The paper works with the DM theory called fully probabilistic design (FPD). FPD models closed DM loop, made by the user and the system, by the joint probability density (pd, real pd). A joint ideal pd quantifies the user's preferences. It assigns high probability values to preferred closed-loop behaviors and low values to undesired behaviors. The real pd should be kept near the ideal pd. By minimizing the Kullback-Leibler divergence of the real and ideal pds, the optimal decision policy is found. The presented algorithmic quantification of preferences provides ambitious but potentially reachable DM aims. It suppresses demands on tuning preference-expressing parameters. The considered ideal pd assigns high probabilities to desired (ideal) sets of states and actions. The parameters of the ideal pd (tuned during the DM via the user's feedback) are: ▶ relative significance of respective probabilities; ▶ a parameter balancing exploration with exploitation. Their systematic tuning solves meta-DM level task, which observes the agent's satisfaction expressed humanly by “school-marks”. It opts free parameters to reach the best marks. A formalization and solution of this meta-task were recently done, but experience with it is limited. This paper recalls the theory and provides representative samples of extensive up to now missing simulations.
Decision making (DM) is the everyday activity of every human. It is important to make the right decisions to achieve the goal. DM is described by a closed-loop formed by an agent (the person, who makes decisions) and an environment. The environment of the agent is usually called a system and its dynamics is unknown. It is described by transition probability density (pd) between its states conditioned by the agent’s actions. The agent observes the state of the system and makes an action to meet their wishes, ideally, to move the system to the desired state. The actions are chosen via the agent’s policy . It consists of decision rules r, which determine what action should be chosen in each time epoch depending on the system’s state and the model of the system. The model m expresses the agent’s beliefs about the dynamics of the real system.
The main task of DM is to select the optimal policy. This paper uses a fully probabilistic design (FPD), which introduces an ideal probability density
c() = ∏︁ m(|, − 1)r(|− 1), which expresses the desired pd of behavior ≡ (0, 1, 1, 2, 2, . . . , , ) ∈ B. It sets high probability values to preferred behaviors and low probability values to unwanted behaviors. It consists of an ideal model m of the system and of an ideal decision rule r. The real pd c () depends on the model m of the system and decision rules r forming the policy . c () = ∏︁ m(|, − 1)r(|− 1).
∈T ∈T This paper exploits Bayes’ learning to get m relating (the observed state, the used action, the next state). The optimal policy in a set Π minimizes the Kullback-Leibler divergence (KLD) of the pd c to the ideal pd c
∈Π ∈ Arg min D(c ||) = Arg min
∫︁ ∈Π ∈B c () ln ︂( c () )︂ c() d.
Theorem 1. (FPD, [22]) Decision rules, which constitute the optimal decision policy , are computed for = , − 1, . . . , 1 and with h( ) ≡ 1 as follows r(|− 1) ≡ r(|− 1) exp[− d(, − 1)] ,
h(− 1) ∫︁
∈S ∫︁
∈A d(, − 1) ≡ m(|, − 1) ln ︂[
m(|, − 1) h()m(|, − 1) ︂] d h(− 1) ≡
r(|− 1) exp[− d(, − 1)] d ∈ h() ∈ [0, 1].
The attained minimum is min D(c ||c) = − ln(h(0)).
∈Π We focus on the preference quantification, on finding the c. The preference specification is mostly incomplete due to the agent’s imperfections. This means that
C ≡ { ideal pds c(), ∈ B, respecting the agent’s wishes}
includes several pds. It can be also empty because of the agent’s inconsistencies. The agent’s
preferences can be in contradiction or the agent can have un-achievable goals. The preference
elicitation (PE) consists of the choice of: ▶ the non-empty set C that overcomes the agent’s
inconsistencies ▶ the optimal ideal pd c from the set (
min D(c ||c).
c∈C ∈Π
Its use in FPD ensures that no preferences are added to the agent’s. Theorem 1 describes the 1 minimization over . The 2 minimization over c is harder and it can be done over individual factors of c for each already observed state.
Then, cf. (
d(), ∈ S, ∈ A, i.e.
Theorem 2. (Optimal m-factor, [19]) Let r
∈ R be a fixed ideal decision rule, which defines a non-empty cross-section M ≡ { m : mr
∈ set (6)}. Let m(|) ∈
d() < ∞, ∀ ∈ A (
The decision rules work on the set of admissible actions. Thus, the support of an admissible r-factor must be included in the set of possible actions i.e. supp[r] ⊂ FPD-optimal r-factor, Theorem 1, implies that supp[r] ⊆ supp[r]. Therefore, only the ideal A. The form of the r ∈ R ≡ {︀ r : supp[r] = A}︀ (4) (5) (7) (8) a scalar > 1
{︃ R ≡ r
∝ A() exp[− d()], ≡ − 1 ∫︁
S
Remarks ▶ The generic constraint (8) implies that the ideal r-factors support exploration, which makes the Bayesian learning efficient.
▶ The parameter controls exploration. Every action from the set of possible actions can be tried with almost the same probability if the parameter is close to 0. If gets bigger the exploration declines, cf. form of r in (10).
M making C ̸= ∅ The optimal ideal r-factor is uniquely given by the choice of m (and by the opted ) via (10). The description of the agent’s preferences only guarantees a non-empty set M. A wide range of practical cases can be covered with a few additional PE-oriented queries. Our specific elaborated case concerns the next agent’s general wish.
The agent wants to reach given sets of ideal states S and ideal actions A,
∅ ̸= S ⊂ S, ∅ ≠ A ⊆ A.
This is quantified as the wish to assign the highest probability to the set of ideal states S and to the set of ideal actions A (11) by closing the loop of the given model m and of the optimal ideal decision rule r. So we choose as the maximized functional ∫︁
A ()r() d ≡ (1 − ) S ()m(|) d + A () r() d.
︂] keep actions ∈ A and exclude none. Thus, (8) is the generic constraint and
R ≡ { r : mr ∈ (6) while m is given by (7)}.
Theorem 3. (Optimal r-factor meeting (8), [19]) Let assumptions of Theorem 2 hold and for r : supp[r] = A, ||r|| ≡ ︂[ ∫︁ (r())d ︂] 1/
}︃ < ∞ , |A| ≡ ∫︁
A d < ∞.
(9) set of ideal actions A relative to being in the set of ideal states S.
The introduced weight ∈ W ≡ [0, 1] parameterizes how much the agent prefers to stay in the The inspected problem has a meaningful solution if () = (1 − ) S ()m(|) d + A () > 0, on A.
∫︁ [︂
A ∫︁
S ∫︁
S
A ︂) , A() is the indicator function of A (10) (11) (12) (13)
If the functional (12) is large, then the probabilities of the preferred sets are large. The part (1− ) ∫︀S S ()m(|) d forces the highest probability to the set S. And the part A ()r() should guarantee that the ideal decision rule will often choose the actions from the set A. The weight balances these probabilities.
Remarks ▶ The weight is fixed. Its fine-tuning is controlled by additional queries. ▶ The function determining () qualitatively plays the role of the reward. ▶ Our construction of the optimal ideal pd c quantifies the agent’s preferences in an ambitious but realistic way. ▶ Maximization of (12) with r given by (10) rely on: Theorem 4. (Optimal value of d, [19]) Under assumptions of Theorem 3, covering those of Theorem 2, and under (13), the optimal ideal model m fulfilling (12) determines d(), giving r = r(m) (10), ∈ A, as the function solvability of (14) ∀ ∈ {} is Theorem 5. (Solvability of (14), [19]) Under (13) and |A| < ∞, the smallest d(¯) exists such that (14) has a solution m(|), ∈ S, ∀ ∈ A. Thus, the smallest d(¯) guaranteeing d(¯) = max 0, max ︂[
∫︁ ∈A S m(|) ln ︂[
() ]︂ (¯)h() pds m(|). It requires to find
m giving d (14) on A.
uniform on S and Theorem (
m(|) exp(− e()m(|)) ∫︀S m(|) exp(− e()m(|)) d ∫︁
S , while |S| ≡ d < ∞.
(16)
The real valued e() in (16) is the existing solution of L(e()) = R(). For d(¯) meeting (15) with ¯ ∈ Arg max∈A (), the left- and right-hand sides of this equation are e()Λ() + ln m(|) exp[− e()m(|)] d , Λ() ≡ m2(|) d L(e()) ≡
R() ≡ − ∫︁
S
In the considered case with the discrete-valued states and actions, the found solution can be directly converted into a compact algorithm. It is done in [19]. Here, we just stress that it uses ︂( (¯) )︂ () ︂) ∫︁
S ∈A d + d(¯) + ln , ¯ ∈ Arg max ().
(17) the Bayesian estimation of unknown but time-invariant values of the transition probabilities Θ. The gained parametric model m(|, − 1, Θ) belongs to the exponential family [1] and makes Dirichlet’s prior pd self-reproducing. Its degrees of freedom counting the observed transitions − 1 = ˜ ∈ S, = ∈ A to = ∈ S form the sufcfiient statistic for learning unknown Θ|,˜ ≡ m(|, ˜, Θ) [3].
The agent specifies the preferred states S and preferred actions A before the beginning DM. A problem arises as the agent1 wishes concern two usually contradiction things. In this case, we need to choose the weight in (12), which determines how much the user prefers to stay in the set A relative to being in S. But they are unable to express how much they prefer it before they will observe how the closed loop behaves. That is why we added a dialogue with the user during the DM. The user will express their preferences and next they will control the results of the DM during the DM. The DM solved in Section 3, referred to as the basic DM, deals with two types of inputs: ✓ those directly describing the basic DM, which include: ▶ the state S and action A sets; ▶ the wishes-expressing ideal sets S ⊂ S and A ⊆ A; ✓ more technical, policy-influencing, inputs that include: ▶ the weight ∈ [0, 1] balancing the relative importance of ideal sets, see (12); ▶ the scalar > 0, see (10), balancing exploration with exploitation (duality, [10, 20]).
Fine variations of ideal sets S, A or the design horizon | | are potential inputs of the preference processing but they are here fixed. Thus, the paper focuses just on the pair , . Its optimal choice depends on: ▶ subjective user’s preferences; ▶ the user’s attitude to the basic DM; ▶ emotions, etc., i.e. on the user’s mental state. The dependence is complex and the mental state can hardly be directly measured and quantified. Two users can have the same preferences expressed by the sets S, A, but their responses differ.
In our solution, the user is asked to judge the DM quality reached for various choices of , . This is the domain of classical PE [8] that often elicits preferences about a static DM and interactively queries the user. Even advanced versions, represented by [4, 5, 7], become cumbersome in the targeted basic dynamic DM. This makes us adopt the next user-driven way that consists of solving an appropriate FPD meta-task, whose description uses capital versions of all functions and parameters entering it, cf. [11].
The user assigns (satisfaction) marks. Their changes during the dialog serve as the (meta-)state ∈ S¯, to the behaviour caused by the policy, designed for trial values of the optional inputs here, (, ). Their changes are the (meta-)actions. They are generated by (meta-)policy gained by the same algorithm as that used at the basic level2. It runs more slowly than the basic DM, ∈ {¯ , 2¯ , . . . , } ⊂ T given by ¯ > 1.
This simple idea has to cope with the possible infinite regress, i.e. DM at meta-level needs meta-inputs opted via a meta-PE, etc. Also, the curse of dimensionality [2] endangers applicability as the opted inputs are multiple and continuous-valued. Our way counteracts both obstacles. We 1The agent will be called user as it is usual for preference elicitation. 2In harmony with the quest for a universal DM. decided to ask queries after every time epoch ¯ > 1, but the queries can be answered irregularly after some multiples of the ¯ . The use of zero-order holder copes with the expected irregularity of user’s responses. It makes realistic the time-invariance of the model M( | , − ¯ , Θ) := Θ | , − ¯ needed for learning this meta-model, cf. the beginning of Sec. 3.
The set of possible meta-states is S¯ := {− 1, 0, 1}. It is implied by a difference of the current mark and previous mark3 i.e. Δ = − − 1. If Δ < 0 =⇒ S¯ = {− 1}, if Δ = 0 =⇒ S¯ = {0} and if Δ > 0 =⇒ S¯ = { } 1 .
The choice of the ordinal scale of marks ∈ G¯ ≡ { 1, . . . , |G¯ | ≡ 5} sufcfies for expressing “satisfaction degree”. A rich, cross-domain, experience, e.g. in marketing [6] or in European Credit and Accumulation System, confirms this. The mark = 1 is taken as the best one. The ideal set of meta-states is then S¯ ≡ {− 1}.
By construction, the outcomes of the basic DM depend smoothly on the discussed inputs. Thus, changes ≡ (Δ, Δ ) of inputs (, ) can be selected in a finite set A¯ := {(Δ, Δ )} of discrete values. The natural flexible options are Δ ∈ {− ¯, 0, ¯}, Δ ∈ {− ¯, 0, ¯}, ¯, ¯ > 0. (18) The meta-policy is to guarantee that its actions stay within their allowed ranges ( ∈ [0, 1], > 0). The used simple clipping at boundaries of (18) seems to suffice. We have no other demands on the actions. Thus, A¯ = A¯ and = 0 (meta-twin to in (12)).
The last input to the meta-DM is the parameter of exploration . It makes no sense to choose a different value at the meta-level: the meta-action is its common value.
The appearance of ¯ , ¯, ¯ still preserves the danger of infinite regress. At present, it is cut by force and they are chosen heuristically. They, however, offer, the first step in a conceptual solution that: ▶ lets appear only meta-inputs that have a weak influence on results; ▶ tunes them via an adaptive minimization of miss-modelling error [17].
This core section presents experiments. We have chosen a DM example with a heating system.
Common simulation options The simulated system is Markov with |S| = 15 and |A| = 7. It is created by learning the transition pd p(|, − 1) on the simulated system generating 106 real values stimulated by independently generated discrete actions in A := {1, . . . , 7}. The states ∈ S := {1, . . . , 15} are gained via an affine mapping of discretized values of the real-valued generated by the equation (0 = 1)
= 0.028− 1 + 1.81− 2 − 0.817− 3 + 0.1 − 0.16− 1 + 0.05.
There, is the white, zero-mean, normal noise with a unit variance. In all experiments with the Markov chain, the number of simulated epoch was 800. The seed of the random generator was ifxed, and the initial state 0 = 1. The initial guess of the entries of the array e (17) was 1.2. The horizon for dynamic programming is ℎ = 2, which suffices when taking the outcome from the previous epoch as the initial guess of the stationary value function. 3We decided to note marks with a symbol as grade, as for mark is already used.
Experiments We present DM results without and with the user’s control. DM without the user’s control, it is the basic DM with no meta-level and preferences expressed by the ideal sets S, A and by fixed options , . DM with the user’s control solves the basic DM supported by the second-layer implementing the solution of the meta-DM task with the dialogue with the user. The DM with the user’s control gives the user the chance to express their satisfaction every ten steps, ¯ = 10. The satisfaction is quite subjective. It is demonstrated by presenting selected results for different users. We also present results with different fixed parameters , to show how these parameters influence DM. In experiments with the user’s control, these parameters are free and they are changed by the responses of the user. The changes of the free parameters , are ¯ = 0.1 and ¯ = 0.3 (18). To compare the results impartially we use prices paid for deviation from the preferred behavior. The agreed prices are in Table 1 (common to all experiments) and Table 2 that suits to the preferred state S = {8}. Other preferred states are priced similarly.
Experiment 1. It shows the results for the preferred state S = {6} and then for S = {8}. No action is preferred, A = A. The free parameters are fixed, = 0, = 1.
(a) States for S = {6}
(b) Actions for S = {6} (c) States for S = {8} (d) Actions for S = {8}
Discussion In the Fig. 1, we can see that the frequency of the preferred state S = {8} is pretty high. It occurs the most often. On the other hand the preferred state S = {6} does not occur the most often and its frequency is low. It is hard for the system to get the state S = { } 6 . We will try to change the free parameters to improve results.
Experiment 2. It shows the results for S = {8} and S = {6} with the extra preference of actions A = {4}. The weight = 0.3 and the value = 1 are fixed.
Discussion With the extra preference on actions the preferred states appear less often for both preferences, but still the preferred state appears the most often for the preference S = {8}. On (c) States for S = {8} the other hand the results for actions are pretty good for both. The preferred state S = {6} with the extra preference of action occurs even much less often, as expected, because these preferences contradict. But still the results are not bad. The user can be satisfied with the results because they could prioritized the results of actions over the poorer results concerning states.
Experiment 3. We would like to show how the parameter influence the results. We try improve our results for the preferred state S = {6}, which gives worse results. We should be able to improve the results when there is no additional preference of actions. If the exploration parameter will be bigger, the selection of the action will not be uniform, but will be concentrated on the action, which guarantees the preferred state.
(a) States (b) Actions
Discussion We can see, that we can improve the previous results via the parameter . We tried many values of , and present the best of for which the preferred state occurs the most often. The actions that cause the state 6 are around the action 2.
Experiment 4. We showed that the results of the experiments are influenced by the parameters and . That is why we left these parameters to be free for the dialogue with the user. We choose their values according to the responses of the users. We would like to show, that they can get the desired results without any knowledge of DM and PE theories just using our algorithm. The users were instructed to want S = {6} without an additional preference of actions A = A and then S = {8} with their preference of actions A = {4}. (c) States for the 2nd user (d) Actions for the 2nd user
Discussion In the Fig. 4 we can see that the results for S = {6}, A = A are much better for the 1st user. The occurrence of the preferred state is pretty high and it appears the most often. For the 2nd user the results are worse. The preferred state does not appear as much often and its occurrence is low. If we look at the evolution of the free parameters and marks Fig. 5, we can see that the courses of weight are very similar and the weight is zero most of the time, which we assumed, because there is no additional preference. The courses of parameter are pretty different. The 1st user’s is almost all the time between 2 and 5 and the 2nd user’s declines to the value 0.1. That is because the 2nd user was strict with their marking, they were not so satisfied and that’s why the algorithm tries to increase the exploration and find the results to satisfy the user. Because of that the results got worse and we got into dead end. So it really depends on the user’s strategy. Thanks to the 1st user we can see that we can get good results but also thanks to the 2nd user we can see that if the algorithm gets bad feedback, it will worsen the results.
Discussion For the preferences S = {8}, A = {4}, Fig. 5 the both users got great results. These preferences are not in a contradiction and as we could see above, it is easy for the system to reach this state. We can see from marking that both users were satisfied. The courses of the weight and differ. The 1st user’s weight increase more and parameter decrease more than for the 2nd user. The 2nd user’s parameters are more consistent but the frequencies of preferred state and action do not differ much.
Table 3 shows the prices paid for actions and states for S = {8}, A = {4}. For S = {6}, A = A the results can be judged in the same way.
We can see that the total price is the best (the lowest) for the 2nd user because they had the
= 0.0, = 1 = 0.3, = 1 1st user 2nd user
The price of actions 1086 181 281 219 top number of selections of the preferred action and the preferred state occurs also very often. They were satisfied as can be seen on the evolution of marks Fig 7. So we can say that it is the best result of our experiments. But the user are different so for someone it is a good results and for someone else not, because the prices that the users are willing to pay are individual. That we should keep in mind. The ”objective” numerical comparison is of secondary importance. We also repeat that the users got the results they want without any knowledge of DM theory. It is also less time demanding to find a good policy via their feedback during the DM.
The paper presents the quantification of preferences within the fully probabilistic design of decision results. It provides the user’s feedback that optimizes free parameters and . It presents the experiments which show how the fixed parameters influence the DM. It compares the DM with and without the user’s control. The algorithm does not need users any additional knowledge of the DM and PE theories.
The further research should: ✓ care about dimensionality curse connected with other wishes; ✓ add more free parameters, e.g., extensions of preferred sets of states and actions; ✓ address continuous systems; ✓ more specific application and real-system cases; etc.
These are hard tasks requiring more research to fill the gaps in the built universal DM theory, cf. Motivation.
Acknowledgement: We would like to thank for the support of this paper by grant MŠMT SGS21/165/OHK4/3T/14 and by the department of Adaptive Systems of Institute of Information Theory and Automation of the Czech Academy of Sciences. [4] Boutilier, C.: A POMDP formulation of preference elicitation problems. In: Proc. of the 18th National Conf. on AI, AAAI-2002. pp. 239–246. Edmonton, AB (2002) [5] Boutilier, C., et al: A constraint-based approach to preference elicitation and decision making. In: Proc. of AAAI Spring Symp. on Qualitative Decision Theory, pp. 19–28. AAAI Press (1997) [6] Brace, I.: Questionnaire design. How to plan, structure and write survey material for effective market research. Kogan Page, London (2004) [7] Braziunas, D., Boutilier, C.: Elicitation of factored utilities. AI Magazine 29(4), 79–91 (2008) [8] Chen, L., Pu, P.: Survey of preference elicitation methods. Tech. Rep. IC/2004/67, HCI
Group Ecole Politechnique Federale de Lausanne, Switzerland (2004) [9] Dwivedi, Y., et al: Artificial intelligence (AI): Multidisciplinary perspectives on emerging challenges, opportunities, and agenda for research, practice and policy [10] Feldbaum, A.: Theory of dual control. Autom. Remote Control 22, 3–19 (1961) [11] Greco, C., Suglia, A., Basile, P., Semeraro, G.: Converse-et-impera: Exploiting deep learning and hierarchical reinforcement learning for conversational recommender systems.
In: Conf. of the Italian association for artificial intelligence. pp. 372–386. Springer (2017) [12] Guy, T., Kárný, M., Rios-Insua, D., Wolpert, D. (eds.): Proc. of the NIPS 2016 Workshop on Imperfect Decision Makers, vol. 58. JMLR (2016) [13] Guy, T., Kárný, M., Wolpert, D.: Decision Making and Imperfection, vol. 474. Springer,
Berlin (2013) [14] Guy, T., Kárný, M., Wolpert, D.: Decision Making: Uncertainty, Imperfection, Deliberation and Scalability, vol. 538. Springer, Switzerland (2015) [15] Hutter, M.: Universal Artificial Intelligence: Sequential Decisions Based on Algorithmic
Probability. Springer, Berlin, Heidelberg, N.Y. (2005) [16] Kárný, M.: Fully probabilistic design unifies and supports dynamic decision making under uncertainty. Inf. Sci. 509, 104–118 (2020) [17] Kárný, M.: Towards on-line tuning of adaptive-agent’s multivariate meta-parameter. Int. J.
of Machine Learning and Cybernetics 12(9), 2717–2731 (2021) [18] Kárný, M., Guy, T.: Preference elicitation within framework of fully probabilistic design of decision strategies. In: IFAC Int. Workshop on Adaptive and Learning Control Systems. vol. 52, pp. 239–244 (2019) [19] Kárný, M., Siváková, T.: Agent’s feedback in preference elicitation. In: 2021 20th International Conference on Ubiquitous Computing and Communications (IUCC/CIT/DSCI/SmartCNS). pp. 421–429 (2021). https://doi.org/10.1109/IUCC-CIT-DSCISmartCNS55181.2021.00073 [20] Mesbah, A.: Stochastic model predictive control with active uncertainty learning: A survey on dual control. Annual Reviews in Control 45, 107 – 117 (2018) [21] Müller, V., Bostrom, N.: Future Progress in Artificial Intelligence: A Survey of Expert
Opinion, pp. 555–572. Springer Int. Pub. (2016)
[22] Šindelárˇ, J., Vajda, I., Kárný, M.: Stochastic control optimal in the Kullback sense.
Kybernetika 44(