Higher Uncertainty Leads to Less Exploration in a Combinatorial Discovery Game

Venue: NeurIPS_cc_2024_Workshop_BDU
Published: 2024-08-27 08:32:28

Abstract: How do people decide whether it is worth pursuing innovation? For example, in machine learning new methods often result from combining existing methods, but there is a risk that a given combination will not work. While seasoned experts could use their intuitions gained through experience to decide whether some combinations are worth trying out, novices to the field have to learn these insights while trying to maximize their rewards. Here, we formalize this problem and derive optimal policies for agents who know, or do not know, how likely each kind of combination is to succeed, emulating the effects of expert knowledge. Our model predicts that novices should not only gather fewer rewards, but also explore systematically less than the experts. An online behavioral experiment ($n=300$) supports this finding, showcasing the profound impact of domain expertise in guiding innovative decision making in a combinatorial space.

Main paper: 
 combinatorial discovery games: 
 Following [3] , we first define a basic combinatorial discovery game G as a tuple ⟨M, T, A, R⟩, where M is a set of items, T the game tree containing successful combinations, A a set of actions, and R the reward function. Combining an item m ∈ M and item n ∈ M is denoted as c(m, n). If c(m, n) ∈ T , this is a successful combination and will produce a new item, say, c(m, n) ⇒ o; if c(m, n) ̸ ∈ T , the combination fails and no new item is discovered. Items that cannot be produced by combining other items are base items, m 0 , with base reward r. Climbing up the game tree increases levels: for a combination c(m i , m j ) ⇒ m k , k = max(i, j) + 1, and the reward associated with item m k is w k • r.Players can take two actions A = {use, combine}. Action use receives the rewards associated with the item, R(use(m k )) = w k r, and action combine combines two items of the player's choice. The immediate reward for taking this action is always zero, R(combine(m, n)) = 0.A discovery game can be parameterized by a success rate p ∈ [0, 1]-the probability of receiving a successful discovery for any given item, and the reward increase rate w > 1. [3] showed that these definitions form a Markov decision process (MDP), and under a finite horizon of D steps in total, the optimal policy in this particular setting corresponds to an optimal stopping problem [4] : One should keep attempting innovation (combine) until a switch point d, then focus on collecting the highest possible existing rewards (use). The expected return for switching at step d isEQUATIONand the optimal switch point isd * = arg max d E π(d) .Solving Equation 1 analytically states that a rational player should switch from use to combine when there is d ′ steps left, whereEQUATIONThe above policy specifies what a rational agent should do when they have complete information about the success rates and reward increase rates. In the real world, this setup corresponds to an expert with strong domain knowledge, enabling informed decisions that drive innovation and yield desirable outcomes.To account for uncertainty in domain knowledge, we extend the setup in [3] to include types of items, aiming to reflect a more realistic scenario where different types of things may be associated with different success rates and reward increase rates-like which kinds of chemicals can be productively combined together. A discovery game with types G τ extends a discovery game G ∪ {Z, σ , τ}, where type indices Z = {1, 2, . . . , z} is a finite set of integers, and σ : M → Z maps each game item to a type index. For |Z| = z number of types, choosing two types from z with replacement-allowing sametype combination-is given by z+2-1 2 = (z+1)! 2!(z-1)! ways of combining types of items. We denote each kind of these combinations by τ.Each kind of combination has its own success rate p τ and reward increase rate w τ . Experts are defined as those knowing the p τ and w τ for all τ. An expert can thus estimate the maximum total reward for each kind of combination using Equation 1, and apply Equation 2 to compute the optimal switch point d * τ for the kind of combination that produces the highest rewards. Formally, the rational decision is to optimize along the most rewarding τ:EQUATIONNon-experts, or novices, are not blessed with such information. They are tasked with both inferring the relevant parameter values, and maximizing their rewards. While the reward increase rate w can be known immediately after a successful combination is found, the success rate p poses a harder inference problem. Without loss of generality, we model a novice's belief about the success rate with a beta distribution Given this prior, the novice player updates their belief about p τ after observing x τ successes out of n τ attempts of combine actions for this kind of combination, withEQUATIONEQUATIONThe novice player can integrate the belief defined in Equation 5with Equation 2 to estimate a switch point d * τ given their current belief of success rate p τ for τ, and it is possible to compute the max expected reward for each τ using Equation 1. The novice player can then apply the same decision rule in Equation 3 to choose which kind of combination they will interact with, and choose the actionEQUATIONNote that Equations 1-6 effectively equate to Thompson Sampling [5] , a posterior sampling algorithm widely used in online learning problems [6] .For a novice's prior belief, we set α τ = β τ = k, representing no biases about whether a kind of combination is particularly promising or devastating. We ran simulations with symmetric beta priors k = 1, . . . , 10, and number of item types z = 2, 3, 4, 5, leading to |τ| = 3, 6, 10, 15 respectively. Figure 1 summarizes these simulation results, and reveals that novices both gain fewer rewards and attempt fusion less frequently than the experts. How strong the prior is-reflected by the k valueshas no substantial influence on the learner's behavior; domain richness-measured by the number of item types-has a much stronger impact: The richer the domain is, the bigger the differences between the novice's and the expert's performances are. These results suggest that higher uncertainty for the novices can lead to more conservative behavior in this particular setting. 
experiment: 
 We test these model predictions in a pre-registered online behavioral experiment (https:// osf.io/x2ymd/?view_only=84c4b13ea553457c8661e426169623a9). The experiment was approved by the university ethics committee (ref. no. omitted for anonymity).Three-hundred participants were recruited from Prolific Academic (age 35 ± 12, 55% female). The experiment took 10 ± 19 minutes. No participants were excluded from analysis. All participants gave informed consent before undertaking the experiment.We used a cover story of making alien crystals that could be used to generate points. Participants could either use an existing crystal (action use), or fuse any two existing crystals together (action combine). A fusion attempt led to a new crystal with probability p. Participants could take 10 actions in each game. Each game had 4 types of alien crystals indicated by 4 shapes: square, triangle, diamond (upside-down triangle), and circle. These four shapes form 10 kinds of combinations (square + square, square + circle, etc.). All crystals start at the base level with r = 100 points. We set the reward increase rate w = 1.5 for all kinds of combinations and let all participants know this was the case. Notably, one of the ten kinds of combinations had a high success rate (p H = 0.8), Participants first read the instructions and had to pass a comprehension quiz to start the task. Each participant completed 5 practice trials and then 5 task trials. Each trial has only one high-p kind of combination, sampled randomly and independently. The experiment ended with a short debriefing.See the experiment in action at https://bz.velezlab.opalstacked.com/crystals-ep/p/ exp.html.We only analyzed data in the task trials. As illustrated in Figure 2a -b, overall, participants in the expert condition collected more total rewards and created items with higher levels. We conducted a mixed-design Analysis of Variance (ANOVA) with condition as the primary factor and task as a repeated measure to assess the effects. The results reveal that for total rewards, there is a significant effect of condition (F(1, 298) = 163.479, p < 0.0001), but not for task Crucially, as predicted by the model, participants in the novice condition attempted fewer fusion actions (Figure 2c ). A mixed-design ANOVA with condition as the primary factor and task as a repeated measure indicated a significant effect (F(1, 298) = 13.183, p = 0.000332), and not for task (F(3.75, 1116.59) = 0.285, p = 0.877) or the interaction between condition and task (F(3.75, 1116.59) = 0.928, p = 0.442).Interestingly, despite being less exploratory in the sense of attempting fewer fusions, participants in the novice condition interacted with more item types (Figure 2d ). Again, a mixed-design ANOVA with condition as the primary factor and task as a repeated measure indicated a highly significant effect of condition (F(1, 268) = 329.443, p < 0.0001), and not for task (F(3.83, 1027.65) = 0.770, p = 0.540) or the interaction (F(3.83, 1027.65) = 0.370, p = 0.822). 
conclusion: 
 Advancing discoveries via recombination is a crucial aspect of human intelligence, ranging from creating physical tools to proposing new theories, or even literally creating novel chemical compounds or protein structures. We examined decision policies in a task sharing a similar combinatorial nature, and in particular investigated the influence of domain uncertainty. As both predicted by the model and supported by empirical data, higher uncertainty not only led to fewer rewards or less advanced items, but also lower rate of exploration, although touching on a wilder range of domains. These results emphasize the importance of integrating domain-expertise in guiding effective exploration, and warn the undesirable possibilities of reward-driven policies in highly uncertain domains. 
 
 Appendix:  



Reviews: review: title: title: review
main_review: main_review: Strengths:

1. Relevance and Timeliness: The paper addresses an important and timely topic in AI and decision-making under uncertainty, which is crucial for understanding innovation processes.

2. Theoretical Foundation: The authors provide a solid theoretical framework, extending previous work on combinatorial discovery games to include domain uncertainty. The use of Bayesian modeling and Thompson Sampling is appropriate and well-justified.

3. Empirical Support: The inclusion of a behavioral experiment with a substantial sample size (n=300) adds empirical weight to the theoretical predictions.

4. Clear Methodology: The paper outlines a clear and replicable methodology, both for the theoretical model and the experimental design.

5. Interdisciplinary Approach: The study bridges theoretical computer science, decision theory, and behavioral psychology, which is valuable for a top AI venue.

Weaknesses:

1. Limited Scope: The study focuses on a specific type of combinatorial discovery game, which may limit its generalizability to real-world innovation processes.

2. Simplification of Expertise: The binary categorization of "expert" vs. "novice" may oversimplify the spectrum of domain knowledge in real-world scenarios.

3. Lack of Deeper Analysis: While the results support the main hypothesis, there's limited discussion on why novices interact with more item types despite being less exploratory overall. This unexpected finding warrants more in-depth analysis.

4. Missing Long-term Implications: The paper doesn't adequately address how the observed short-term behaviors might impact long-term innovation outcomes.

5. Limited Discussion of Practical Applications: The authors could have elaborated more on how these findings might be applied to real-world AI development or innovation strategies.

6. Potential Confounds: The experiment's cover story (alien crystals) might introduce unintended biases or misunderstandings among participants. A more neutral framing could have been considered.

Recommendations:

1. Expand the discussion on the unexpected finding of novices interacting with more item types. This could lead to valuable insights about different exploration strategies.

2. Consider running additional experiments with varying levels of expertise to create a more nuanced understanding of how domain knowledge impacts exploration.

3. Provide more discussion on how these findings might be applied in real-world AI development or innovation processes.

4. Conduct sensitivity analyses to test the robustness of the model under different parameters and assumptions.

5. Include a section on limitations and future work to address potential criticisms and outline next steps for this line of research.

Overall Evaluation:
This paper presents a novel and important contribution to understanding decision-making under uncertainty in combinatorial discovery tasks. The combination of theoretical modeling and empirical testing is a strength. However, the limited scope and some missed opportunities for deeper analysis slightly diminish its impact. With the suggested improvements, this paper could be a strong candidate for acceptance at a top AI venue. As it stands, it's a good fit for a workshop and with revisions could be suitable for a main conference.
title: title: Interesting finding
main_review: main_review: ## Summary:

The authors follow the assumption that creating new things by recombining existing things (such as drug design by recombining molecular structures) can be formalized by a Combinatorial Discovery Game (CDG). Then, this paper try to answer how domain knowledge affect a rational agent's decision making in a CDG. This work extends existing models to better predict human decision-making behavior at different levels of domain knowledge. Their model shows that novices should not only gather fewer rewards, but also explore systematically less than the experts.  The authors also conducts an online behavioral experiment to support the finding. 

In my opinion, the authors' finding is interesting and counter-intuitive (i.e., novices explore less than experts). I believe this finding is useful to help researchers design new exploration methods for reinforcement learning agents (such as knowledge-guided exploration). However, I have some concerns about the technical contributions of this paper, as the extensions to previous models seem to be trivially.



### Clarity : 
   The paper is well-structured and the writing is fluent and easy to read.

### Quality :
  The problem focused by this paper is interesting, but the technical contribution seems insufficient. However, It should be emphasized that the content and finding of this paper is valuable and inspiring for me.

### Originality :
   To the best of my knowledge, this work is novel.

### Significance :
   While the finding of this paper is interesting, I am concerned about its significance given the simplicity of the setting and the lack of deeper analysis provided.