Valdinei Freire

valdinei.freire@usp.br

São Paulo, SP

Brazil

Since 2011, I am an Assistant Professor at EACH-USP in the Bachelor Undergraduate Program in Information Systems (BSI) and in the Graduate Program in Information Systems (PPgSI).

I hold a Ph.D. in Electric Enginer (2009) and a bachelor in Computer Engineer (2002), both from Escola Politécnica (USP) . During my Ph.D., I was a visiting scholar in the Instituto Superior Técnico, in Lisbon.

Research Interests:
My current research efforts focus on various aspects of sequential decision making under the frameworks of Markov Decision Process and Reinforcement Learning. In particular, I have been developing and studying models that consider a Risk Sensitive Evaluation. Although most of my work is theoretical, lately I have been applying MDP and RL to Education.

Fragmentos Estocástico:
Since January 2020, I have been maintained a Youtube channel in Portuguese, Fragmentos Estocásticos. There, I present snippets of MDP and RL theory. It may serve as a fast introduction to the mathematics behind MDP and RL.

selected publications

JBCS

ALICAT: a customized approach to item selection process in computerized adaptive testing

G. Jatobá, V.M., Farias, J.S., Freire, V., and Delgado, Karina V.

JOURNAL OF THE BRAZILIAN COMPUTER SOCIETY, 2020

Abs HTML

Computerized adaptive testing (CAT) based on item response theory allows more accurate assessments with fewer questions than the classic paper and pencil (P&P) test. Nonetheless, the CAT construction involves some key questions that, when done properly, can further improve the accuracy and efficiency in estimating the examinees’ abilities. One of the main questions is in regard to choosing the item selection rule (ISR). The classic CAT makes exclusive use of one ISR. However, these rules have differences depending on the examinees’ ability level and on the CAT stage. Thus, the objective of this work is to reduce the dichotomous test size which is inserted in a classic CAT with no significant loss of accuracy in the estimation of the examinee’s ability level. For this purpose, we analyze the ISR performance and then build a personalized item selection process in CAT considering the use of more than one rule. The case study in Mathematics and its Technologies test of the ENEM 2012 shows that the Kullback-Leibler information with a posterior distribution (KLP) has better performance in the examinees’ ability estimation when compared with Fisher information (F), Kullback-Leibler information (KL), maximum likelihood weighted information (MLWI), and maximum posterior weighted information (MPWI) rules. Previous results in the literature show that CAT using KLP was able to reduce this test size by 46.6% from the full size of 45 items with no significant loss of accuracy in estimating the examinees’ ability level. In this work, we observe that the F and the MLWI rules performed better on early CAT stages to estimate examinees’ proficiency level with extreme negative and positive values, respectively. With this information, we were able to reduce the same test by 53.3% using the personalized item selection process, called ALICAT, which includes the best rules working together.
MICAI

Risk-Sensitive Piecewise-Linear Policy Iteration for Stochastic Shortest Path Markov Decision Processes

Dias Pastor, H., Oliveira Borges, I., Freire, V., and Valdivia Delgado, L.

In Martínez-Villaseñor L., Herrera-Alcántara O., Ponce H., Castro-Espinoza F.A. (eds) Advances in Soft Computing. MICAI 2020. Lecture Notes in Computer Science, 2020

Abs HTML

A Markov Decision Process (MDP) is commonly used to model a sequential decision-making problem where an agent interacts with an uncertain environment while looking for minimizing the expected cost accumulated along the process. If the process horizon is infinite, a discount factor γ ∈ [0, 1] is used to indicate the importance the agent gives to future states. If the agent’s mission is to achieve a goal state, the process becomes a Stochastic Shortest Path MDP (SSP-MDP), the in fact model used for probabilistic planning in AI. Although several efficient solutions have been proposed to solve SSP-MDPs, there are little research carried out when we consider the “risk” in such processes. A Risk Sensitive MDP (RS-MDP) allows modeling the agent’s risk-averse and risk-prone attitudes, by including a risk and a discount factor in the MDP definition. The proof of convergence of known solutions based on dynamic programming adapted for RS-MDPs, such as risk-sensitive value iteration (VI) and risk-sensitive policy iteration (PI), rely on the discount factor. However, when solving an SSP-MDP we look for a proper policy, i.e. a policy that guarantees to reach the goal while minimizing the accumulated expected cost, which is naturally modeled without discount factor. Besides, it has been shown that the discount factor can modify the chosen risk attitude when solving a risk sensitive SSP-MDP. Thus, in this work we aim to formally proof the convergence of the PI algorithm for a Risk Sensitive SSP-MDP based on operators that use a piecewise-linear transformation function, without a discount factor. We also run experiments in the benchmark River domain showing how the intended risk attitude, in an interval of extreme risk-averse and extreme risk-prone, varies with the discount factor γ, i.e. how an optimal policy for Risk Sensitive SSP-MDP can go from being a risk-prune policy to a risk-averse one, depending on the discount factor.
BRACIS

Finding Feasible Policies for Extreme Risk-Averse Agents in Probabilistic Planning

Fernandez, M.C., Barros, L.N., Mauá, D., Delgado, K.V., and Freire, V.

In Cerri R., Prati R.C. (eds) Intelligent Systems. BRACIS 2020. Lecture Notes in Computer Science, 2020

Abs HTML

An important and often neglected aspect in probabilistic planning is how to account for different attitudes towards risk in the process. In goal-driven problems, modeled as Shortest Stochastic Path (ssp) problems, risk arises from the uncertainties on future events and how they can lead to goal states. An ssp agent that minimizes the expected accumulated cost is considered a risk-neutral agent, while with a different optimization criterion it could choose between two extreme attitudes: risk-aversion or risk-prone. In this work we consider a Risk Sensitive ssp (called rs-ssp) that uses an expected exponential utility parameterized by the risk factor λ that is used to define the agent’s risk attitude. Moreover, a λ-value is feasible if it admits a policy with finite expected cost. There are several algorithms capable of determining an optimal policy for rs-ssp s when we fix a feasible value for λ. However, so far, there has been only one approach to find an extreme λ feasible i.e., an extreme risk-averse policy. In this work we propose and compare new approaches to finding the extreme feasible λ value for a given rs-ssp, and to return the corresponding extreme risk-averse policy. Experiments on three benchmark domains show that our proposals outperform previous approach, allowing the solution of larger problems.
ICAPS

An Exact Algorithm to Make a Trade-Off between Cost and Probability in SSPs

Freire, Valdinei, Delgado, Karina Valdivia, and Silva Reis, Willy Arthur

In Proceedings of the International Conference on Automated Planning and Scheduling 2019

Abs HTML

In stochastic sequential decision problems, such as Stochastic Shortest Path Problems, the GUBS (Goal with UtilityBased Semantics) criterion considers a trade-off between probability-to-goal and cost-to-goal using a goal semantics based on Expected Utility Theory (EUT); in such a semantics, goal paths have priority over non-goal paths, but it implies neither the MAXPROB criterion nor the dual optimization criterion that finds the cheapest policy among the policies that maximize goal probability. Whereas evaluation criteria based on a sound theory such as EUT are desirable, optimal policies under GUBS are non-markovian. Non-markovian solutions are undesirable because there is not always a finite representation and even if it can be represented in a finite way, the representation may be too large to be stored. Here we define a special case of GUBS criterion that allows a finite representation to the optimal policy, the eGUBS criterion, where the cost utility function is exponencial. Considering this special case, we contribute with: (i) the proof that the eGUBSoptimal policy has a finite representation; (ii) the first exact algorithm to obtain finite optimal policies for the eGUBS criterion, and (iii) four strategies to find sub-optimal policies. We conduct experiments on one synthetic problem to evaluate each strategy. Although optimal solutions have a high memory cost, sub-optimal policies can save memory space with a small decrease in performance.
AAMAS

GUBS: A Utility-Based Semantic for Goal-Directed Markov Decision Processes

Freire, Valdinei, and Delgado, Karina Valdivia

In Proceedings of the 16th Conference on Autonomous Agents and MultiAgent Systems 2017

Abs HTML

A key question in stochastic planning is how to evaluate policies when a goal cannot be reached with probability one. Usually, in the Goal-Directed Markov Decision Process (GD-MDP) formalization, the outcome of a policy is summarized on two criteria: probability of reaching a goal state and expected cost to reach a goal state. The dual criterion solution considers a lexicography preference, by prioritizing probability of reaching the goal state and then minimizing the expected cost to goal. Some other solutions, consider only cost by using some math trick to guaranteed that every policy has a finite expected cost. In this paper we show that the lexicography solution does not allow a smooth trade-off between goal and cost, while the expected cost solution does not define a goal-semantic. We propose GUBS (Goals with Utility-Based Semantic), a new model to evaluate policies based on the expected utility theory; this model defines a trade-off between cost and goal by proposing an axiomatization for goal semantics in GD-MDPs. We show that our model can be solved by any continuous state MDP solver and propose an algorithm to solve a special class of GD-MDPs.