For questions related to the linear programming optimisation technique used in the context of AI (e.g. in the context of RL, in order to solve an MDP).
Questions tagged [linear-programming]
10 questions
5
votes
1 answer
What are the differences between constraint satisfaction problems and linear programming?
I have taken an algorithms course where we talked about LP significantly, and also many reductions to LPs. As I recall, normal LP is not NP-Hard. Integer LP is NP-Hard. I am currently taking an introduction to AI course, and I was wondering if CSP…
Prabh Dhali
- 51
- 2
5
votes
1 answer
How can we use linear programming to solve an MDP?
Apparently, we can solve an MDP (that is, we can find the optimal policy for a given MDP) using a linear programming formulation. What's the basic idea behind this approach? I think you should start by explaining the basic idea behind a linear…
nbro
- 42,615
- 12
- 119
- 217
4
votes
1 answer
What AI technique should I use to assign a person to a task?
I'm trying to learn AI and thinking to apply it to our system. We have an application for the translation industry. What we are doing now is the coordinator $C$ assigns a file to a translator $T$. The coordinator usually considers these criteria…
Jaime Sangcap
- 143
- 4
2
votes
1 answer
Are linear approximators better suited to some tasks compared to complex neural net functions?
Model based RL attempts to learn a function $f(s_{t+1}|s_t, a_t)$ representing the environment transitions, otherwise known as a model of the system. I see linear functions are still being used in model-based RL such as in robotic manipulation to…
mugoh
- 549
- 4
- 21
2
votes
1 answer
Which algorithm can I use to solve a problem with multiple objectives and constraints?
Consider a problem with many objectives. In my case, these are school grades for different courses (or subjects). To be more concrete, suppose that my current grade for the math course is $12/20$ and for the philosophy course is $8/20$. My objective…
YLM
- 121
- 3
1
vote
0 answers
Linear / Quadratic Program for Solving MDPs
Aside from value iteration, we can use the following linear program to solve the optimal value function of an MDP.
I am planning to put some constraints on the policies class that I consider, for example,…
Lyapunov1729
- 41
- 3
1
vote
0 answers
Solving MDP as linear program: why minimize the sum of the states' values?
This is a follow-up question to the answer to How can we use linear programming to solve an MDP?
Quick recap: the $max$ operators that appear in the Bellman optimality equations can be turned into a set of inequality constraints in hope of making a…
Celelibi
- 111
- 1
0
votes
0 answers
How to train a neural network with a non-differentiable linear program in the loss?
I am currently trying to train a neural network to predict certain input parameters for a linear program based on an input dataset of system measurements related to these parameters. The workflow is something like this:
System measurements -->…
0
votes
1 answer
Why are policy gradients popular in RL when there exists a dual LP formulation in terms of occupation measures that can be solved easily?
Why are policy gradient methods popular in reinforcement learning when there exists a dual LP formulation in terms of occupation measures that can be solved easily?
0
votes
1 answer
Is it possible to solve a linear programming problem using reinforcement learning? (DDPG algorithm)
I'm trying to solve a linear programming problem using reinforcement learning.
The linear programming problem is:
\begin{array}{ll}
\text{maximize}_x & C* x \\
\text{subject to}& A*x \le b\\
& x_i \in [0,1],\ where \…
Avarash Goel
- 1
- 2