Week 1: May 25 ~ May 31
I came to Providence right after finishing all my finals. Getting into the DREU program and renting an apartment from a stranger on Craigslist - everything had been surreal until the moment that I got off the taxi. The other DREU student, Hang Chen from UVa, had moved in two days ahead of me. This is a three-storey house situated in a quiet neighborhood. Hang helped me moving my huge suitcase up. This place is where I am going to spend my summer at!
I went to Brown with Hang the next day. There was a group meeting in the morning, and I met Amy and all our teammates. There were two graduate students and eight undergrads, including me and Hang. Victor and Eric are the two graduate students. Victor has had a paper published on ad auction algorithm, but he is graduating. Max, Donnie, Jordan, and Moshe are all undergrads at Brown, but some of them will be working on the project part-time (Evan and Aaron will join next week). The first meeting was a bit confusing for me, because I had not had a chance to read the spec of the game, and most people in the team had taken a class with Amy during the past semester.
It took us quite a while to get settled because of the complexity of Brown's impossible network. I got two cards and three passwords on the first day! The assignment for the week was to read the spec and read the code of two baseline agents built in class by two other students. They use very simple bidding strategy but have satisfactory results. This is a good exercise, since I learn the environment of the game and understand what stage we are.
Apart from work, the first week was fun. For the first time, I tried cooking for myself, and I got mixed results. I spent the weekend exploring the neighborhood and getting to know our neighbors.
Week 2: June 1 ~ June 7
We got our office this week! This week we were suppose to work on "models" but I could not come up with anything useful. I was burning to write my own agent, especially because I see that some of our baseline agents can be improved. Also, as I was going over the notes of the class, I was captivated by the idea of "equating profit" agent. I put things together and finally got my agent running - it was doing a pretty good job! The exercise gave me more sense of what matters in the game. However, as Amy wanted me to hand her a formal write-up, I tried to prove whether the algorithm had any property. Only then I realize that it did not. Although we believed that it was a good approximation, it did not give optimal solution in general.
Something amazing happened this week - the chief engineer from the search agency (TSA) visited us and gave us a talk on what they were doing. They have a software that generates bids for keywords for google's ad auction - that is they have an agent that works in real ad auctions! The engineer introduced the many approaches that they had taken and we also learned the differences between real world auctions and our simulated environment. Nonetheless, I was amazed by how close this is related to real world application
We took a walk in Brown's campus that weekend. Although we went to the CS department everyday, we never really visited the main campus. Brown is smaller than I thought. We met a really kind staff of Brown that gave us a brief introduction of Providence and Brown. I always admired the architecture of classic New England buildings. I also mailed a couple of Brown postcards to my parents, friends and professors.
Week 3: June 8 ~ June 14
Hang and I were getting our old agents fixed because qualification round would be next week! I was still looking for new ideas of our agents as I was slightly disappointed by last week. Also I began to think about the importance of models - our original assignment that I kept putting off. Finally, I came up with another model-heavy approach and talked to Victor about it. Victor liked the algorithm suggest me writing another write-up. The more I thought about the idea, the more excited I got into it. Yet before I could do that, I had to fix existing agents and run some simulations for next week...
Besides work, Hang and I walked to downtown on Saturday. We spent much time at the mall and had good dinner. Also, we were lucky because there was waterfire that evening. It was gorgeous! (The picture of my homepage is the river in daytime. And the wood was lighted when it was dark.) Everyone was on the street. There was a live jazz concert as well. Providence is such a pretty city!
Week 4: June 15 ~ June 21
We got the 3rd place in the qualification round! I remade this agent out of two of our old rule-based agent. The implementation of a rule-based agent looks like a lot of if-then statements. The agent has some sort of general goal, and it attempt to move close to its goal in each iteration (or day). For example, our agent here attempts to equate profit across queries. It does so by setting some subgoals which can be achieve by changing bids and spending limit. However, there is no guarantee that agent will be able to do so. Also, the agent does not know by how much it should change its bid and limit, it just increase or decrease the parameters by a small, predetermined amount. A rule-based agent can have stable performance, assuming that it has reasonable rules. I think it is a good try for this complex setting and a good baseline. The problem is that it is not optimal and we should be able to do better by effectively using all information given.
As a team, we were pretty sure that we would use a model-based agent for the real competition. More specifically, the agent should be able to estimate the bid price of positions, how many clicks a given position can get, the impression for different types of queries, etc. Then based on all these estimates, the agent needs to make optimal decisions. The algorithms that we had were: MCKP (multiple-choice knapsack problem), ILP (integer linear programming), portfolio selection. I proposed a new algorithm under the MCKP model and hade been working on the implementation.
On Thursday, we had a serious discussion of models. Now that we had a lot of good data from the qualification round, we have no excuse for postponing model design. Hang, Jordan and I will need to work on the bid/position to number of clicks models. I also planned to finish my implementation and do some testing.
This weekend I went to Boston to visit a friend. We went shopping and had a lot of yummy food.
Week 5: June 22 ~ June 28
The first two days, I was still working on the implementation of my model based agent. Because we did not have good models yet, this new agent does worse than the rule-based one. It was quite disappointing but not surprising. It only means we need to work harder on models!
Donnie parsed all data from the qualification round into a mysql database. We used jdbc and jfreechart to get some pretty graphs to get a sense of what sort of model we can make. We find out that the position to number of clicks model looks like a pretty logarithmic function, but the bids to anything model looks like a box. This is not surprising because the position to number of clicks model is more relevant to the underlying user population distribution which has some patterns. However, the bids to other thing models seem to be more useful.
We agreed that we were going to run regression and see what we could get. Aaron, who was working on bid to CPC models developed a time series regression model. Initially, he had an offline model and Jordan helped to automate the regression online using Java and R. I helped in making an offline baseline, since we are not going to have enough information on the first days, we will need to make prediction out of the database using the same method. We are a little behind schedule, since the competition is only 2 weeks away now. But we think it will not be too hard to extend this method to other models.
Week 6: June 29 ~ July 5
This week we first worked on the bid to click probability model, or bid to position model and position to number of clicks model. We managed to find another workable online regression model for bid to click probability, but we did not get very far on bid to position model. We discussed some ideas of equilibrium price but did not find them helpful. I personally believe that since the game lasts only for 60 days, and there is only 8 agents, equilibrium pricing does not make much sense. Although, We could modify the algorithm so that the agent will not reason about position at all and go directly from bid to number of clicks. Also, Eric had a break-through on the conversion probability model. His idea was inspired by the talk from TSA. Donnie and Eric together implemented it and it was ready to use.
I also spent sometime trying to make DP work with the newly developed models, yet it seems that because the model was not very accurate, the DP agent was not doing so great against the baselines. There was much frustration this week, because I realize the dynamics of the game is hard to grasp. We had an agent that crashed on day 15, but won the game (the system would assume that the agent use the same bid bundle as yesterday if it fails to prepare one, so a crashing agent winning a game is not entirely crazy). Finally, Amy suggest that we look back at some baseline agents.
We started to pick up G3Agent, a rule based agent. The idea is from one student who took the class in the Spring semester - it has very simple rules - guess the same profit that you want to make on all the quries and bid accordingly. The only model it uses is the conversion probability model.
I went to Boston to see my friends on Saturday. Some of them were doing research/intern in Boston and some of them came up from New Haven. We spent the evening in a karaoke place and went to the bank of Charles river to see the fireworks.
Week 7: July 6 ~ July 12
Last week before the competition! G3Agent was re-coded and tweaked. It became the best agent by far. It tried to achieve the same thing that the agent we entered for the qualification round should achieve - but it had a more effective way to do so. This week we need to work on budgetting and targetting strategy (as we believed they were generic for all types of agents), schedule test runs to decide which agent to enter for the final (the two contending agents were G3 and MCKP; Hang and I sponsored G3 and Jordan sponsored MCKP), and make posters about the work we had been doing.
All the tasks went along pretty well. MCKP and other sophisticated agents had budgetting strategies by nature of their algorithms. We decided that we will only put a loose safety-net-like campaign budget for G3. Max did an overall study for targetting and developed a targetting strategy model. We made different versions of our candidates, e.g. G3 with targetting, G3 with targetting and budgetting, etc. On Thursday, we set our machines to run tests on varies versions of our agents. G3 and MCKP performed equally well in the testing - the final decision was: since there would be two servers running simultaneously, we will enter G3 for one and MCKP for the other. On Sunday, we left for the Trading Agent Design and Analysis (TADA) workshop held in conjunction with IJCAI at Pasadena. We are all quite nervous.
Week 8: July 13 ~ July 19
We attended the TADA workshop on Monday, where we heard professors and students present their papers on various kinds of trading agent research - there were studies in auction theory, human-agent competition, and various methods and theories applied in TAC games. Apart from TAC AA, there are TAC SCM (supply chain management) and TAC Market Design. The TAC games is not just a competition, for the researchers at the workshop, it also provides means for understanding these games. This is the first year that the organizer includes the ad auction game and the key developer of this game is a phD student at University of Michigan. For us, the most important thing of these two days was the outcome of the TAC AA games!
During the workshop, our agent was competing in the semifinals. There were 15 agents entering the semifinals, and the top 8 agents would compete in the final on Tuesday. Overall, we got the 2nd place in the semifinals. The team from Univeristy of Texas at Austin (their agent's name was TacTex) got the first place. Donnie gave us a quick analysis of G3 and MCKP. Surprisingly, G3 and MCKP had similar results again. Also, we found out that the performance of TacTex on the two servers was drastically different. We thought they had two different agents just as we did. We decided that we were going to use G3 for the medium capacity games, MCKP for the high capacity games, and for the low capacity games we would "flip a coin."
Tuesday was a casual day. We went to the workshop room early in the afternoon to follow the final. Our hybrid agent got the third place. TacTex won the first place and AstonTac got the second place. We chatted with the developer of TacTex after the game ended. We found out, with much surprise, that they did not enter two agents for the semifinals! Also, their winning agent accomplished something that we did not have time to finish. They had a good impression model and something like a bid to position model. AstonTac's developers were not there, but it seemed that their agent placed the same bid since day 10. I think they might be finding some equilibirum price, yet their agent did not do as well in the semifinals.
Everyone was satisfied with the result, yet I still felt that I did not fully understand this game even at this point. We are going to do some formal analysis and hopefully get most of a paper done for the rest of the time.
Week 9: July 20 ~ July 26
This week is devoted to a paper that will summarize what we have done for the summer. We had a meeting and divided the tasks. We would need to clean up our code for release, write the section on simple agents and dynamic programming agent, and run some experiments using different agents. We finished a first draft of our simple agent section. Writing isn't fun, and I honestly would prefer coding a huge program to writing a paper. On Friday, we had farewell ice cream together.
We went to Newport on Saturday. I really recommend it! We toured the mansions from the Gilded age and wandered along the cliff walk. The mansions were summer houses for the business magnates of the late 1800s and early 1900s, and were centers of social events of the elites. They were masterpieces of art and architecure, and I loved them. Yet, to some extent they were also a living proof that luxury and happiness do not always go together. Since the owners of the most ostentatious ones only enjoyed the mansions for a very little time.
Week 10: July 27 ~ July 31
This week I continued working on refining the write ups. I attempted to analyze the difference between algorithm that focuses on profit per click (PPC) and profit per sale (PPS). In theory, equating the true marginal profit would always be optimal. However, since the true marginal profit is hard (maybe even impossible) to find, PPC and PPS are two possible approximations. Yet it was hard to tell which one was better on paper. In our experimenets, it seemed that using PPS was better than PPC. The rest of time, I took a look at another almost forgotten agent - the ILP agent. It also formulates the game as a MCKP and formulate it as an ILP. It could be a good agent if we had more time to work on it.
I spent much of my last weekend cleaning the house (again), but I did get a chance to take some pictures of the campus and Providence, and it was finally sunny after a wet week! The two months here left me with so much great memories, and I enjoyed the experience so much!