在这篇短文中，我将基于过去一年中的研究经验，简单地分享一下我目前对行为决策建模的见解。

In this post, I will briefly discuss some of my current thoughts on decision behavior modeling based on my research experience over the past year.

抽象地来看，决策行为即在给定决策信息$s$（下称状态）的情况下，通过某种策略$\pi$采取动作$a$

From an abstract point of view, decision making is to take an action $a$ according to a certain strategy $\pi$ given decision information $s$ (hereinafter referred to as the state)

$$a \sim \pi(s).$$

而行为决策建模，则希望根据观察数据$\mathcal{D} = \{(s,a)\}_n$，获取决策机制$\pi$的相关信息。

While decision behavior modeling attempts to infer the strategy $\pi$ from observations $\mathcal{D} = \{(s,a)\}_n$.

由于数据集$\mathcal{D}$是有限的，能够很好地拟合该数据集的$\pi$可能有无穷多个。因此，研究者通常需要对$\pi$的形式做出额外假设。而一个最基础且核心的假设是$\pi$服从效用最大化原理。

Because the dataset $\mathcal{D}$ has finite datapoints, there can be an infinite number of $\pi$ that fits well into the dataset. Therefore, researchers often need to make additional assumptions about the form of $\pi$. And one of the most fundamental assumptions is that $\pi$ follows the utility-maximization principle.

Introduction

Inverse reinforcement learning (IRL) is the dual of reinforcement learning (RL) and aims at recovering the reward function that the agent optimizes with. Compared with supervised learning (behavior cloning, BC), IRL imposes more restrictive regularity conditions on the set of policies and is more appropriate in cases with inadequate expert demonstrations and for robust estimations. For example, consider a routing problem on a grid network: the optimal actions taken by the agent are geographically correlated. In this case, compared with BC, IRL has a higher chance of recovering the internal reward structure and leads to more consistent actions across space.

In this post, I will briefly introduce several recent works using the generative adversarial network (GAN) for IRL and discuss their connections.

交通即人与物在时空上的流动。从本质来看，交通系统的设计是为这种流动提供可靠的载体。在交通系统设计不能得到改进的情况下，在提高出行能力（即满足更多的出行需求）与缓解城市拥堵之间必然存在着取舍。这种在出行能力与拥堵之间的取舍平衡，在下面的讨论中中将统一称为系统供需平衡。我这一年在交通方面的研究，主要就是关注于各类共享出行服务（shared mobility）对这种系统供需平衡的影响。

This semester, when I was working on homework of 1.200, there was a frequently asked question: under what situation would the queue system have a steady state? It is claimed that system with finite capacity always have a steady state, but no proof is given in the class. In this post, I will discuss the dynamical system approach for this problem, and suggest several extensions.

Last semester, in course 1.202 Demand Modeling, there is an interesting case study of Quebec energy consumption. Exploratory data analysis indicates that there are potential market segments, and subsequent computation shows that multinomial logit models estimated from separate datasets have a better total log likelihood than the one from the whole dataset. An interesting question then arises: can we discover latent classes efficiently on high dimensional data?

This June, when traveling in Mexico, I encountered one of the most unexpected congestion in my life. The horrible performance of Google Maps was annoying and during the summer I kept thinking about how to model and solve this problem. In last several days, I realized the tools we needed were no more than high school arithmetics.

Inner Approximation: $V$-representation, Dantzig-Wolfe decomposition, and Branch and Price

Assume we are given problem

$$\begin{aligned} z_I =\max & \ c^Tx \\ s.t. & \ A_1 x \leqslant b_1 \\ & \ A_2 x \leqslant b_2\\ & \ x \in R^{n_1} \times Z^{n_2} \end{aligned}$$

and we know that LP relaxation for $Q=\{A_2 x \leqslant b_2, x \in R^{n_1} \times Z^{n_2}\}$ is tight but that for the whole problem is weak. One can then think of dual approach utilizing the tighter local constraint structure:

Cuts are important tools to strengthen your formulation and improve computation efficiency. In this post, I will introduce two kind of cuts: geometric cuts, which consider the geometric property of the polyhedron and have general application, and implicit cuts, which are more problem specific but potentially can lead to very strong formulation.

Unbalanced Branching and Encoding

Consider constraint $\sum_i x_i= 1$ with $x_i\in \{0,1\}$, which arises naturally in problem with selection (e.g. union of polytope $x\in \cup_i P_i$). Recall that, in standard MIP solver, $x_i$ is first relaxed into continuous variable, and then forced to be integer with B&B. For the constraint above, when we branch on a fractional $x_i$, we have two choices, $x_i=1$ or $x_i=0$, but the result of each branch is different. With $x_i=1$, we immediate know $x_j=0, \forall j\neq i$, even though they are still assumed continuous. But with $x_i=0$, the optimal solution might still contain another fractional $x_j$ and further branching is needed. In extreme case, we need to branch $n-1$ times to locate the optimal integer solution.

Assume we need to solve a mixed integer linear program (MILP), and the feasible region is $S\subseteq R^{n_1}\times Z^{n_2}$.  For some reasons we don’t have a simple formulation of $S$, and we want to use some polyhedron $P=\{(x,y)\in R^{n_1+n_2}\times R^{m_1+m_2}: Ax+By\leqslant b\}$ and its subset $P_I=P\cap R^{n_1}\times Z^{n_2}\times R^{m_1}\times Z^{m_2}$ to represent $S$. Notice that we can use auxiliary variables $y$; these representation are called extended (sometimes we MUST have some integer variables $y$ to construct a valid formulation; in this case, the formulation is not extended). One important question is: what is a good representation?