AI Research
Three papers from my Artificial Intelligence coursework at Boise State. Each starts with a question I could not answer by reading, so I built something to find out: how an agent reasons about what it cannot see, what it costs to plan perfectly, and whether a neural network is actually the right tool.
1. Reading a Room Full of Strangers
Suspicion: A Graph Based Approach to Knowledge Tracking During Game Play
Suspicion is a hidden-identity board game. Every player secretly holds one of ten guest identities, collects gems, and has to work out who everyone else is from indirect, ambiguous clues. A good player doesn't memorize a board. They keep a running theory of the room.
I wanted to know whether an agent could do the same with plain logic instead of a learned model of belief. So each agent draws that theory as a graph. Players sit on one side and the ten possible identities on the other. An edge means "this could still be you." Evidence removes edges until only the consistent possibilities remain.
The graph does most of the thinking. Hall's Marriage Theorem says that if some group of players shares exactly as many candidate identities as there are players in the group, those identities belong to that group and nobody else. That lets an agent delete edges it has never directly observed.
For the final guess, the pruned graph goes into a small Graph Convolutional Network that scores every player against every identity. The agent commits only its most confident guess, updates the graph, and runs the network again, so each decision sharpens the next one.
I ran four agents plus a random baseline through two 1,000-game tournaments.
The agents built on the graph won roughly three to four times as often as chance. The agent that learned its own value function from play did no better than random. In this game, the quality of the deduction mattered far more than the cleverness of the strategy. A small amount of structure outperformed a learned belief model.
2. What a Perfect Plan Costs
Scaling Dynamic Programming on Finite MDPs
Dynamic programming is the gold standard for planning: given a complete model of the world, it finds the provably optimal policy. The catch is that "complete" gets expensive fast. I used Jack's Car Rental problem from Sutton and Barto, in which a company moves cars between two lots to meet uncertain demand, to see where that cost starts to bite.
First I replicated the base problem. The optimal policy reads like common sense once you see it: move cars toward whichever lot is running short.
Then I changed the rules to see how the policy would respond. In Exercise 4.7, one car per night shuttles for free and any lot holding more than ten cars pays a parking penalty. The policy reorganized around those costs.
The core of the paper is scale. I grew the number of states from about a hundred to over forty thousand, and compared synchronous evaluation, which sweeps the whole table each pass, against asynchronous evaluation, which updates states in place.
Finally, I gave the agent a second job: pick the rental price as well as move the cars, using a demand model in which the two lots respond differently to price. The extra decision made the problem much heavier, and the asynchronous advantage grew with it.
The takeaway is practical. Dynamic programming reliably finds interpretable, optimal policies, but the cost grows quickly enough that real-world problems need approximation.
3. Do You Need a Neural Network?
Social Media Prediction: Gradient-Boosted Trees vs. Towered Neural Networks
Can a model look at a Flickr post, meaning the photo, its title and tags, and its metadata, and predict how popular it will be? I took the SMPD-Image dataset from the Social Media Prediction Challenge, about 486,000 posts from 70,000 users, and gave two very different models the same inputs: CLIP embeddings of each image and its text, plus tabular metadata.
One was a towered neural network. Each kind of input gets its own tower, and the three are fused into a single prediction. It looks like the right answer for multimodal data.
The other was CatBoost, a gradient-boosted tree ensemble that treats everything as columns in a table.
I validated with 5-fold cross-validation grouped by user. A post from the same account never appears in both the training and test folds, so the model can't win by memorizing who posted.
Both models beat the baselines comfortably, which confirms the embeddings carry real signal. CatBoost beat the neural network, though, and it did so across all five folds. My read is that this dataset is a tabular problem at heart. Trees handle a messy mix of counts, categories, and dense vectors without being taught how, and the network has to learn all of that from scratch.
The more interesting finding is what the dataset leaves out. It has no follower counts or account history, and a photo posted by someone with a large following will reach more people than the identical photo from someone with none. That sets a ceiling on what any model looking only at content can do. The paper points toward graph-based approaches, which model how posts spread through a network.